본문 바로가기

알고리즘/이론

 (52)
이진 트리 - 예제 1 [1. 문제 설명] https://algospot.com/judge/problem/read/NERD2 [2. 풀이 접근] [3. 코드]
트리 - 예제 2 [1. 문제 설명] [2. 풀이 접근] [3. 코드]
트리 - 예제 1 [1. 문제 설명] tree 에 대해서 전위 순회와 중위 순회가 주어졌을 때, 후위 순회 한 결과를 출력한다. [2. 풀이 접근] 비슷한 문제가 있었으니 자세한 설명은 아래를 참고 https://testkernelv2.tistory.com/354 [3. 코드]
06. 결정 문제 - 예제 2 [1. 문제 설명] N개의 도시를 지나치는데, i 번째 도시까지의 남은 거리를 나타내는 표지판이 도착하기 M 미터 전부터 시작해서 G 미터 간격으로 설치 된다. 시작점으로 부터 각 도시 까지의 거리(L) 와 M, G 에 대한 값이 주어질 때, K번째 표지판의 위치를 찾는다. Li, Mi, Gi (1
06. 결정 문제 - 예제1 [1. 문제 설명] n 개의 탐사기지와 무전기가 존재 모든 무전기의 통신 반경은 d 따라서, 두 탐사 기지 사이의 거리가 d 이하이어야만 연락 가능 항상 모든 기지 간에 서로 연락 가능하다록 하는 무전기의 최소 통신 반경을 계산 [2. 풀이 접근] printf / scanf 서식문자 https://testkernelv2.tistory.com/57?category=513498 [3. 코드]
05. 조합 탐색 - 예제2 [1. 문제 설명] m가지의 음식을 준비할 수 있고, n명의 친구를 초대하려고 한다. 각 친구가 먹을 수 있는 음식, 먹을 수 없는 음식이 주어질 때, 각 친구가 먹을 수 있는 음식이 최소한 하나씩 있게 하려면 최소 몇가지의 음식을 해야하는가? [2. 풀이 접근] NP 완비 문제 중 하나로, 다항 시간에 푸는 방법은 아직 없다. 탐욕적 접근 방법으로 가장 많은 사람들이 먹을 수 있는 음식을 만들어 보는 방식으로 접근 할 수 있지만, 모든 입력에 대해 최적해를 찾아낼 수는 없다. 예제) ??? 완전 탐색으로 접근 해서, 간단한 가지치기를 하면 답을 구할 수 는 있지만, 시간 내에 동작하지 않는다. 이 문제를 푸는 간단한 방법은 탐색의 형태를 바꾸는 것 이다. 매 재귀 호출마다 아직 먹을 음식이 없는 친구를..
05. 조합 탐색 [1. 개요] 동적 계획법이나 분할 정복 등의 문제 해결 방법을 모든 문제에 적용 할 수 없다. 캐시를 위한 메모리를 너무 많이 사용하거나 적절한 분할 방법이 없는 경우가 존재하기 때문이다. 이 경우 완전 탐색에서 다시 돌아와 생각 해야 한다. 부분 답과 완성된 답의 집합을 탐색공간이라 부른다. 완전 탐새의 수행 시간은 탐색 공간의 크기에 비례한다. 유한한 크기의 탐색 공간을 뒤지면서 답을 찾아내는 알고리즘을 조합 탐색이라 부르기로 한다. 기본적으로 최적해가 될 가능성이 없는 답들을 탐색하지 않는다. [2. 가지치기 기법] pruning 기법은 현재 상태에서 답의 나머지를 완성했을 때 얻을 수 있는 가장 좋은 답이 지금까지 우리가 구한 최적해보다 나쁘면 탐색을 더 하지 않는다. 똑똑한 가지치기 기법들은 ..
04. 탐욕법 - 예제3 [1. 문제 설명] [2. 풀이 접근] 적당한 사람을 배정 해야 할 때 vector 를 정렬해서 사용했을 시 문제점 탐색은 O(logn) 이 가능하나, 배정했으므로 vector 에서 제거해야 한다. 이 때, vector 특성 상 제거하는데, O(n) 시간이 소요된다. 이진검색트리인 set 혹은 multiset 을 사용한 경우 탐색과 제거 모두 O(logn) 에 할 수 있다. 그런데 set 은 중복 값을 저장 할 수 없으나 multiset 은 중복 값을 저장 할 수 있다. [3. 코드]
04. 탐욕법 - 예제2 [1. 문제 설명] n 개의 문자열들의 길이가 주어질 때, n 개의 문자열들을 순서와 상관없이 합쳐서 한개의 문자열로 만들 때 필요한 비용의 최소 값 ex) {al, go, spot} 을 합칠 때 {al+go}+spot => al+go 비용: 4, algo+spot 비용 8 => 총 비용 12 [2. 풀이 접근] 한 문자열이 전체 비용에 미치는 영향에 대해서 생각해보면 병합되는 문자열들의 총 길이가 전체 비용에 더해진다. 병합의 대상이 되는 문자열의 길이가 매번 전체 비용에 누적된다고 볼 수 있다. 위 예제에서 "al" 은 "al" + "go" 에서 전체 비용에 더해지고 "algo" + "spot" 에서 전체 비용에 더해진다 볼 수 있다. 그래서, 항상 길이가 짧은 두 문자열이 병합의 대상이 되게 하는 ..
04. 탐욕법 - 예제1 [1. 문제 설명] n 개의 도시락이 있고, i번째 도시락을 데우는데 m[i] 초, 먹는데는 e[i] 초가 걸린다. 도시락을 먹기 위해서는 도시락을 먼저 데워야 한다. 도시락을 여러번에 나누어 데울수는 없다. 모든 사람이 도시락을 다 먹을 때 까지 걸리는 최소 시간 [2. 풀이 접근] 스케줄링 문제는 보통 탐욕법으로 풀 수 있다. (모든 경우는 아님) 전체 시간 = n-1 개의 도시락을 데우는 시간 + 마지막 도시락을 먹는데 걸리는 시간 먹는데 오래 걸리는 도시락부터 데우면 된다. 먹는데 오래 걸리는 도시락을 먼저 데우면, 다른 도시락을 데우는 시간 동안 이 도시락을 먹을 수 있기 때문이다. === 탐욕적 선택 속성 증명 먹는데 가장 오래 걸리는 샤브샤브 도시락을 먼저 데우는 최적해가 반드시 하나 있음을..

티스토리툴바