본문 바로가기

알고리즘40

백준 2146번 다리 만들기 1. 2146번 다리 만들기 1-1. 링크 1-2. 문제 해석 1-3. 코드 및 해설 1. 2146번 다리 만들기 1-1. 링크 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1-2. 문제 해석 섬에서 섬을 잇는 다리를 1개 놓는다고 했을 때 가장 짧은 다리의 길이를 구하는 문제이다. 위 예시에서 색칠된 부분이 섬이고 색칠되지 않은 부분이 바다라고 보면 된다. 위 예시에서는 깃발 사이에 다리를 건설했을 때 가장 짧은 길이의 다리를 만들 수 있다. 위 사진은 위쪽 깃발 위치를 기준으로 다리를 건설했을 때 길이가 얼.. 2021. 12. 15.
백준 1697번 숨바꼭질 1. 1697번 숨바꼭질 1-1. 링크 1-2. 문제 해석 1-3. 코드 및 해설 1. 1697번 숨바꼭질 1-1. 링크 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1-2. 문제 해석 BFS 문제인데 2차원이 아니라 그냥 x좌표만 있는 문제라고 보면 된다. 움직일 수 있는 방법이 -1, +1, *2 이렇게 3가지가 있다. 수빈이와 동생이 0과 100,000에도 서있을 수 있다는 점에 유의하자. 이 2가지만 신경 쓰면 쉽게 풀 수 있는 문제이다. 나는 두 번째 유의점을 신경 못써.. 2021. 12. 8.
백준 7576번 토마토, 7569번 토마토(3차원 버전) 1. 7576번 토마토 1-1. 링크 1-2. 문제 해석 1-3. 코드 및 해설 2. 7569번 토마토 1-1. 링크 1-2. 문제 해석 1-3. 코드 및 해설 1. 7576번 토마토 1-1. 링크 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1-2. 문제 해석 처음에는 "음? 이거 뭐 특별한 로직없이 삼중 포문 쓰면 풀리지 않나?"라고 생각했다. 모든 칸들을 반복문으로 돌면서 상하좌우로 퍼지게하고... 하루가 지날 때마다 다 채워졌는지 체크하면 될 거라고 생각했는데 답은 잘 나오지만 시간.. 2021. 12. 7.
Codeforces Round #690 (Div. 3) - A, B, C 3솔 1. A (Favorite Sequence) 1-1. 링크 1-2. 문제 해석 1-3. 코드 및 해설 2. B (Last Year's Substring) 1-1. 링크 1-2. 문제 해석 1-3. 코드 및 해설 3. C (Unique Number) 1-1. 링크 1-2. 문제 해석 1-3. 코드 및 해설 4. 반성의 시간 1. A (Favorite Sequence) 1-1. 링크 Problem - A - Codeforces codeforces.com 1-2. 문제 해석 숫자들이 담긴 배열이 주어진다. 예를 들어서 a = [1, 2, 3, 4, 5, 6]이라고 해보자. 이걸 앞에서부터 차례대로 옮겨적을건데 앞서 적은 숫자와 가장 멀리 배치되도록 적을 것이다. 1 예를 들어서 1을 옮겨 적었다고 치자 1 2.. 2021. 12. 6.
1953번 - 탈주범 검거 1. 문제 1-1. 링크 1-2. 문제 해석 2. 코드 3. 실행시간 1. 문제 1-1. 링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1-2. 문제 해석 전형적인 BFS 문제이다. 기준점으로부터 1씩 이동하면서 방문했던 곳을 체크하며 카운트를 하면 된다. 근데 나는... 아직도 BFS보단 DFS가 편해서 DFS로 풀었다. DFS로 풀려면 방문했던 곳을 체크하는 거로 문제를 풀 수 없다. 한 번 방문했던 곳보다 더 빠른 루트가 있을 수 있기 때문이다. 예를 들어 DFS로 파란색 루트를 먼저 탐색했다고 치자. 주황색 루트로 탐색하면 더 빠르게 도착하고, 주어진 시간 내에 더 먼 거리까지 도달할 수 있을 텐.. 2021. 9. 13.