세상을 바꾸는 데이터

① 문제 링크 https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net ② 알고리즘 분류 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 ③ ★문제풀이 Point★ - 순환선에 속하는 역은 깊이 우선 탐색(dfs) 실시 - 각 역과 순환선 사이의 거리는 너비 우선 탐색(bfs) 실시 ④ 풀이 이 문제는 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구하는 문제다. 1. 순환선에 속하는 역 구하기 각 역과 ..

① 문제 링크 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net ② 알고리즘 분류 그래프 이론, 그래프 탐색, 깊이 우선 탐색 ③ ★문제풀이 Point★ - N(인원수)의 범위가 2000이 최대이므로 방문 표시를 2001개 만들기 - dfs를 돌리며 조건(5명의 친구 관계가 성립)에 맞는지 확인 ④ 풀이 이 문제는 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력하는 문제이다. 문제에서 캠프에 있을 수 있는 명수 N가 최대 2000이므로 방문 표시 visited를 2001개 지정해준다. 친구 관계를 나타내는 리스트 rela..

① 문제 링크 https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net ② 알고리즘 분류 그래프 이론, 그래프 탐색, 깊이 우선 탐색 ③ ★문제풀이 Point★ - 전형적인 DFS 문제 ④ 풀이 이 문제는 게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구하는 문제로 전형적인 DFS 문제다. 사이클이 만들어지는 조건에 대해 살펴보자. 1. 4개 이상의 서로 다른 점으로 구성되어 있어야 함. 2. 시작 지점이 끝 지점과 일치해야 함. 3..

① 문제 링크 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ② 알고리즘 분류 이분 탐색, 매개 변수 탐색 ③ ★문제풀이 Point★ - 이분 탐색(이진 탐색)의 개념을 알고 있는지 여부 ④ 풀이 이 문제는 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하는 문제다. 이 문제를 풀기 위해서는 이분 탐색 알고리즘에 대해 알아야 한다. 이분 탐색 ..

① 문제 링크 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net ② 알고리즘 분류 자료 구조, 스택 ③ ★문제풀이 Point★ 1. 스택(stack)을 제대로 알고 있는지 여부 2. 스택에 push 하는 순서는 반드시 오름차순인 점 ④ 풀이 이 문제는 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop ..

① 문제 링크 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net ② 알고리즘 분류 구현, 브루트포스 알고리즘 ③ ★문제풀이 Point★ 1. 인접한 두 칸을 바꾸는 작업 필요 2. 인접한 두 칸을 바꾼 후 상근이가 먹을 수 있는 사탕의 최대 개수(count_candy) 구하고, 전체 사탕의 최대 개수(ans)와 비교하여 최댓값(ans)을 반환 ④ 풀이 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하는 문제다. 전형적인 브루트포스(완전 탐색) 문제이다. 먼저 사탕의 색이 다른 인접한 두 칸을 고르는 것은 파이썬..

① 문제 링크 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net ② 알고리즘 분류 구현, 시물레이션 ③ ★문제풀이 Point★ 1. 문제에서 요구하는 내용 그대로 충실히 코드 구현하기 2. 공기청정기 바람 이동은 파이썬의 swap(변수 바꾸기) 이용하기 ④ 풀이 이 문제는 방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구하는 문제이다. 문제에서 요구하는 대로 먼저 미세먼지의 확산 함수(dust_diffusio..

문제 링크: https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 풀이 유형: 수학, 정수론, 그리디 ★문제풀이 Point★ 1. 시간 복잡도 파악 2. 최적의 해를 도출하기 위한 방법 생각 풀이 과정: 이 문제는 자연수 N이 주어졌을 때, g(N)을 구하는 문제이다. 필자는 처음에 O(N^2) 방식을 이용해 하나씩 비교하며 답을 구하려고 했다. 그러나 주어진 문제에서 N = 1,000,00..