https://www.acmicpc.net/problem/10866 문제 풀이문제 요구사항에 맞춰서 메서드를 구현하고, 조건문으로 분기처리 하면 된다! 물론 앞뒤로 빼고 요리조리 건드리는 과정에서 시간 초과가 발생할 수 있기 때문에 반드시 파이썬의 덱 컬렉션을 써서 구현해야 한다. 덱의 경우 앞뒤로 빼고 넣을 때 O(1)의 시간복잡도를 가진다. 정답 코드import sysfrom collections import dequeinput = sys.stdin.readlinen = int(input())numbers = deque()def push_front(x): numbers.appendleft(x)def push_back(x): numbers.append(x)def pop_front(): ..
https://www.acmicpc.net/problem/2164 문제 풀이문제에 주어진 단계를 지켜가며 구현하면 된다. 이때 시간 초과가 날 수 있기 때문에 파이썬의 덱을 활용해서 O(1)으로 구현했다.맨 위의 숫자를 popleft()로 버린다. 버리기 때문에 따로 변수에 저장하지 않는다.그다음 숫자를 popleft()로 빼서 변수에 저장한 후 append()를 통해 맨 밑에 저장한다.위 과정을 덱의 크기가 1 이하가 될 때까지 반복한다. 정답 코드import sysfrom collections import dequeinput = sys.stdin.readlinen = int(input())numbers = deque()for i in range(1, n+1): numbers.append(i)w..
문제 링크스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게 된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다.문제에 제시된 조건과 요구 결과이다. 최대 점수를 얻을 수 있도록 스티커를 떼야한다. 처음엔 공유하는 스티커가 찢어져 사용할 수 없으니 BFS인가..? 했는데 전혀 아니었고, 그럼 그리디인가..? 했는데 무조건 높은 점수를 더해가면 나중에 틀리는 반례가 있었다. 즉, 모든 스티커에 방문할 때마다 최댓값을 비교하며 변경해야 하는 다이내믹 프로그래밍이었다. 예시를 통해 그리디가 아닌 이유를 알 수 있다...
https://www.acmicpc.net/problem/3085 3085번: 사탕 게임예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.www.acmicpc.net 인접한 두 사탕의 색깔이 다르면 스왑한 뒤 전체 사탕의 색깔을 탐색하면서 하나의 색으로 일치하는 가장 긴 행 or 열을 찾으면 된다. 처음에 스왑하고 유지되는 줄 알았는데, 탐색 후에 다시 원래 상태로 되돌려놔야 한다.- 상하좌우로 탐색- 어? 나랑 붙어있는데 색깔이 다르네?- 스왑 후 N x N 탐색하면서 색깔이 연속하는 가장 긴 행 or 열을 찾기- 탐색 끝나면 다시 재스왑 (원래대로 돌려놓기)- 다시 색깔 다른 인접한 칸 찾기- 반복 1. origin에 기존 색깔을 저장해 두고, 인접한 사탕의 색깔이 다르면 스..
https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 일단 이 문제는 1080번 행렬 문제와 비슷하다. 문제에서 최소 횟수를 요구하고 있기 때문에 한 번 바꿔준 애는 다시 바꿔주면 안 되겠다는 생각이 들었다. 현재 전구 상태가 원하는 전구 상태와 같으면 그냥 넘어가고, 아니면 눌러주는 방식으로 구현하고자 했다. 하지만 이렇게 풀면 예제를 틀린다. 예제에서는 000을 010으로 바꾸고 싶어 하는데, 내가 말한 대로 풀게 되..
https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 문제 풀이 a, b를 입력받은 후 비교 메서드를 호출한다. 3*3으로 뒤집어주기 때문에 n-2, m-2 범위까지만 비교한다. 3*3 범위 중 (0, 0)가 달라서 뒤집어줄 때 나머지도 함께 뒤집히기 때문이다. 뒤집기 메서드를 호출할 때마다 count를 하나씩 올린다. 뒤집기 작업이 끝난 후에는 모든 행렬 요소를 비교한다. 이때는 n, m의 전체 범위를 기준으로 비교한다. 만약 한 개라도 다른 부분이 있다면 바로..
https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 가장 큰 수를 구하는 방법 문자열을 하나씩 탐색하다가 K를 만나면 끊어준다. 만약 문자열이 K로 끝나지 않으면? K로 끊은 이후의 문자열은 하나의 M으로 취급해 준다. (예를 들어 KMKMM인 경우 K, MK, M, M) 가장 작은 수를 구하는 법 문자열을 하나씩 끊어준다. 단, M이 연속되는 경우는 묶어준다. (예를 들어 MKKMMK인 경우 M, K, K, MM, K) 정답 코드 import sys input = sys.stdin.readline strings = list..
https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 해결 과정은 다음과 같다. 주어진 막대 길이들 중, 가장 긴 막대의 인덱스를 찾는다. 가장 긴 막대를 기준으로 오른쪽 그룹과 왼쪽 그룹으로 나누어 탐색한다. 가장 길이가 긴 막대의 인덱스까지 반복문을 돌린다. (오른쪽 그룹은 0에서 해당 인덱스까지, 왼쪽 그룹은 가로길이에서 해당 인덱스까지 역순으로) 오른쪽 그룹 기준으로, 가장 오른쪽 막대의 길이를 변수 right_height로..
