https://www.acmicpc.net/problem/28298 28298번: 더 흔한 타일 색칠 문제 첫째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. $(1\le N,M,K\le 500;$ $N,M$은 $K$의 배수이다$)$ 다음 $N$개의 줄에는 타일의 $i$행 색상 배치를 의미하는 길이 $M$의 문자열 $d_i$가 주어진다. www.acmicpc.net 시간 초과가 생긴 문제. 이번엔 입력값 제한을 보고 시간에 맞게 로직을 짰다고 생각했는데 시간초과가 발생했다. 로직을 조금 수정하니까 통과했다. 왜 그런지 생각해 보니 원인을 찾을 수 있었다. 중간에 리스트에서 개수가 가장 많은 요소를 출력하는 메서드가 필요했다. 많은 방법이 있지만 나는 코드를 간결하게 작성하고 싶어 ..
https://www.acmicpc.net/problem/28250 28250번: 이브, 프시케 그리고 푸른 MEX의 아내 첫째 줄에 정수 $N$이 주어진다. ($2 \le N \le 200\,000$) 둘째 줄에 $N$개의 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($0 \le A_i \le 100\,000$) www.acmicpc.net 문제 이름이 특이해서 풀어본 문제. 실2라고 얕잡아봤다가 끔찍한 결과가 나왔다. 실제 코테였다면 풀었을지 장담 못하겠다. 꼭 입력값 제한을 보면서 시간을 추측하는 습관을 들이자. 여담이지만 코테 환경을 상상하며 문제를 푸는 건 도움이 되는 거 같다. 아이디어 1. 이중 for문 실패 수식을 보고 무식하게 이중 for으로 구현했다가 ..
https://www.acmicpc.net/problem/28017 28017번: 게임을 클리어하자 첫째 줄에 산지니가 게임을 몇 회차를 하는지 나타내는 수 $N$과 무기의 종류 $M$이 공백으로 구분되어 주어진다. $(2 \le N, M \le 500)$ 둘째 줄부터 $N$개의 줄에는 각 무기마다 게임을 클리어하는데 www.acmicpc.net 대회 초반에 삽집하다가 DP인걸 깨닫고 해결했다. pypy로 제출, 이후 python으로 다시 제출. 아이디어 1. 반복문 단순 반복문으로 작성했다 실패했다. 2. DP n회차의 각 무기마다 올 수 있는 시간을 저장하면 된다. 위 이미지처럼 이전 행에 있는 값 중 최솟값을 다음 행에 더해가며 업데이트하면 된다. 최종적으로 마지막 행의 최솟값을 출력하면 된다. 전..
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 그래프 탐색하는 문제. 비슷한 유형의 문제를 풀어봤으면 쉬운 문제. 아이디어 1. 모눈종이 M*N 크기의 2차원 리스트로 모눈종이를 나타냈다. 주어진 직사각형 좌표에 따라 직사각형을 표현해준다. 1은 직사각형, 0은 빈공간을 나타낸다. 문제에서는 좌표가 왼쪽 아래가 원점(0, 0)이지만, 리스트는 왼쪽 위가 원점이다. 어차피 가로축에 대해 대칭이므로 문제에서 요구한 값을 구하는..
https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 조건만 잘 생각하면 되는 착한 문제. 아이디어 1. 다익스트라 출발지로 부터 최단거리를 계산해서 수색 범위안에 들어가는지 확인하면 된다. 수색 범위안에 들어오면 아이템 개수를 더해주면 된다. 1 ~ n까지 for문으로 출발지를 바꾸면서 탐색하면 된다. 2. 플로이드 워셜 지역의 개수(100)가 적으므로 플로이드 워셜로 풀어도 시간초과에 걸리지 않는다. 전체 코드 다익스트라 import heapq imp..
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 구간 합 구하기 2차원 버전 아이디어 1. 누적 합 사용 구간 합 구하기 4와 유사하게 풀었다 먼저 (0 ,0)에서 (x , y)까지의 합을 arr [x][y]에 저장한다. 그럼 아래와 같은 리스트를 만들 수 있다. 이걸 사용해서 구간 합을 구하면 된다. 예를 들어 (1, 1)에서 (2, 3)까지 구하려면(문제에서는 2,2 ~ 3,4) arr [2][3]..
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 배열에서 i부터 j까지가 팰린드롬인지 아닌지 여러 번 확인하는 문제. 아이디어 1. dp 간단하게 리스트 슬라이싱으로는 시간 초과가 나서 dp를 사용 i번째부터 j까지의 수가 팰린드롬인지 확인한 결과를 저장하기 위해 이차원 리스트를 사용하기로 결정했다. 2. 점화식 먼저 무조건 팰린드롬인 i부터 i까지의 수는 1로 저장해둔다. 그리고 i번째 수와 i + 1번째 수가 같으면 팰린드롬이니까 이것도 1로 저장. 점화식은 이미 팰린드롬인 수 ..
알고리즘 문제를 풀고 정답을 출력할때 자주 사용하는 join함수. 알아두면 유용하다. arr1 = ['a', 'b', 'c', 'd'] print(', '.join(arr1)) 출력 결과: a, b, c, d join은 기본적으로 '구분자'.join(리스트) 형태를 가지고 있다. str1 = ''.join(arr1) print(str1) 출력결과: abcd join함수는 문자열을 반환해준다. a = ['is', 'you', 'down'] print('_'.join(a)) print(' '.join(a)) 출력결과: is_you_down is you down 이런식으로 사용 가능 arr2 = [1, 2, 3 ,4] print(', '.join(map(str,arr2))) 출력결과: 1, 2, 3, 4 jo..
