분류 전체보기113 [백준]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. [백준]BOJ 14891: 톱니바퀴 - Python 14891번: 톱니바퀴 (acmicpc.net) 14891번: 톱니바퀴첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터www.acmicpc.net문제위 링크 참조풀이설명이 불친절하고 매우 비직관적이므로 문제를 잘 읽어야 한다. 딱히 필요로 하는 알고리즘은 없고, 구현 능력 자체도 크게 요구하지 않는다. 그냥 문제를 이해하는것 자체가 이 문제의 가장 큰 난관이지만, 그렇다고 국어문제도 아닌게 애초에 문제가 말이 안된다. 이 문제에서 톱니바퀴는 절대로 현실의 톱니바퀴처럼 움직이지 않는다. 이전 톱니바퀴가 회전하면 다음 톱니바퀴도 회전해야할지 말아야 할지를 이미 .. 2024. 4. 19. [백준]BOJ 14890: 경사로 - Python/구현 14890번: 경사로 (acmicpc.net) 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 길어서 생략, 위 링크 참조 풀이 경사로의 방향을 생각해보면 왼쪽에서 오른쪽으로 올라가는 방향이 있을 것이고, 그 반대인 오른쪽에서 왼쪽으로 올라가는 방향도 있을 것이다. 이러한 경우에는 한 번에 해결하기 보다는 배열을 정방향, 역방향으로 각각 순회하여 경사로를 만들어주는 것이 좋다. 따라서 알고리즘은 다음과 같다. 1. 주어진 2차원 배열을 Transpose한 배열을 하나 더 만든다. 세로 모양의 길을 찾기 위해서이다. 2. 정방향으.. 2024. 4. 19. [백준]BOJ 14499: 주사위 굴리기 - Python 14499번: 주사위 굴리기 (acmicpc.net) 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제 풀이 특별한 알고리즘이나 문제 해결 기법을 사용할 필요 없이, 순수하게 딕셔너리 자료구조만을 사용해서 풀 수 있는 문제이다. 주어진 주사위의 전개도를 이용하여 각 면에 숫자를 붙이고(면에 써져있는 숫자가 아닌 각 면을 인식하게 해주는 숫자, 이하 ID숫자라고 하겠다.) 이를 방향: ID 숫자의 꼴로 딕셔너리를 생성한다. 또 ID숫자: 면에 .. 2024. 4. 15. [백준]BOJ 12100: 2048 (Easy) - Swift/DFS https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 위 링크 참조 (길어서 생략) 풀이 최대 20 * 20 크기의 보드에서 2048 게임을 하는 것이다. 최대 5번의 이동만 한다고 문제에 주어져 있으므로, 모든 경우를 탐색하여 문제를 풀 수 있다. 이 문제에서 주의해야할 점은 다음과 같다. 1. 이동하는 방향에서 가까운 숫자부터 이동해야한다. -> 당연하지만 먼 숫자부터 이동한다면 앞에 있는 숫자들 때문에 이동이 .. 2024. 4. 14. 이전 1 2 3 4 5 ··· 13 다음
