코딩 검색 결과
271 개의 검색 결과가 있습니다.
코딩/백준 (C++)

백준 4991번: 로봇 청소기 (C++)

접근 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 간단하게 말하자면 트리(그래프)가 아닌 문제를 트리로 만들어서 풀면 쉽게 풀 수 있다. bfs 알고리즘을 이용하여 출발점과 각 쓰레기 위치까지의 이동 거리, 그리고 각 쓰레기 위치에서 다른 쓰레기 위치까지의 거리를 모두 측정하면, 각 쓰레기 위치를 노드로 하고 그 사이의 거리를 간선의 길이로 하는 그래프를 그릴 수 있다. 해당 그래프에서 모든 노드들을 방문하는 최소 간선의 길이를 가지는 경로를 dfs..

2022. 4. 28. 01:32
코딩/백준 (Python)

백준 6087번: 레이저 통신 (Python)

접근 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 처음에는 BFS 알고리즘을 이용하여 visited 배열 (r, c) 에 해당 위치에 도달할 수 있는 최소 거울 수를 저장해가면서 탐색하면 아주 쉽게 풀 수 있을 것이라고 생각했다. 하지만 그 생각이 틀렸다는 것을 알 때까지는 오래 걸리지 않았고, 이후에는 꺾은 수가 적은 경우를 먼저 탐색하는 0 1 BFS 방법을 이용도 해봤지만 잘 되지 않았다. 결론적으로는 BFS 알고리즘을 변형하..

2022. 4. 20. 01:36
코딩/백준 (Python)

백준 9376번: 탈옥 (Python)

접근 https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 처음에는 DFS로 풀고 예시를 맞춘다음 이것을 최적화해보려했지만, 딱봐도 계산이 많아서 어려울 것이라고 생각하고 다른 방법이 떠오르지 않아 다른 블로그의 글을 여러개 참고하여 풀 수 있었다. 설명을 봐도 이해하기가 어려웠던 문제였다. 정리차원에서 말하자면 풀이를 위한 총 3가지의 핵심 개념이 있었다. 각 죄수들을 시작점으로 하는 BFS 를 진행하여 해당 죄수가 특정 위치 (r, c)에 도달했을 때 그 위..

2022. 4. 18. 22:36
코딩/백준 (Python)

백준 2749번: 피보나치 수 3 (Python)

접근 https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net n으로 주어지는 숫자가 매우 큰것을 보고, 이것은 그냥 알고리즘으로 풀 수 없다는 것을 어렴풋 느끼고 무조건 무언가 주기가 있겠구나 하고 접근하기 시작했다. 피보나치 수가 0으로 시작하므로 처음으로 0이 나오는 피보나치 수를 찾아 주기성을 보려고 했는데 틀렸다. N = int(input()) mod = 1000000 fib = [0, 1] i = 2 while 1: fib.append(fib[i - 2] + fib[i - 1]) fib[i] %= mod if fib[i] ..

2022. 4. 16. 16:10
코딩/백준 (Python)

백준 2933번: 미네랄 (Python)

접근 https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net bfs 알고리즘을 이용하여 미네랄의 집합인 클러스터를 확인하는 것을 제외하면 단순 구현 문제였다. 좌우에서 반복해서 돌을 던지며 돌에 의해 부서지는 미네랄을 기준으로 상하좌우를 탐색하여 해당 위치의 클러스터가 공중에 떠있는지 아닌지를 판별하여 문제를 해결할 수 있다. 공중에 떠있다면 해당 클러스터를 한 칸씩 이동하며 바닥 혹은 다른 미네랄에 닿는지를 확인해주게 된다. 코드 import sys from co..

2022. 4. 16. 14:58
코딩/백준 (Python)

백준 3197번: 백조의 호수 (Python, PyPy3)

접근 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제 자체는 쉬워보이지만 시간 안에 들어가기가 굉장히 빡셌던 문제였다. 핵심은 백조와 얼음이 녹는 과정을 매번 bfs 탐색하는 것이 아니라, 처음에는 bfs 탐색을 하지만, 두번째 부터는 얼음이 녹은 부분, 그리고 백조는 백조가 신규로 갈 수 있는 부분만 탐색하는 것이 중요했다. 그러기 위해 백조 큐, 백조 임시 큐, 물 큐, 물 임시 큐 총 4개의 큐를 이용해서..

2022. 4. 15. 01:35
반응형