코딩기록

https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr BFS만 사용하면 마지막 테스트 케이스가 통과되지 않는다! BFS + DP의 조합으로 ..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제에 제시된 그림을 보면, 답을 구할 수 있는 힌트가 있다. 다음과 같이 경우를 나눠볼 수가 있다. 가로로 오는 경우 -> 가로에서 가로로, 대각선에서 가로로 세로로 오는 경우 -> 세로에서 세로로, 대각선에서 세로로 대각선으로 오는 경우 -> 가로에서 대각선으로, 세로에서 대각선으로, 대각선에서 대각선으로 이것을 기반하여 DP를 활용하여 코드를 작성하면 된다. 가로, ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 생각보다 어렵지 않은 투포인터 문제여서 자신있게 제출했지만 시간초과...^^ 이유는 sum()을 사용한 것 때문! 부분합 리스트를 저장해두는 방법을 사용하여 해결했다 n, s = map(int, input().split()) nums = list(map(int, input().split())) l, r = 0, 1 # 투 포인터 ans = 1e9 # 최소 길이 sum_n = [0] ..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 방문리스트(visited)를 3차원 배열로 만드는 것이 핵심인 문제였다. 벽을 한번만 뚫을 수 있으므로 3차원으로 만들어야 한다. visited[x][y][0] 에는 벽을 뚫지 않고 온 경우의 최단경로를 저장하고, visited[x][y][1] 에는 벽을 뚫고 온 경우의 최단경로를 저장한다. from collections import deque n, m = ma..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 전형적인 LCS 문제입니다. LCS 개념과 푸는 방법만 알면 쉽게 풀 수 있습니다. 먼저 두 문자열을 담은 2차원 리스트를 만듭니다. 그리고 문자 하나씩 비교해가면서 최장 수열의 개수를 세면 됩니다. 최장 수열의 개수를 세는 방법은, 문자가 같은 경우 -> dp[i][j] = dp[i-1][j-1] + 1 (글자가 추가 되기 전 최대 길이 +..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이 문제를 풀기에 앞서 이분 그래프의 개념을 알고 가야 한다. 이런 식으로 정점의 색깔을 바꾸어 칠하면서 같은 색끼리 간선이 없는 경우 이분 그래프이다. 간선이 있다면 이분 그래프가 될 수 없다. 이것을 코드에 적용하면 문제를 풀 수 있다. 코드에서는 색상을 숫자로 표시하였다. (예 - 파랑은 1로, 빨강은 -1로) from collections import deque import sys inpu..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net import copy N, M = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(N)] dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] direction = { 1: [[0], [1], [2], [3]], 2: [[0, 2], [1, 3]], 3: [[0, 1], [1..

https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net MK일 경우 최소값은 15, 최대값은 50이 된다. MMK일 경우 최소값은 105, 최대값은 500이 된다. MKMM일 경우 최소값은 1510, 최대값은 5011이 된다. 이제 규칙을 알 수 있다. ▶ 최소값의 규칙 = K로 끝날 때마다 10 ** (K가 나오기 전 M의 개수) + 5 를 추가한다. M으로 끝날 때 10 ** (M의 개수 - 1) 를 추가한다. ▶ 최대값의 규칙 = K로 끝날 때마다 5 * (10 ** (K가 나오기 전 M의 개수)) 를 추가한다. M으로 끝날..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N, K = map(int, input().split()) nums = list(input()) k, stack = K, [] for i in range(N): while k > 0 and stack and stack[-1] < nums[i]: # 앞에 숫자가 해당 숫자보다 작을 경우 지운다 stack.pop() k -= 1 stack.append(nums[i]) print(''.join(stack[:N-K])) # K개를 지우지 못하는 경우를 위해 인덱스 슬라이싱을 해준다..

https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 그리디 문제이다. 해결방법은 다음과 같다. [ 이동 방법 ] 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 1. N == 1 인 경우 - 위 아래로 움직일 수 없으므로 시작칸만 방문할 수 있다. 따라서 방문할 수 있는 칸의 수는 1이다. 2. N == 2 인 경우 - 위 아래로 1칸만 움직일 수 있으므로 2, 3번 방법만으로 움직일 수 있다. 가로가 아무리 길더라도 최대 3번 이상 움직일 수 없..