본문 바로가기

알고리즘 코딩테스트/알고리즘 이론

 (7)
[ 이것이 코딩 테스트다 ] 6. 다이나믹 프로그래밍 다이나믹 프로그래밍 (Dynamic Programming)메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법 (동적 계획법)특정 범위의 값을 구하기 위해 이전 범위의 값을 활용하는 방법 다이나믹 프로그래밍으로 해결할 수 있는 문제에 대해 알아보자 피보나치 수열이전 두 하의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 이는 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게 표현할 수 있다. 수열 자체가 규칙에 따라서 배열된 형태를 의미하기 때문이다. # 피보나치 함수(Fibonacci Function)을 재귀함수로 구현def fibo(x): if x == 1 or x == 2: return 1 return fibo(x - 1) + fibo(x - 2)p..
[ 이것이 코딩 테스트다 ] 5. 이진 탐색 순차 탐색 (Sequential Search)리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 특정 데이터를 찾아야 할 때 사용되고 개수를 세는 count() 메서드를 이용할 때도 내부에서 순차 탐색이 수행된다.# 순차 탐색 소스코드 구현def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i + 1 # 현재의 위치 반환 (인덱스는 0부터 시작하므로 1 더하기) return -1 ..
[ 이것이 코딩 테스트다 ] 4. 정렬 정렬 (Sorting)데이터를 특정한 기준에 따라 순서대로 나열하는 것. 다음 장에서 배울 이진 탐색의 전처리 과정이니 제대로 학습하자.  선택 정렬 (Selection Sort)데이터 중에서 가장 작은 데이터를 선택해서 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]for i in range(1, len(array)): for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복 if array[j]  선택 정렬의 시간복잡도 : O(N**2) 직관적으로, 2중 반복문이 사용되었기 때문이라고 볼 수 있다.다른 알고리즘에 비해 매우 비효율적이지만,..
[ 이것이 코딩 테스트다 ] 3-2. DFS/BFS (탐색 알고리즘) DFS (Depth-First Search)깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선으로 탐색하는 알고리즘이다.DFS는 스택 자료구조와 재귀함수를 이용하여 구현한다. 동작과정1. 탐색 시작 노드를 스택에 삽입하고 방문 처리2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄3. 더 이상 2번의 과정을 수행할 수 없을때까지 반복  # DFS 메서드 정의def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i ..
[ 이것이 코딩 테스트다 ] 3-1. DFS/BFS (자료구조 기초) 탐색많은 데이터 중에서 원하는 데이터를 찾는 과정, 자료구조 안에서 탐색   ex) DFS, BF자료구조데이터를 표현, 관리, 처리하기 위한 구조   ex) 스택, 큐 가장 대표 탐색 알고리즘인 DFS와 BFS 원리를 이해하기 위해서는 기본 자료구조에 대한 이해가 필요하므로 기초 자료구조에 대해 학습해보자. 스택(Stack)스택은 박스 쌓기에 비유할 수 있다. 박스는 아래에서부터 위로 차곡차곡 쌓고 치우기 위해서는 위에 있는 박스를 먼저 내려야 한다. 즉, 선입후출 구조를 가지고 있다.stack = []# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()stack.append(5)stack.append(2)stack.append(3)stack.ap..
[ 이것이 코딩 테스트다 ] 2. 구현 구현머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 이 단원에서 완전탐색, 시뮬레이션 유형을  다루고 있다.완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행  문제 1. 상하좌우여행가 N * N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 * 1 크기의 정사각형으로 나누어져 있다.가장 왼쪽 위 좌표는 (1,1) 이며, 가장 오른쪽 아래 좌표는 (N,N) 이다. ( 시작좌표는 (1,1) 이다 )상하좌우로 한칸씩 움직이며 정사각형 공간을 벗어나는 움직임은 무시된다.L : 왼쪽 / R : 오른쪽 / U : 위쪽 / D : 아래쪽   한 칸 이동n = int(input())x, y = 1, 1plans = input()...
[ 이것이 코딩 테스트다 ] 1. 그리디 알고리즘 그리디(Greedy) , 탐욕법현재상황에서 지금 당장 좋은 것만 고르는 방법매 순간 가장 좋아 보이는 것을 선택하며, 현재 선택이 나중에 미칠 영향을 고려하지 않음  출제방식그리디 알고리즘은 "기준"에 따라 좋은 것을 선택하므로 문제에서'가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 알게 모르게 제시해준다.대체로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.  그리디 알고리즘의 정당성대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없기에 모든 알고리즘 문제에 적용할 수 없다. 거스름돈 문제(문제1)를 그리디 알고리즘으로 해결할 수 있는 이유는 "가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 ..

티스토리툴바