Door

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

https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 전형적인 백트레킹 문제입니다. 이 문제는 모든 종이를 다 돌면서 종이를 크기에 따라 다 붙어야하기 때문에 종이의 모든 칸을 다 봐야합니다. 그래서 이 문제는 탐색과 백트래킹 두 가지를 해주면 되는 문제입니다. 탐색형 백트레킹은 처음이어서 이 문제를 처음 풀었을 때 많이 당황하기도 했었네요. #백준 17136번 room=[list(map(int,input().split())) for _ i..

알고리즘 공부 2022. 9. 22. 20:58

https://www.acmicpc.net/problem/15806 15806번: 영우의 기숙사 청소 통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검 www.acmicpc.net 이 문제는 무식하게?풀면 바로 시간초과가 뜹니다. 제가 처음풀었던 풀이입니다. #백준 15806번 영우의 기숙사청소 N,M,K,t=map(int,input().split()) dir=[(-2,-1),(-2,1),(-1,2),(-1,-2),(1,-2),(1,2),(2,-1),(2,1)] virus=[] check=[] for _ in range(M): a,b=map(int,input().spl..

알고리즘 공부 2022. 9. 22. 14:41