전체 글

[자료구조] 힙

힙 힙(heap) 자료구조는 우선순위 큐를 구현하기 위해 사용하는 자료구조중 하나다! 우선순위 큐는 우선순위에 따라 처리하고 싶을 때 사용 예를들어 여러개의 데이터 중 자료구조에 넣었다가 우선적으로 꺼내고 싶은 데이터부터 꺼내서 체크할 때 우선순위 큐를 사용하면 효과적이다. PriorityQueue heapq 파이썬에서는 위 라이브러리로 구현할 수 있다. 최소힙, 최대힙을 이용하는데 최소힙을 사용할 경우 가장 낮은 데이터가 우선적으로 삭제되고 최대힙을 사용할 땐 가장 높은 데이터가 우선적으로 삭제됨 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선으로 방문하므로 최소힙을 사용하는 것이 적합! 우선순위 큐 구현 방식 삽입시간 삭제시간 리스트 O(1) O(N) 힙 O(logN) O(logN) ※해..

[알고리즘] 최단경로 찾기

최단경로 다익스트라 최단 경로 알고리즘 플로이드 워셜 알고리즘 그리디알고리즘과 다이나믹 알고리즘이 적용됨! 다익스트라 최단 경로 알고리즘 다익스트라(Dijkstra) 알고리즘은 여러개 노드가 있을 떄 특정노드에서 다른 노드로 도착하는 각각의 최단 경로를 구하는 알고리즘이다. 매번 가장 비용이 적은 노드를 선택하는 과정을 반복하기 떄문에 그리디 알고리즘으로 분류 음의 간선이 없을 때 적용가능하다. 과정 1. 출발 노드 선정 2. 최단 거리 테이블 초기화(무한으로 초기화) 3. 방문 하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택 4. 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 생성 5. 3번과 4번의 과정 반복! import sys input=sys.stdin.readline ..

[알고리즘] 다이나믹 프로그래밍

다이나믹 프로그래밍 다이나믹 프로그래밍(Dynamic Programming)기법은 동적계획법이라고도 하는데, 메모리공간으 더 사용해서 연산속도를 증가시킬 수 있는 알고리즘이다. 탑다운 방식 보텀업 두가지 방식이 있다. 다이나믹 프로그래밍을 사용할 수 있는 조건 큰 문제를 작은 문제로 나눌 수 있을때 작은 문제에서 구한 답이 작은 문제를 포함하는 큰 문제에서도 답이 동일할 때 대표적인 예시로 피보나치 수열로 설명을 할 수 있다. 피보나치 수열은 이전 두항의 합이 현재의 항이 되는 수열이다. 1 1 2 3 5 8 13 21 34 55 ... 이런식으로 말이다. 이를 점화식으로 표현하면 an=an-1+an-2, a1=1, a2=1 단순히 코드로 표현하면 def fibo(a)i : if a==1 or a==2:..

[이것이 코딩테스트다] 이진탐색 부품찾기

입력 조건 첫째 줄에 정수 N이 주어짐 (1

[알고리즘] 이진탐색

이진탐색 이진탐색(Binary Search)은 반으로 쪼개가면 탐색하는 알고리즘이다. 단, 데이터가 정렬되어있다는 것을 전제조건으로 깔고 간다. 이를 위해 시작, 끝, 중간점을 변수로 지정하여 찾으려는 값과 배열의 중간점에 있는 데이터를 반복적으로 비교한다! 시간복잡도 : O(logN) 코드 구현 #이진탐색은 전제조건을 정렬이다. #처리해야할 데이터 개수나 값이 1000만 단위 이상으로 넘어가면 이진탐색과 같이 o(logn)의 속도를 내는 이진탐색을 고려야한다 def binary_search(array, target, start, end) : if start>end : return None pivot=(start+end)//2 if array[pivot]==target : return pivot elif..

[알고리즘] DFS/BFS

DFS DFS(Depth-First Search)는 깊이 우선 탐색 알고리즘이다. 그래프에서 깊은 부분을 우선으로 탐색하는 것이다. 그래프가 그럼 뭘까? 그래프는 Node(혹은 정점이라고 부르기도함(vertex))와 Edge(간선)로 표현된다. 예를 들어 노드를 장소, 간선을 거리라고 생각할 수도 있다. 약국에서 병원까지의 거리를 3km, 약국에서 학교를 5km라고 한다면 아래 이미지처럼 표현할 수 있다. 약국 병원 학교 약국 0 3 5 병원 3 0 무한 학교 5 무한 0 ※ 연결되지 않은 노드는 무한으로 표현한다 그래프는 두가지 방식으로 표현된다. 인접 행렬 : 2차원 배열로 그래프의 연결관계를 표현 인접 리스트 : 리스트로 그래프의 연결관계를 표현 인접행렬(Adjacency Matrix) INF= 9..

스택과 큐

자료구조란? 데이터를 표현하고 관리하고 처리하기 위한 구조 삽입 : 데이터를 삽입 (PUSH) 삭제 : 데이터를 삭제 (POP) 스택 스택(stack)은 이름 그대로 쌓는걸 생각하면 된다. 블럭을 쌓는 놀이를 한다고 생각해보자 처음엔 차근차근 블럭을 아래에서 위로 쌓을 것이다. 다시 쌓은 블럭을 해체시키려면 위에서부터 하나씩 꺼내야한다. 즉 맨 마지막에 쌓은 블럭을 젤 먼저 뽑는 거다. 이를 선입후출이라고 한다! stack=[] stack.append(2) stack.append(3) stack.append(1) #stack->[2,3,1] stack.pop() #stack->[2,3] stack.pop() #stack->[2] stack.pop() #stack->[] 큐 큐(Queue)는 음식점 대기줄..

[이것이 코딩테스트다] 구현 (3) 게임개발

실전 문제 난이도 ●● 풀이시간 40분 시간제한 1초 메모리 제한 128MB 문제 1x1 크기의 정사각형으로 이뤄진 NxM 크기의 직사각형으로 각각의 칸은 육지 또는 바다. 캐릭터는 동서남북 중 한 곳을 바라봄 맵의 칸은 각 (A, B)로 나타낼 수 있으며 A는 북쪽으로부터 떨어진 칸의 개수. B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 메뉴얼은 이러하다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전하는 방향)부터 차례대로 갈 곳을 정함 2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로부터 한칸을 전..