Door

https://www.acmicpc.net/problem/1548 1548번: 부분 삼각 수열 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 www.acmicpc.net 이 문제는 처음 문제를 읽다가 이게 뭔소리야? 하면서 이해를 못했던 문제. 1번 예시에서 최대길이를 2라고 출력했습니다. 어라? 삼각수열은 분명 3개가 들어가야하니깐 최소 3이 되어야할텐데. 이게 뭐지? 구글링해서 뒤지다가 배열이 2보다 큰데 삼각수열이 0이라면 저렇게 받아도 되는 걸 알게되었습니다. 이 문제에서 오랫동안 헤..

알고리즘 공부 2022. 7. 8. 16:41

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/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