Door

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

https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 이 문제는 처음 마주하면 '어라?쉬운데?'하다가 제출하는 순간 ???이게 뭐지?? 하게 되는 문제. 이 문제에서 대부분의 사람이라면 '각 사람들까지 거리합이 최소'라는 말에 유의합니다. 그래서 최소지점을 '(현재 마을위치-지금 마을위치)x(지금마을 인구)' 이렇게 거리를 구한 뒤 이게 최소가 되는 지점을 찾을 것입니..

알고리즘 공부 2022. 9. 20. 17:42

https://www.acmicpc.net/problem/18224 18224번: 미로에 갇힌 건우 건우가 가장 빨리 탈출할 수 있는 날이 몇번째 날인지, 그리고 낮이면 "sun", 밤이면 "moon"을 공백으로 구분하여 함께 출력한다. 예를 들어, 2번째 날 밤일 경우, "2 moon" 을 출력하고, 3번째 날 낮 www.acmicpc.net bfs문제 중에서 '조건'이 정말 까다롭게 붙은 유형. 이 문제를 봤을 때 가장 어려운 부분은 'm만큼 이동하면 낮과 밤이 바뀐다'라는 부분. 문제를 잘 읽어보면 이동하는 순간에 바뀝니다. 예를들며 m=2인데 낮 1 이라면 이동하는 순간 2가 되어서 밤 0으로 바뀌는 것. 사실 여기까지만 알면 문제가 안풀립니다. 게시판의 반례에 계속 넣어보는데 문제가 안풀렸습니다..

알고리즘 공부 2022. 9. 19. 17:44

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 이 문제는 까다로운 지점이 많습니다. 우선, 그림으로 이 문제에서 봐야할 걸 보겠습니다. 바로 방문한 곳을 다시 갈 수 있는 점입니다. 조건에 불켜진 곳만 방문할 수 있다고 적혀있습니다. 그래서 처음에는 가지 못하는 곳이 다른 곳을 방문하면서 스위치를 키면 방문이 가능해집니다. 그런데 bfs를 구현하다보면 '한번 방문한 곳은 다시 방문하지 않는..

알고리즘 공부 2022. 9. 19. 14:20