Door

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 상당히 까다로웠던 dp문제. DP+길찾기가 합쳐져서 어려웠습니다. #백준 1520번 내리막길 #시간초과 코드 from collections import deque dx=[0,0,1,-1] dy=[1,-1,0,0] N,M=map(int,input().split()) room=[list(map(int,input().split())) for _ in range(N)] dp=[[0]*M for _ in ran..

알고리즘 공부 2022. 9. 29. 11:05

https://www.acmicpc.net/problem/22955 22955번: 고양이 도도의 탈출기 첫째 줄에 방의 높이 $N$ ($ 2 \leq N \leq 1\,000$)과 방의 너비 $M$ ($ 2 \leq M \leq 1\,000$)이 주어진다. 둘째 줄부터 $N$개의 줄에 공간의 상태가 주어진다. 공간의 상태는 $C$, $D$, $E$, $F$, $L$, $X$로 이루 www.acmicpc.net 구현+다익스트라가 합쳐진 독특한 구조. 다익스트라를 써서 가장 적은 체력으로 목적지에 도착하는 경우를 구합니다. 쌩구현이라 시간이 좀 걸리지만 크게 로직이 어려운 건 없었습니다. 주의할 점은 X에서 내려갈때, 바닥이나 문을 만나는 경우 이외에도 사다리를 만날 수 있다는 점입니다. 또, 사다리가 연속..

알고리즘 공부 2022. 9. 28. 18:29

https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 처음 문제를 마주하고 조금 까다롭다고 생각한 문제. 그래도 일반적인 bfs라 생각하고 문제를 풀이했습니다. #백준 9328 열쇠 from collections import deque dx=[0,0,1,-1] dy=[1,-1,0,0] T=int(input()) def bfs(sx,sy): global answer global key global visited q=deque() q.append((sx,sy)) v..

알고리즘 공부 2022. 9. 28. 10:10

https://www.acmicpc.net/problem/5022 5022번: 연결 A1과 A2, 그리고 B1과 B2를 연결하는데 필요한 전선의 길이의 최솟값을 출력한다. 만약, 불가능한 경우에는 "IMPOSSIBLE"을 출력한다. www.acmicpc.net 예전에 이 문제를 접하고 예시코드까지 보고도 뭔소리인지 몰라서 접었는데 다시 보니 풀이방법이 보였습니다. 이 문제는 bfs문제인데 좀 특이합니다. bfs를 총 2번 해야하며, 이전 bfs로 지나간 곳은 지나갈 수 없습니다. '그럼 bfs2번만 해주면 되는 쉬운 문제네요' 라고 생각하실 수 있겠지만 bfs특성상 모든 지역을 다 탐색할 수 있습니다. 아무리 heaq로 구해도 이미 거의 대부분 지역을 탐색한 뒤라서 다음 bfs에서 이상하게 됩니다. 그래..

알고리즘 공부 2022. 9. 27. 11:51

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl&categoryId=AV597vbqAH0DFAVl&categoryType=CODE&problemTitle=SW&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2&&&&&&&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 일반적으로 deque를 써서 이동하면 되는 문제가 아니라 알고리즘을 구성하는데 애를 많이 먹었습니다. 가장 어려웠던 부분은 '군집이..

알고리즘 공부 2022. 9. 26. 10:56

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE&problemTitle=SW&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2&&&&&&&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 어떻게하면 가장 적은 비용으로 구할지 계산하는 문제. 저는 이 문제같은 경우에는 dfs를 활용해서 풀었습니다. #삼성sw 1952 ..

알고리즘 공부 2022. 9. 24. 17:12

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com bfs를 써서 등산로를 구하는 문제. 단, 조건이 좀 많이 붙었습니다. 1. 이전의 지나갔던 곳은 방문하면 안된다 -->'bfs구현하면 당연한 소리인데요' 이런 케이스가 있습니다. 이 문제에서 주의할 점은 산을 깍고나서 다시 돌아가는 케이스입니다. 일반적인 bfs로 구현하면 이 부분을 놓치기 쉽습니다. 저는 q안에 집합을 넣으면서 지나갔던 곳을 계속 넣어줬습니다. 2. 최대 K만큼 깍을 수 있다했지 꼭 K만큼 깍으라고는 안했다 -->최대 K라고 했..

알고리즘 공부 2022. 9. 23. 22:01

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4suNtaXFEDFAUf SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com (무단복제 이슈가 있어서 문제 일부만 캡쳐했습니다.) core가 주어지고 core를 격자밖까지 이을 수 있다면 해결할 수 있는 문제. 이 문제를 보면 자연스럽게 백트레킹이 떠오릅니다. 예를들면 1번 core를 위쪽으로 연결했다면 2번 core는 좌로는 연결이 되지 않는 식이 발생할 수 있으니 1core 상->2core 하 ->3core 좌 -->2core 상 -->3core 우 이런식으로 모든 케이..

알고리즘 공부 2022. 9. 23. 11:43