Door

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

https://www.acmicpc.net/problem/2026 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 문제에서 설정이 누락된 게 있습니다. '모두 친구'여야한다는 조건. 이 문제를 잘못읽으면 a-b b-c c-d 이렇게만 이어져있으면 소풍조라고 생각하기 쉽습니다. 하지만 이 문제가 요구하는 건 abcd이렇게 소풍조라면 a-c a-d b-d 이 관계도 있어야 한다는 말. 서로 건너건너 아는 것이 아니라 모두 친구여야한다는 말이 빠져있어서 저도 몇 번 헤매다가 구글링을 통해 조건을 파악했습니다. #백준 2..

알고리즘 공부 2022. 9. 21. 20:27

https://www.acmicpc.net/problem/18500 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 2022.08.18 - [알고리즘 공부] - [백준 2933번] 미네랄(파이썬) [백준 2933번] 미네랄(파이썬) https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸 door-of-tabris.tistory.com 위의 문제와..

알고리즘 공부 2022. 9. 21. 11:22

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 그리디 문제입니다. 만약에 날짜가 겹친다면 가격을 더 쌘데 부르는 곳을 가야합니다. 이 문제는 우선순위 큐로 풀 수 있었습니다. q에 페이를 넣어주되 현재 날짜가 q보다 크면 q의 가장 작은 값을 pop해줍니다. 예를들면 1 20 1 100 이렇게 들어왔다고 치면 1 100을 넣으면 q가 20 100 이렇게 2개가 됩니다. 그런데 day==1이므로 q의 길이가 ..

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