그래프를 탐색하는 방법에는 크게 두 가지가 있다. 깊이 우선 탐색(Depth First Search, DFS) 저번에 봤듯이 Stack 또는 재귀의 단계를 활용하여 구현 너비 우선 탐색(Breadth First Search, BFS) 탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후, 방문헀던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로 선입선출 형태의 자료구조인 큐를 활용 순서 def BFS(G, v): # 그래프 G, 탐색 시작점 v visited = [0]*(n+1)# n: 정점의 개수 queue = [] # 큐 생성 queue.append(v) # 시작점 v를 큐에 삽입 while que..

분할 정복이란 말 그대로 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다. 정복(Conquer) : 나눈 작은 문제를 각각 해결한다. 통합(Combine): (필요하다면) 해결된 해답을 모은다. 거듭제곱을 통한 예제를 통하여 분할 정복을 알아보자. 기존의 함수를 구현한다면 O(n)의 시간 복잡도가 걸린다. def Power(Base, Exponent): if Base == 0: return 1 result = 1 # Base^0는 1이므로 for i in range(Exponent): result *= Base return result 분할 정복 기반 알고리즘을 통한다면 O(log 2 n)의 시간 복잡도가 걸리는데 어떻게 이렇게 될 수 있을까? 어떤 정수 C^8 = C x C x C..

# 백트래킹 해를 찾는 도중에 '막히면' (해가 아니면) 되돌아가서 다시 해를 찾아가는 기법 최적화(optimization) 문제와 결정(decision) 문제를 해결할 수 있다. 결정 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'No'가 답하는 문제 미로 찾기, n-Queen 문제, 부분 집합의 합 등.. 정의를 보면 앞서 봤던 DFS-깊이 우선 탐색과 비슷한 것 같다. 미로 찾기 예를 통해서 어떤 차이가 있는지 알아보자. 미로 찾기 아래 그림과 같이 입구와 출구가 주어진 미로에서 입구부터 출구까지의 경로를 찾는 문제 이동할 수 있는 방향은 4가지로 제한된다. 내가 지나가는 경로를 스택에 저장해준 후 pop을 이용해 다시 경로를 되돌아 갈 수 있다. # 백트래킹과 깊이우선탐색의..

LIFO 구조의 Stack을 이용하여 계산기를 구현해보자. 여기서의 계산기는 중위 표기법(infix notation) (A+B)를 후위 표기법(postfix notation)(AB+)으로 변경하여 스택을 이용하여 계산한다. 중위 표기식의 후위 표기식 변환 방법 1 수식의 각 연산자에 대해 우선순위에 따라 괄호를 사용하여 다시 표현 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동시킨다. 괄호를 제거한다. 변환 알고리즘 2 (스택 이용) 입력받은 표기식에서 토큰을 읽는다. 토큰이 피연산자이면 토큰 출력 토큰이 괄호를 포함한 연산자일 때, 토큰이 스택의 TOP에 저장되어 있는 연산자보다 우선순위가 높으면 스택에 PUSH 하고, 그렇지 않다면 스택 top의 연산자의 우선순위가 토큰의 우선순위보다 작을 때까지..

1ㄷ1 관계는 선형구조라고 불렀고 1ㄷN의 관계는 트리라고 불렀다. 그럼 N:N의 관계는 어떤 구조일까? 바로 그래프 구조라고 부른다. 비선형 구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요하다. 특히, 그래프와 비슷한 트리와의 큰 차이점은, 순환(Cycle) 할 수 있다는 것 이를 위한 탐색 방법 2가지가 있는데 오늘은 우선 DFS에 대해 알아볼 것이다. 깊이 우선 탐색 (Depth First Search, DFS) 너비 우선 탐색 (Breadth First Search, BFS) 두 방법의 차이 DFS는 탐색을 한 뒤 이전의 정점으로 돌아온다 이것은 백트래킹(Backtracking)이라고 부른다 # DFS - 깊이 우선 탐색 시작 정점의 한 방향으로 갈 수 있는 경로가 ..

앞에서 보았던 피보나치 수를 재귀 함수로 구하는 프로그램은 "엄청난 중복 호출" 이라는 큰 문제가 존재한다. 이를 해결하기 위해 동적 계획법의 핵심 기술인 memoization에 대해 먼저 알아보자 # memoization 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술 글자 그대로 해석하면 '메모리에 넣기 (to put in memorty)'라는 의미 앞서 구했던 fibo(n)의 값을 계산하자 마자 저장하면 O(2^n) 시간을 O(n)으로 줄일 수 있다. 이제 memoization을 활용한 Dynamic Programming에 대해서 알아보자 # DP(Dynamic Programming) 동적 계획 알고리즘은 그리..

문제 참고 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 키와 몸무게가 주어질 때 두 가지 모두 커야 덩치가 크다. 각각 리스트에 넣어준 후 for문을 이용해 모두 큰 경우에만 카운팅을 해주었다. 하지만 문제에서 원하는 결과는 '내가 몇번 째로 크냐'가 아닌 '나보다 큰 사람이 몇명인가' 였다. N = int(input()) height = [] # 키를 담을 리스트 weight = [] # 몸무게를 담을 리스트 cnt = N f..

문제 참고 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 이해부터 조금 난해한 문제였다.. 결론은 서류 성적과 면접 성적 중 그 누구와 비교해도 두 성적 모두 낮지만 않으면 된다. 브루트포스와 같이 2중 for문을 통한다면 정말 쉽게 구할 수 있을 줄 알았다. # 시간초과 1 #입력받은 성적을 순회하며 두 성적 모두 떨어진다면 제외 for j in range(len(grade)): for k in range(len(..

문제 참고 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 정해진 시간 동안 가장 많이 회의를 진행하는 문제였다. 시작 시간과 끝나는 시간에 대한 정렬을 통하여 비교 기준을 저장해주고 반복문을 통해 비교를 해주었다. 처음엔 정렬을 하지않고 2중 for문을 통하여 기준을 그때그때 바꿔주려고 하였다. # 1931_회의실 배정 # N개의 회의에 대해 회의실 사용표를 만든다. # 각 회의 I에 대해 시작 시간과 끝나는 시간이 있고 회의가 겹치지 않으며 사용할 수 있는 최대 개수 # 회의는 중간에 중단 불가하고 회의의 시작 시간과 끝나는 시간이 같을 수 있다. # 전체..