안녕

0. 문제 링크 https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 1. 풀이 방법 가능한 좌표를 찾는 함수 놓을 수 있는지 판단하는 함수 스티커 붙이는 함수 회전 함수 이 모든 것을 조화롭게 사용하면 풀 수 있음 2. 코드 import sys input = sys.stdin.readline def canCoordinate(sticker): # 가능한 좌표를 찾는 함수 coordinate = [] yOffset = len(sticker) xOffse..

0. 문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 이전 풀이 2023.02.03 - [Computer Science/알고리즘] - [백준 - Python] 6087 - 레이저 통신 [백준 - Python] 6087 - 레이저 통신 0. 문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 ..

0. 문제 링크 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 1. 풀이 방법 큐를 4개 사용했음. (백조가 움직이는 큐, 물이 녹는 큐, 다음 턴에 백조가 움직여야 하는 큐, 다음 턴에 물이 녹아야 하는 큐) 사실 이것만 있어도 충분히 풀 수 있을거라 생각함 2. 코드 import sys from collections import deque input = sys.stdin.readline def waterMelt..

0. 문제 링크 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 1. 풀이 방법 이분 탐색 + 매개변수 탐색 풀이로 풀었다. 정답이 시간이므로, 시간의 리스트 내에서 매개 변수를 탐색하는 방식 start, end 시간은 아래의 코드와 같이 설정했음. 이유는 최솟값은 무조건 불가능한 것, 최댓값은 무조건 가능한 것으로 설정해야 하기 때문 이후 while 문을 돌면서, 각 심사대마다 정해진 시간만큼 받을 수 있는 인원 세었음. 받을 ..

0. 문제 링크 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1. 풀이 방법 이 문제는 DFS + DP이다. 안 그래도 어려운 두 개를 붙였으니 더 어려웠던 것 같다. https://minny27.tistory.com/42 [백준 1937] 욕심쟁이 판다 (Python) 문제 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤..

0. 문제 링크 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 1. 풀이 방법 굉장히 찝찝하게 풀었다. 정렬을 이용해서 풀었는데, 파이썬은 문자열을 길이가 아닌 사전 순대로 나열해서 정렬을 해준다. 그래서 정렬을 해서 직전 문자열이 다음 문자열의 부분이 되는가만 파악하면 된다. 나는 좀 거창한 풀이를 생각했는데, 생각보다 간단해서 허무했다. 사실 숫자의 트리를 만들어서 풀려고 했다. 예를 들어 911 다음에 91112..

0. 문제 링크 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 풀이 방법 이 문제는 감이 중요할 것 같은 문제이다. 행렬의 곱셈 연산에서 생각했을 때, DP로 풀어야 될 것 같지만 정답은 그리디로 풀어야 하는 문제이다. 아래의 코드에서 써놓았는데, i < j < k라고 가정했을 때, 최소 연산은 당연히도 (i + j) + (i + j + k) = 2 * (i + j) + k이다. i + k를 먼저 수행한다면, 2 * (i ..

0. 문제 링크 https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 1. 풀이 방법 일단 맨 처음에는 BFS로 문제를 풀었는데, 시간 초과, 메모리 초과가 발생하였다. BFS가 아님을 깨달았고, 고등학교의 확통에서 비슷한 문제를 풀었던 경험이 생각났다. 현재 위치로 올 수 있는 애는 내 좌측과 위이므로, 좌측과 위로 갈 수 있는 경우의 수를 더하면 현재 위치에 도달할 수 있다.는 것이 확통에서 문제를 푼 방법이다. 물론 조합을 사용..

0. 문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. 풀이 방법 내 기준 가장 신박했던 문제 문제 유형은 이분 탐색 + 매개 변수 탐색이다. 이 유형은 최적화 문제를 결정 문제로 바꿔서 푸는 문제이다. 그렇다면 어떤 부분이 최적화일까? 를 먼저 생각해야 하는데, 문제에 나와있듯이 가장 인접한 두 공유기 사이의 '최대 거리'이다. 그러면 이 부분을 결정 문제로 바꿔야 하는데, ..

0. 문제 링크 https://www.acmicpc.net/problem/21925 21925번: 짝수 팰린드롬 (1, 1), (5, 6, 7, 7, 6, 5), (5, 5) www.acmicpc.net 1. 풀이 방법 스택이 비어있다면, 매 숫자마다 스택에 넣는다. 그리고 다음 숫자로 이동한다. 만약에 스택에 숫자가 들어가 있다면, 스택의 길이를 측정한다 -> l 현재 숫자의 위치인 cur과 스택의 마지막 숫자를 비교하며 좌우로 넓혀가며 팰린드롬을 만족하는지 확인한다. 이때 스택의 길이가 남은 숫자의 길이보다 길다면 이 또한 팰린드롬을 만들 수 없다. 만약 스택에 들어있는 숫자 3개와 현재 숫자의 위치인 cur에서 cur + 2까지의 3개의 숫자가 팰린드롬을 만족한다면, 스택을 모두 비운다. 그리고 T..