Problem Solving43 [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. [Programmers] Lv.2 순위 검색 - Swift/Hash Table, Binary Search https://school.programmers.co.kr/learn/courses/30/lessons/72412 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이많이 해맨 문제다. 처음에는 다음과 같이 알고리즘을 생각했다.1. 일단 쿼리의 개수와 info 배열의 크기를 생각해보면 filter를 사용하는 문제는 아님2. 바이너리 서치, Upper bound와 Lower bound의 차이가 해당하는 원소의 개수가 같음3. info 배열을 잘 정렬해서 바이너리 서치만 하면 쉽게 해결될 문제 하지만 조금만 생각해보면 이러한 방식의 알고리즘은 문제를 절대로 해결할 수 없다.우선 쿼리의 조건들이 독립적이다. .. 2025. 1. 7. [백준]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 14179: 빗물 - C++/Stack 14719번: 빗물 (acmicpc.net) 문제풀이스택 문제이다. 빗물은 양 옆이 블록으로 막혀있을 때, 낮은 블록의 높이를 기준으로 그 사이에 빗물이 고이게 된다. 따라서 스택을 하나 만들고 인덱스 순서대로 입력받은 다음에, "현재까지" 가장 높게 쌓여있던 블록의 높이(currentMax)와 같거나 더 높게 쌓여있는 블록이 스택에 들어오려 할 때, 스택에 쌓여있는 모든 블록들을 빼내면서 고여있는 물의 양을 더하면 된다(currentMax - 중간 블록의 높이). 하지만 이러한 방법을 쓰면 문제점이 하나 있는데, 블록이 계속 커진다는 보장이 없기 때문에, 마지막에 있는 블록들이 붕 뜨게 된다. 이 때는 스택을 뒤집어서 해결하면 된다. 현재 currentMax보다 더 큰 수가 앞에 존재하지 않는다면 뒤집.. 2024. 5. 28. [백준]BOJ 17266: 어두운 굴다리 - Swift 17266번: 어두운 굴다리 (acmicpc.net)문제풀이가로등 간의 최대 간격을 찾으면 되는 문제이다. 일반적인 가로등 간의 간격과, 시작점과 첫 가로등의 간격, 도착점과 마지막 가로등의 간격을 알아내면 된다.가로등 사이의 간격은 양 사이드 모두가 가로등이기 때문에 간격에서 2를 나눠줄 필요가 있다. 이 문제에는 작은 함정이 하나 있는데, 가로등 사이의 간격이 만약 홀수인 경우에는 2로 나눴을 때 0.5가 내림 되기 때문에 주의해야 한다. 코드import Foundationlet n = Int(readLine()!)!let m = Int(readLine()!)!let x = readLine()!.split(separator: " ").map { Int($0)! }var answer = max(x.fi.. 2024. 5. 6. 이전 1 2 3 4 5 다음
