운동하는 개발자/알고리즘, 코딩테스트 (40) 썸네일형 리스트형 Beakjoon] 수 묶기 (백준 1744 코테) - 그리디 🅰️문제주소 : https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 🚩문제 🪡풀이 - 최댓값을 구하기 위해 공식을 잘 살펴보면 양/음 수끼리 절댓값이 큰 수의 곱을 묶어줘야 하며 0은 절대로 곱해져서는 안되며 양수 1은 곱해 봤자 이므로 더해줘야 한다. - 위의 분석으로 숫자는 4개의 타입을 가진다 (0, 1, 1을 제외한 양수, 음수) - 1을 제외한 양수와 음수는 우선순위 큐로 나눠서 정렬시키고 남은 수가 1개 이하가 될 때까지 곱을 묶어준다.. Beakjoon] K번째 수 (백준 1300 코테) - 탐색 🅰️문제주소 : https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 🚩문제 🪡풀이 - 문제 그대로 2차원 배열을 만들고 정렬을 시키면 시간복잡도가 N^2으로 초과해버린다. - A[i][j] = i×j 배열에서 두 가지의 규칙을 찾아야 한다. 1) 해당배열은 k번째 값은 k의 값을 넘지 못한다. (3x3배열에서 마지막 인덱스의 값이 9이므로) 2) 한 행에서 '중앙값을 행으로 나눈 값' vs '열의 수' 둘 중 작은 수.. Beakjoon] 트리의 지름 구하기 (백준 1167 코테) - 탐색 🅰️문제주소 : https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 🚩문제 🪡풀이 - 가장 긴 두 점 사이의 거리를 구하는 방법을 알아야 하는데 이는 임의의 어떤 한 점에서 가장 먼 곳의 위치를 찾아낸 후 그 위치로부터 가장 멀리 있는 곳까지의 거리로 구할 수 있다. - map을 그릴때 vector 으로 거리값도 함께 저장하면서 그린다. - 방문여부 배열과, 누적 거리 배열을 만든다. - 임의의 위치에서 BFS를 시작하고 누적거리 .. Beakjoon] 미로 탐색 (백준 2178 코테) - 탐색 🅰️문제주소 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 🚩문제 🪡풀이 - 최단경로를 구하는 문제로 BFS를 사용해서 도달한 깊이값을 사용하면 됨. - 상, 하, 좌, 우 이동이 가능하고 이 이동을 하기위한 값을 미리 저장해 둠. - 방문한 위치는 depth값을 기록하면서 해당 위치에 도달하기 위한 최솟값을 저장해 둠 ☕코드는 아래 숨김 더보기 #include #include #include #include static std::vector map; static std.. Beakjoon] DFS와 BFS (백준 1260 코테) - 탐색 🅰️문제주소 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 🚩문제 🪡풀이 - DFS와 BFS의 기본적인 구현. 탐색이 끊긴다던가 특정 depth의 값을 구하는 것이 아니므로 특별한 조건 없이 구현하면 된다. 주의할 점은 방문할 수 있는 정점이 여러개면 번호가 작은 것부터 방문하게 해야 한다는 것인데 이는 정렬을 통해 다른 조건을 줄 필요 없이 간단하게 해결된다. ☕코드는 아래 숨김 더보기 #includ.. Beakjoon] 연결 요소의 개수 (백준 11724 코테) - 탐색 문제주소 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 문제 풀이 - 기본적인 DFS 문제로 그래프를 그리고 재귀함수로 풀어내면 됨 코드는 아래 숨김 더보기 #include #include std::vector graph_map; std::vector visited; void DFS(int v) { if (visited[v] == true) return; visited[v] .. Beakjoon] 수 정렬하기 3 (백준 10989 코테) - 정렬 문제주소 : https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 - O(nlogn)으로도 풀 수 없는 시간복잡도의 수의 개수를 가지고 있다(10,000,000) c++의 sort로는 nlogn의 속도의 시간복잡도기에 계수정렬 O(kn)을 통해 풀어야 한다 코드는 아래 숨김 더보기 #include #include int main() { std::ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(N.. Beakjoon] 버블 소트 2 (백준 1517코테) - 정렬 문제주소 : https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 문제 풀이 문제 그대로 버블정렬로 카운트는 가능하지만 O(n^2)의 경우 시간복잡도에서 실패하게 된다. O(nlogn)의 시간복잡도로 문제를 풀어야 하는데 핵심 이론은 병합 정렬을 사용하되 병합정렬 시 뒤쪽 데이터가 앞으로 이동하는 경우는 이동한 칸만큼 swap이 일어났다고 볼 수 있다는 것이다. (이미 앞쪽데이터는 스왑에 의해 자동으로 뒤로 밀려나기에 카운트에.. 이전 1 2 3 4 5 다음
