Door

https://www.acmicpc.net/problem/20926 20926번: 얼음 미로 탐험가 테라는 얼음 미로에 갇혔다. 얼음 미로의 바닥은 빙판으로 되어 있어 발을 내디디면 바위에 부딪힐 때까지 미끄러진다. 예를 들어, 위 그림에서 테라가 왼쪽 방향으로 이동한다면 중간에 www.acmicpc.net 이 문제는 가중치가 있기 때문에 다익스트라를 쓰면 좋습니다. 다만, 이 문제는 일반적인 BFS,DFS와 다른 점이 있습니다. 바로 '한번에 쭉 간다'라는 것. 테라는 미끄러지면서 이동합니다. 상하좌우로 미끄러질 수 있는데 돌이나 출구를 만나기 전까지 미끄러집니다. 만약 범위를 벗어나거나 구멍을 만나면 아웃이고요. 그래서 한번에 쭉~~~미끄러진다는 걸 구현만 한다면 이 문제는 상대적으로 무난한게 풀 수..

알고리즘 공부 2022. 8. 25. 17:25

https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 이 문제는 풀이방법은 단순할 수 있지만 어떻게하면 반복문을 줄일 수 있는가에 대해서 생각해보면 좋은 문제입니다. 우선, 아래는 제가 처음 이 문제를 보자마자 바로 떠올린 코드입니다. #백준 10775번 공항 G=int(input()) P=int(input()) gate=[i for i in range(1,G+1)] g_in=[False]*(G+1) planes=[..

알고리즘 공부 2022. 8. 24. 15:28

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 처음 이 문제를 만났을 때에는 '이게 골드2? 이거 골드 5수준이잖아?' 하면서 쉽게 생각했습니다. 그리고 제출하자마자 시간초과. 제가 생각한 방식은 간단했습니다. '지도돌다가 1만나면 거기서 bfs해준다' 이렇게 하면 예제는 통과하지만 시간초과가 납니다. 그리고 시간초과가 뜰 때 내가 뭘 생각하지 못하는구나 깨닫고 힌트를 얻어봤습니다. https://ku-hug.tistor..

알고리즘 공부 2022. 8. 22. 12:02

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이 문제는 알고리즘로직보다도 시간초과,메모리 초과와의 싸움을 해야하는게 무척이나 힘들었습니다. 이런 경로를 찾는 알고리즘은 다익스트라 알고리즘을 쓰면 쉽게 풀립니다. https://justkode.kr/algorithm/python-dijkstra Python으로 다익스트라(dijkstra) 알고리즘 구현하기 최단 경로 알고리즘은 지하철 노선도, 네비게이션 등 다방..

알고리즘 공부 2022. 8. 21. 19:10

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 이 문제는 BFS로 외부 공기를 계속 구해주면서 치즈를 제거하는 문제입니다. 2022.06.30 - [알고리즘 공부] - [백준 2573번] 빙산(파이썬) [백준 2573번] 빙산(파이썬) https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진..

알고리즘 공부 2022. 8. 21. 11:52

https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 처음 이 문제를 보고 '와 개 쉽네' 라고 신나게 구현했다가 예제를 통과하지 못했습니다. 처음에는 dfs로 한칸씩 이동하다가 3칸째 이동했을때 여태까지 이동한 칸 합의 최대를 구하는 줄 알았습니다. 그런데...얼라라? 부메랑을 만든 것의 총합?? x된 칸에 부메랑을 넣는다가정하면 저렇게 1,2,3의 케이스가 있습니다. 저렇게 채우면 더이상 채울 수 없으니 그때의 합을 구합니다. ..

알고리즘 공부 2022. 8. 19. 14:01

https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 이 문제에서 구현할 건 크게 두 가지. 1. 막대기로 미네랄 깨기 2. 클러스터 내리기 여기서 2가 상당히 복잡합니다. 여기서 클러스터라는 게 빡셉니다. 문제를 잘 읽어보면 클러스터는 한 덩어리입니다. 그래서 미네랄 하나만 내리는 것과 비교하면 많이 복잡한 편입니다. 그림으로 예시를 구현해봤습니다. 저렇게 한 덩이가 그대로 내려와야합니다. 그리고 저 내려오는 걸 구현하는 게 상당히 난해했습니다. https://..

알고리즘 공부 2022. 8. 18. 12:27

https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 이 문제는 유사한 연구소1,연구소3 등의 문제를 예전에 풀어본 적이 있어서 체감적으로 쉬웠습니다. 구현할 건 2가지. 1. 어떤 지점에서 바이러스를 처음 둘 것인가 2. 바이러스를 어떻게 퍼트리고 최댓값을 구할 것인가 1의 경우, 저는 combination을 사용했습니다. 백트레킹도 좋긴한데 저는 이 방식이 가장 간편했습니다. 2의 경우에는 bfs를 사용했습니다. 사전에 visited라는, -1로 되어있는..

알고리즘 공부 2022. 8. 15. 19:36