Door

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 약 2주정도 고민했으나 도저히 안풀려서 결국 구글링을 했습니다. 제가 처음 잡았던 아이디어와 가장 유사한 것을 기준으로 코드를 참고했습니다. 우선, 그림으로 그려본 것입니다. 참고로 문제에서 주어진 트리는 이진트리가 아니지만 이해를 돕기 위해 이진트리로 그렸습니다. 저는 맨 위의 부모트리에서 아래로 차근차근 내려가는 방식을 구했습니다. 편의상 왼쪽 오른쪽 경로를 나눴는데, 이건..

알고리즘 공부 2022. 7. 18. 15:47

https://www.acmicpc.net/problem/11509 11509번: 풍선 맞추기 첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다. www.acmicpc.net 이 문제는 어떻게하면 화살을 적게 쓰고 풍선을 다 터트릴 수 있는가를 묻고 있습니다. 이 문제는 정렬을 절대 쓰면 안 됩니다. 화살의 조건을 보면 정렬을 잘못쓰면 문제의 상당부분이 틀어저버리죠. 정답 코드에 앞서, 제가 처음 풀었던 오답코드를 보겠습니다. #백준 11509번 풍선 맞추기 N=int(input()) ballons=list(map(int,input().split())) answer=1 now=ballons[0] for i in range..

알고리즘 공부 2022. 7. 17. 17:27

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/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 이 문제는 쉬운 bfs문제처럼 보이지만 '벽이 움직인다'라는 까다로운 조건이 붙어서 애를 많이 먹었습니다. 저는 처음에 while wall: wx,wy=wall.pop(0) nwx=wx+1 if nwx>=8: continue else: if [nwx,wy] in man: p=man.index([nwx,wy]) man.pop(p) room[nwx][wy]='#' new_wall.appen..

알고리즘 공부 2022. 7. 1. 15:52

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/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 2022.06.22 - [알고리즘 공부] - [백준 7576] 토마토(파이썬) [백준 7576] 토마토(파이썬) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다... d..

알고리즘 공부 2022. 6. 30. 13:54

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