본문 바로가기

백준25

[BOJ]2193: 이친수 - Swift/DP 문제https://www.acmicpc.net/problem/2193풀이문제에서 명시적으로 두 가지 조건을 제공해준다.0으로 시작하지 않는다.1이 연속되지 않는다.이진수라는 조건도 있으므로, 3가지 조건이 있다고 볼 수 있다.케이스를 몇개 써보면 쉽게 DP로 풀 수 있는걸 알 수 있다.dp[1] = 1 // 1dp[2] = 1 // 10dp[3] = 2 // 100, 101dp[4] = 3 // 1000, 1001, 1010 2번째 조건 때문에, 0으로 끝나는 경우에는 1을 붙일 수 있지만, 1로 끝나는 경우에는 0으로 붙일 수 없는 것을 알 수 있다.DP 테이블을 다음과 같이 정의하자.dp[i][j]: 자리수가 i인 이진수 중 마지막 자리수가 j인 이친수의 개수따라서 점화식은 다음과 같이 된다.dp[i.. 2025. 4. 30.
[BOJ]12852: 1로 만들기 2 - Swift/DP 문제https://www.acmicpc.net/problem/12852풀이DP를 사용해서 해결했다.문제를 거꾸로 뒤집어보자. n에서 1을 가는 최단거리가 아니라, 1에서 n으로 가는 최단거리로 바꾸는 편이 편하다.이렇게 뒤집으면 개별 숫자에서 다른 숫자로 갈 수 있는 방법은 3가지가 주어진다.1 더하기2 곱하기3 곱하기쉽게 점화식을 만들 수 있다.`dp[i] = max(dp[i - 1], dp[i / 2], dp[i / 3]) + 1` 하지만 경로도 트래킹 해야 하는데, 이건 각 개별 숫자에 도달하기 전에 어떤 수에서 왔는지를 저장하는 배열 하나를 만들고, 최종적으로 이 배열을 루프로 순회하거나, 재귀를 통해서 경로를 얻어낼 수 있다.코드func trackPath(_ startNode: Int) { .. 2025. 4. 30.
[백준]BOJ 13144: List of Unique Numbers - Swift/Two Pointer 13144번: List of Unique Numbers (acmicpc.net) 문제풀이매우 특이한 유형의 투 포인터 문제다. start, end가 증가만 해서는 모든 경우의 수를 나타낼 수 없으며, 모든 경우의 수를 탐색하려면 O(n^2)이 된다. 1 2 3 1 2 라는 수열이 있을 때를 생각해보자그러면 겹치지 원소가 나오지 않도록 작성한 일반적인 투 포인터는 1, 12, 123, 231, 312 이렇게 5번 탐색을 하고 종료한다. 하지만 1 2 3 1 2의 정답은 5가 아니라 15이다. 하지만 이 5번의 탐색만으로도 15라는 결과를 얻을 수 있는데, 우리는 정확한 부분 수열의 형태보다 경우의 수만 알면 되기 때문이다. 다음은 15라는 정답을 유도하는 과정을 시각적으로 나타낸 것이다: "1"1 "12".. 2024. 6. 12.
[백준]BOJ 4179: 불! - Python/BFS https://www.acmicpc.net/problem/4179 문제풀이지훈이가 움직이고, 불을 퍼뜨리면 된다. 순서대로 진행하면 되는데 주의해야 할 점이 두 가지 있다.1. 1분마다 기준으로 번갈아서 움직여야 한다.2. 지훈이가 움직이기 전에 불에 타면 안된다.코드from collections import dequedef bfs(jihun, fires): is_jihun_Visited = [[-1] * c for _ in range(r)] fire_queue = deque() jihun_queue = deque() fire_queue.append(fires) jihun_queue.append([jihun]) is_jihun_Visited[jihun[0]][jih.. 2024. 6. 10.
[백준]BOJ 7490: 0 만들기 - Swift/DFS https://www.acmicpc.net/problem/7490 문제풀이DFS 문제이다. 3가지 연산자 (" ", "+", "-")를 배치하는 모든 경우의 수를 수식으로 만든 후 계산하면 된다.코드import Foundationfunc calcuate() { var rawExpression = "" for idx in 0.. 2024. 6. 10.
[백준]BOJ 2668: 숫자고르기 - C++/DFS 2668번: 숫자고르기 (acmicpc.net) 문제풀이문제를 간단하게 표현하면 그래프 내의 사이클을 모두 찾은 다음에, 사이클에 포함되는 노드을 모두 출력하면 된다. 사이클을 찾으려면 그래프내의 모든 노드에서 dfs를 쓰면 되는데 다음과 같은 케이스들로 나눌 수 있겠다. 1. 사이클에 도달하긴 하나 시작 노드는 사이클에 포함되지 않는 케이스 주어진 예제에서 2번, 4번, 6번, 7번 노드가 해당한다.탐색을 시작한 노드에서 사이클에 도달하긴 하나, 시작한 노드는 사이클에 포함되지 않는다. 최적화를 위해 이러한 케이스에도 사이클만 따로 분리해 중복되는 연산을 줄일 수 있겠지만, 이 문제의 n이 큰 수가 아니므로, 그냥 아무런 행동도 하지 않는다. 2. 탐색을 시작한 노드가 사이클에 포함되는 케이스예제에서 .. 2024. 6. 4.
[백준]BOJ 14658: 하늘에서 별똥별이 빗발친다 - Python, Brute force 14658번: 하늘에서 별똥별이 빗발친다 (acmicpc.net) 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 문제 풀이 우선 최악의 경우를 생각해보자. N, M이 각각 500,000 이고, L은 1, K가 100일 때가 최악인 경우가 된다. 이 상태에서 모든 경우의 수를 확인하려면 별의 위치를 250,000,000,000,000번 확인해야 한다. 따라서 모든 경우의 수를 판단하는건 불가능 하다. 따라서 트램펄린을 설치할 위치를 합.. 2024. 4. 7.
[백준]BOJ 10159: 저울 - Python, Floyd-Warshall 10159번: 저울 (acmicpc.net) 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 문제 풀이 노드간의 연결 여부를 따지는 따지는 문제이므로 처음에는 단순히 Union-Find Set을 사용하면 될 줄 알았다. 하지만 물건 A와 B의 관계가 있을 때 가능한 경우의 수는 'A가 B보다 무겁다' 혹은 'B가 A보다 무겁다' 두 가지의 경우가 있으므로 방향 그래프가 된다. 따라서 Union-Find Set을 사용하는 것 보다는 방향 그래프에서도 적용 가능한 알고리즘을 사용해야 한다... 2024. 4. 7.
[백준]BOJ 17298 - 오큰수 - Swift & C++/Stack https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 풀이 스택을 이용하는 문제이다. 2493번 문제와 사실상 같은 문제인데, 배열이 뒤집혀 있다는 것과 인덱스가 아닌 해당 인덱스에 대응하는 값을 사용하는 것이 다르다. 코드 Swift import Foundation let n = Int(readLine()!)! let a = Array(readLine()!.split(separator: " ").map { Int(String($0))! }.reverse.. 2023. 7. 10.

티스토리툴바