할머니의 콤퓨타 도전기

브루트 포스는 완전 탐색, 모든 경우의 수를 탐색하여 결과를 도출하는 기법 (노가다와 다굴을 논리적이고 과학적으로 하는 방식) 어쩔 수 없이 모든 경우의 수를 탐색해야 하는 경우, 모든 경우의 수를 요구하는 문제에서 주로 사용

이분 탐색 탐색 범위를 두 부분으로 분할해서 찾는 방식. 따라서 전부를 탐색하는 것에 비해 속도가 빠름 시간 복잡도 O(log(n)) 1. 이미 정렬이 되어있어야 이분 탐색 가능 2. left, right로 mid 값을 결정 3. mid 값과 구하고자 하는 값 비교 4. 비교할 때 mid 값보다 구하고자 하는 값이 크면 left를 mid + 1로, 낮으면 right를 mid-1로 만듦 5. left > right 가 될 때 까지 위의 과정을 반복해 구하고자 하는 값 찾음

다이나믹 프로그래밍이란 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 크고 어려운 문제가 있으면, 그것을 먼제 잘게 나누어 해결한 뒤에 처리하여 나중에 전체의 답을 구하는 것 Memoization이 사용됨 이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야할 때는 저장된 값을 단순히 반환하기만 하면 됨 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 -> 이 두 가정이 모두 성립하면 다이나믹 프로그래밍 사용 가능

합집합 찾기(Union-Find), 서로소 집합(Disjoint-Set) 알고리즘 여러 개의 노드 중 두 개의 노드를 선택해서, 이 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘입니다. 1. 우선 모든 노드가 연결되지 않고 자신만을 집합의 원소를 갖고있도록 만듭니다. 따라서 모든 값이 자기 자신을 가리키도록 합니다. 첫 번째 행은 노드 번호, 두 번째 행은 부모 노드 번호입니다. 즉, 각 노드 번호가 어떤 부모에 포함되어 있는지를 의미합니다. 1 2 3 4 5 1 2 3 4 5 2. 1번 노드와 2번 노드가 연결되어있다고 가정합시다. 1 2 3 4 5 1 1 3 4 5 부모를 합칠 때에는 더 작은 값 쪽으로 합치는 것(Union)이 일반적입니다. 따라서 1번 노드와 2번 노드가 연결되면 2번 노드의..

크루스칼 알고리즘(Kruskal Algorithm) 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. (최소비용신장트리를 만들기 위한 대표적인 알고리즘) 여러개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자할 때 실제로 적용합니다. ​ 모든 간선정보를 오름차순으로 정렬한 뒤에 (간선 거리(비용)이 짧은(적은) 순서대로 정렬) 비용이 적은 간선부터 차근차근 그래프에 포함시키면 됩니다. 1. 정렬된 순서에 맞게 그래프에 포함 2. 포함시키기 전에는 사이클 테이블 확인 3. 사이클을 형성하는 경우 간선을 포함시키지 않는다 ​ 사이클이 발생하는 지의 여부는 Union-Find 알고리즘을 적용하면 됩니다. #include #include #include..

문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작..