Door

https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 이 문제를 처음 보고 오만가지 생각을 다 했습니다. 최대 K번만큼 원숭이가 말처럼 움직인다라... 그럼 원숭이가 움직일 때마다 있는 지점에서 상하좌우 이동+말이동 이걸 다 봐야하나? 그럼 K번만큼 움직이는 건 어떻게 구하지?? 시간초과 엄청날텐데... 문제의 접근조차 하지못해서 상당히 애를 먹었다가 이 문제에서 힌트를 얻었습니다. 2022.06.30 - [알고리즘 공부] - [백준..

알고리즘 공부 2022. 7. 6. 15:41

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 이 문제에서 구현해야할 것은 크게 2가지. 1. 지운 노드의 아래 자식 노드 전부 삭제. 2. 자식노드 판별 여부 이 문제를 처음 접할 때는 트리를 전부 구현해서 푸는 건가... 하고 생각이 들었습니다. 그래서 열심히 파이썬에서 트리를 구현한 걸 찾아봤으나 이 문제에 적용하기는 힘들었습니다. 그러다가, 이 문제의 힌트를 얻으면서 차근히 풀었습니다. 1. dfs를 이용해서 자식노드를 지운다. ..

알고리즘 공부 2022. 7. 6. 13:04

https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 www.acmicpc.net 이 문제는 처음 문제를 쓱 읽으면 '뭐야. 문제 개쉬운데?' 라는 착각을 줍니다. 물론 예제를 푸는 정도 수준은 어렵지 않는 코드이지만 그렇게하면 시간초과가 뜰 것입니다. #백준 16932번 모양만들기 from collections import deque N,M=map(int,input().split()) room=[] zero=[] ones=[] for x in range(N): da..

알고리즘 공부 2022. 7. 4. 22:48

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 이 문제는 BFS를 해줄 것이 2가지입니다. 하나는 불이 퍼지는 것. 또 하나는 지훈이의 이동. 이 문제가 조금 애매하게 서술해서 어떤 걸 먼저 BFS해줘야할지 애매해서 질문글을 찾아보니 불을 먼저 BFS해주는 걸로 했습니다. #1. 불이 먼저 번짐 new_fire=deque() for x,y in fire: for d in range(4): nx=x+dx[d] ny=y+dy[d] ..

알고리즘 공부 2022. 7. 2. 17:54

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 이 문제에서 구현해야할 것은 크게 두 가지. 1. 빙산을 녹인다. 2. 빙산의 덩어리를 찾는다. 1. 빙산을 녹인다. 인접한 공간에 0이 있는지 확인하고 0이 있다면 -1 단, 빙산은 0에서 더 이상 뺼 수 없습니다. 이런 류의 문제는 deepcopy를 써주면 좋습니다. 만약 빙산을 받은 리스트에 0을 기준으로 지우다보면 위의 같은 NG케이스가 생깁니다. 원래는 0이 인접한 게 2개였는데 앞..

알고리즘 공부 2022. 6. 30. 15:29

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 전형적인 BFS를 이용한 풀이입니다. 이런 유형의 문제는 풀이방법을 모른다면 체감난이도가 확 올라갈 수 있습니다. 그 이유는 '최소일수'를 구하는 것 때문이죠. 이 문제를 BFS로 푼다, 아니면 하다못해 DFS로 푼다는 것까지는 문제 유형을 읽다보면 생각이 어느정도 납니다. '토마토가 익을 때는 인접한 왼쪽 오른쪽만 익히는 구나. 그럼 토마토가 익는 걸 기점으로 그래프를 이동시키면..

알고리즘 공부 2022. 6. 22. 10:56

https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 이 문제에서 접근해야할 것은 크게 2가지입니다. 1. 배열을 외부만 돌려주는 걸 어떻게 할 것인가. 2. 밖에 큰 거 돌려주고 안에 작은 건 어떻게 돌려줄것인가. 예시 1의 경우로 본 경우. 먼저, 외부의 사격형을 돌려주고 그 다음 안의 사격형을 돌려줘야합니다. 1. 돌려주는 경우. 저는 좌 하 우 상으..

알고리즘 공부 2022. 6. 9. 11:35

https://www.acmicpc.net/problem/22858 22858번: 원상 복구 (small) 수가 적혀있는 $P_1, P_2, ..., P_N$ $N$개의 카드가 있다. 1부터 N까지 수가 하나씩 존재하는 $D_1, D_2, ... , D_i , ... D_N$ 가 있다. 이때 $D_i$는 $P_{D_i}$ 값을 $i$ 번째로 가지고 오는 것을 의미한다. 이러한 www.acmicpc.net 문제를 읽으면 다소 복잡해보일 수 있습니다. 한번 이 문제의 요구를 예시와 함께 보겠습니다. 저는 역으로 구해준다는 걸로 이해했습니다. 예시1의 경우를 살펴보면 섞는 패턴이 4 3 1 2 5입니다. 그럼 K=1일 때는 첫번째 숫자가 4번째로. 두번째 숫자가 3번째로. 세번째 숫자가 1번재로. 네번째 숫자..

알고리즘 공부 2022. 6. 7. 18:38