백준
-
백준 6064 : 카잉 달력백준 2023. 11. 29. 16:05
1. 문제 : https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 2. 문제 접근 해가 지날 수록 $x$와 $y$에 $1$을 더함. $x$와 $y$는 현재 해를 각각 $M$과 $N$으로 나눈 나머지임. 두 수의 최소 공배수를 주기로 $x$와 $y$가 반복됨. 완전 탐색으로 모든 수를 탐색할 경우 int 타입의 최댓값은 약 20억이므로 시간 초과. $x$, $y$ 중 하나를 기준으로 최소 공배수까지 탐색. 3. 문제 해결 1. $M$과 $N$의 최대 공..
-
백준 5014 : 스타트링크백준 2023. 11. 27. 14:58
1. 문제 : https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 문제 접근 각각의 위치를 노드라고 생각한다면 그래프로 표현할 수 있음 -> 그래프 탐색 적어도 몇 번 눌러야하는가 -> 최소한 몇 번 눌러야하는가 -> 최단 거리 탐색 -> BFS 3. 문제 해결 중복 노드 방문을 방지하기 위한 벡터 초기화 시작 노드부터 BFS 탐색 노드에서 다른 노드로 이어지는 간선은 총 2개 위로 몇 층 이동할 수 있는지에 대한 U 아래로 몇 층 이동할 수 있는지에 대..
-
백준 2667 : 단지 번호 붙이기백준 2023. 11. 20. 19:05
1. 문제 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2. 문제 접근 2차원 배열이 주어지고 이를 조건에 따라 탐색. -> DFS나 BFS를 사용하여 그래프를 탐색 3. 문제 해결 주어진 단지 정보를 순차적으로 탐색. $(i, j)$ 노드가 아파트가 존재한다면 BFS나 DFS 탐색 시작. $(i, j)$ 노드가 이미 방문한 노드라면 탐색하지 않음. 노드의 갯수를 차례대로 저장하여 마지막에 정렬 후 반환. 4. 코드 #include #in..
-
백준 2468 : 안전 영역백준 2023. 11. 16. 17:28
1. 문제 : https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 2. 문제 접근 장마로 인한 물의 높이가 얼마인지 주어지지 않았으며, 안전지대의 개수는 지역의 높이에 따라 규칙 없이 달라짐. -> 최소 높이인 $0$부터 지역의 최대 높이인 $100$까지 모두 확인해야 함 -> 완전 탐색 2차원 배열이 주어지고 이를 조건에 따라 탐색. -> DFS나 BFS 사용 3. 문제 해결 높이 $h$를 $0$부터 $100$까지 설정하고 안전 지대 개수를 확인 주어진..
-
백준 2178 : 미로 탐색백준 2023. 11. 14. 17:20
1. 문제 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 2. 문제 접근 2차원 배열이 주어지고 목표 지점까지의 경로 탐색 -> 그래프 탐색 최단거리, 즉 그래프 탐색 시 가장 짧은 Depth를 반환해야 함 -> BFS 3. 문제 해결 중복 노드 탐색을 방지하기 위해 노드 방문 여부를 저장하는 2차원 배열 초기화 시작 노드부터 상, 하, 좌, 우로 이동하며 방문 가능한 노드일 경우 BFS에 노드 추가 목표 지점에 도달했을 경우 해당 노드의 Depth를 반환 4. 코드 #..
-
백준 1946 : 신입 사원백준 2023. 11. 12. 18:00
1. 문제 : https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 2. 문제 접근 완전 탐색 : 모든 지원자의 점수를 비교해야하므로 $N^2$ -> 최악의 경우 십만 * 십만 = 백억번의 계산이 필요. -> Time Limit 정렬 : 두 점수 중 하나를 오름차순으로 정렬한다면 나머지 하나의 최솟값을 갱신해가며 합격한 지원자인지 판단하면 된다. 정렬의 경우 $N\log{N}$이고 이후 배열을 탐색하는 로직은 $N$, 즉, 전체..
-
백준 1932 : 정수 삼각형백준 2023. 11. 11. 16:54
1. 문제 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 2. 문제 접근 완전 탐색 : 주어진 이진 트리의 높이는 $N$이고 경로의 수는 $2^{N-1}$이므로 모든 노드를 탐색한다면 시간이든 메모리든 모두 초과하게 된다. DP : 방문했던 노드를 중복해서 계속 방문하기 때문에 중복되는 Sub-Tree가 너무 많아 불필요한 계산을 하게 된다. 방문한 노드까지의 값을 미리 저장한다면 중복 방문하는 노드를 제거하여 많은 메모리와 시간을 아낄 수 있다. (메모이제이션) 3. 문제 해결 모든 노드까지의 경로 합을 0으..
-
백준 1931 : 회의실 배정백준 2023. 11. 10. 20:04
1. 문제 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 2. 문제 접근 회의실을 사용할 수 있는 회의의 최대 갯수를 찾아야 한다. -> 스케줄링 문제 회의실은 한 개만 존재한다 -> 여러 개의 스케줄 중 하나의 스케줄만 활성화가 된다. -> Activity Selection Problem 3. 문제 해결 회의가 끝나는 시간을 기준으로 정렬한다. 끝나는 시간이 같다면 시작하는 시간을 기준으로 정렬한다. 정렬된 배열을 순차적으로 탐색하면서 시간이 겹치지 않는 회의를 찾아낸다. 4. 코드 #include #include #include using namesp..