코딩테스트

[Python] 백준 1654번 - 랜선 자르기

문제: https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 재미있게 푼 문제였다. 문제를 읽으면서 이분탐색을 해서 최대값을 찾아야할지, 그리디로 풀 수 있을지 고민했다. "N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다." 라는 말 때문에 최선의 선택을 하면서 분기점이 넘어가는 순간을 찾으면 되겠다고 생각해서 그리디로 풀어보았다. k, n = map(int, input().split()) cables = [int..

[Python] 백준 5427번 - 불

+) 6/30 추가 오늘 같은 문제를 한번 더 풀어보았다. 혼자 다시 풀어보니 여전이 이해가 안되는 부분이 있었다. 내가 헷갈렸던 부분은, 상근이가 이미 지나온 자리에 대해서는 불이 옮겨붙지 않다도 된다는 것이다. #### #*@. #### 예를 들어 위와 같은 미로가 주어지는 경우, 1초 뒤에는 다음과 같이 변해있어야 한다고 생각했다. #### #**@ #### 하지만 이렇게 변하면, 1초 안에서 불이 먼저 번지고 상근이가 옮겨갈 차례가 될 때 상근이의 위치를 상실하게 된다. 상근이는 출구까지 최단거리로 이동하기 때문에 지나왔던 자리를 다시 지나갈 필요가 없게된다. 즉, 지나왔던 자리에 대해 불이 붙는지 아닌지 코드상에서 알 필요가 없다는 것이다. 결국 어제 짰던 코드를 다시 참고해서 풀었다 .. fr..

[Python] 백준 2583번 - 영역 구하기

문제: https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net BFS나 DFS를 활용해서 푸는 문제이다. 푸는데 크게 어렵지는 않았지만, 예시를 직교좌표계 위에 올려주고 있어서 좌표값을 정하는데 좀 헷갈렸다. 평소에 문제를 풀 때는 왼쪽 위를 (0, 0)으로 주로 잡고 풀었는데, 본 문제는 왼쪽 아래를 (0, 0)으로 잡고있어서 행을 거꾸로 생각해주어야 했다. 종종 직교좌표계 위에 올려 문제를 푸는 경우가 있으니 해당 방식도 연습을..

[Python] 백준 12904번 - A와 B

문제: https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 처음에는 백트래킹을 사용해서 S를 T로 만드는 모든 경우를 다 찾아보려고 했었다. 그런데 시간제한에 걸려서.. 다른사람들이 푼 방식을 참고했다. S를 T로 만들어주는 대신, T가 S가 되는지만 확인해주면 되는 간단한 문제였다! 문제 조건이 S의 마지막에 매번 A나 B를 추가해주기 때문에, T의 가장 마지막 문자만 떼어주며 S가 나올 수 있는지 확인하면 ..

[Python] 백준 2212번 - 센서

문제: https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 그리디 알고리즘을 적용해 문제를 풀었다. 처음에는 집중국을 기준으로 원으로 자료를 수집한다고 생각했는데, 예제를 보면 집중국 기준으로 단방향으로만 수집을 한다는 힌트를 얻을 수 있다. 주어진 센서들을 총 K개(집중국의 개수)만큼 그룹을 지어주면 되는 문제이다. 따라서 센서들 간의 거리를 저장하는 별도의 리스트를 만들어주고, 리스트를 내림차순으로 정렬한다. K개의 그..

[Python] 백준 7562번 - 나이트의 이동

문제: https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 먼저 출발지, 도착지가 주어졌고 이 사이를 최소 몇 번만에 이동할 수 있는지 묻고 있기 때문에 BFS를 사용하면 적절하다는 것을 알 수 있다. 나이트 8방향에 대한 이동 코드는 다음과 같이 주었다. dir = [[1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1], [-2, 1], [-1, 2]] 이를 가지고 BFS를 적용해 풀었다. 이때, 처음에는 ..

[Python] 백준 4179번 - 불!

문제: https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 처음에는 1초마다 불을 번지게 하고, 지훈이가 나갈 루트를 BFS로 찾아 이동시켜주면 되겠다고 생각했다. 내가 생각한 로직은 다음과 같다. - 불의 개수는 1개 이상일 수 있다. - 지훈이가 있는 곳은 다시 '.'으로 바꿔주기 - 1초가 지났을 때, 불을 먼저 퍼트리고 지훈이를 BFS하여 출구로 갈 수 있는지 확인 - BFS가 아니고 DFS로 풀어야할 것 같다. 탈출 루트를..

[Python] 백준 1700번 - 멀티탭 스케줄링

문제: https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net Greedy 알고리즘을 이용해서 풀면 되는 문제다. Edge case짜는게 약하다는걸 많이 느낀 문제였다. 내가 처음 짠 로직은 다음과 같다. 1. 일단 멀티탭 구멍 개수만큼 전자기기를 꽂는다 2. 다음 전자기기가 이미 꽂혀있는 경우, 그냥 넘어간다. 3. 다음 전자기기가 꽂혀있지 않은 경우, 무슨 전자기기를 뺄지 선택한다. 3-1. 꽂힌 전자기기 중 남은 전자기기에 없는 전자기기가 있으면..