3월 4주차 코딩테스트
목차 미로 탈출 넘버원 (1) 지도와 폭탄 (1) 테트리스 알까기 챔피언 (1) 최소 합차 (1) 1. 미로 탈출 넘버원 (1) 풀이 import collections def solution(N, M, maze): rows = N cols = M def bfs(): directions = [(-1, 0)
3월 3주차 코딩테스트
목차 한밤의 습격자 2회 윷놀이 최강자전 DP같은 PQ 나누어 떨어뜨리기 수영장 1. 한밤의 습격자 풀이 from collections import deque """ * BFS 문제의 변형입니다. * 일반 BFS 미로찾기에, 낮/밤에는 지도가 달라지는 기믹을 적용합니다. * visited 외에 waite
3월 2주차 코딩테스트
목차 이어 붙인 문자열 카지노 교환원 1. 이어 붙인 문자열 풀이 def solution(s, words): result = False def dfs(s): nonlocal result if s == '': result = True return for w in words: if s.startswith(w
3월 1주차 코딩 테스트
목차 방탈출 열쇠편 좀비 바이러스 성역 평면 상의 MST 거꾸로 BFS 점프! 1. 방탈출 열쇠편 풀이 def solution(maze): def subprob(a, b, start): m = b[0] - a[0] + 1 n = b[1] - a[1] + 1 dp = [[0]*n for _ in range
2월 4주차 코딩 테스트
목차 단 한번의 기회 n번 숫자 세고 말하기 사전식 배열 aaaaaa 유능한 암살자 1. 단 한번의 기회 풀이 def solution(num): num_str = list(str(num)) # 숫자를 문자열 리스트로 변환 n = len(num_str) # 가장 큰 숫자의 인덱스를 저장 max_index
2월 3주차 코딩 테스트
목차 금쪽이 상담소 삽질의 대가 한 번의 거짓말 제한된 비행편 전광판 컨트롤 1. 금쪽이 상담소 풀이 def solution(start, end, price): items = [(e, s, p) for e, s, p in zip(end, start, price)] items.sort() dp = [0 f
2월 2주차 코딩테스트
목차 유사 삼합 나만의 atoi 직사각형들과 직사각형 의리의 짐싸기 효율적인 문제 풀이 1. 유사 삼합 풀이 /* * 3개의 숫자를 뽑는 것은 brute-force로 할 경우 * nC3 = n*(n-1)*(n-3) / (3*2*1) 가지이므로, O(n^3)에 해당합니다. * 숫자를 정렬한 후에 투포인터
2월 1주차 코딩 테스트
목차 이중 점수 돌 게임 통 속의 공 강력한 패스워드 k자리 제거하기 선을 넘나드는 사각형 1. 이중 점수 돌 게임 풀이 이 문제는 두 돌의 가치의 합이 가장 큰 순으로 정렬하고 차례대로 뽑으면 된다. 그 이유는 자신의 돌의 가치가 낮더라도 상대의 돌의 가치가 높다는 뜻이되어 상대가 높은돌의 가치를 뽑지
1월 5주차 코딩 테스트
목차 CCW 제한된 소인수 케르베로스 밥먹이기 소코반 최소의 연료통 1. CCW 풀이 def solution(points): p1, p2, p3 = points x1, y1 = p1 x2, y2 = p2 x3, y3 = p3 val = (x1 * y2 + x2 * y3 + x3 * y1) - (x2 *
1월 4주차 코딩 테스트
목차 바둑돌 1. 바둑돌 문제 당신은 N x N 의 격자 형식의 종이 위에 친구와 바둑과 유사한 놀이를 하였다. 이 놀이의 결과로 바둑돌은 격자 위라면 어디에도 놓여있을 수 있으며, 바둑돌이 없어 연필로 그려져 있다. 이제 한 게임이 끝나고, 다음 게임을 하기 위해서 당신은 연필로 그려진 바둑돌을 모두
1월 3주차 코딩 테스트
목차 활동 선택 1. 활동 선택 풀이 이 문제는 그리디 문제로 회의실 배정 알고리즘에 속한다. 풀이 방법은 모든 조합을 따져보는 방법이나 이는 너무 시간이 오래걸린다. 따라서 많은 회의를 진행하기 위해서는 최대한 빨리 회의가 끝나야 한다는 관점으로 풀이해야 한다. 제일 빨리 끝나는 회의를 기준으로 겹치는
1월 2주차 코딩 테스트
목차 (미완) 은행거래 한 끗 차이 단어 유사도 1. 은행 거래 풀이 이 문제를 처음에는 순환 그래프인 경우 그것을 1개의 거래로 최적화할 수 있겠구나라는 방식으로 접근하였다. 그러나 이 문제는 누구에게 보내는지에 대한 제약이 없고 그냥 최종적인 결과만 같으면 되는 문제이다. 예시: [[0, 1, 100
1월 1주차 코딩 테스트
1. 바가지 문제 풀이 def solution(x, y, target): if x + y < target: return False visited = set() q = [] q.append(0) visited.add(0) while q: curr_val = q.pop(0) if curr_val == tar
12월 4주차 코딩 테스트
목차 원 그리기 배열의 최솟값 1. 원 그리기 풀이 이 문제는 원의 중심좌표와 탐색하고자하는 픽셀좌표와의 거리를 구한다. 만약 원의 반지름보다거리가 작거나 같으면 원을 그리는데 포함되는 픽셀이고 원의 반지름 보다 크다면 원을 그리는데 포함되지 않는다. 피타고라스의 정의를 사용한다. 문제에서 픽셀영역(네모
12월 3주차 코딩 테스트
목차 이진 영상 0보단 1 전광판 채우기 장대 정상에 올라가기 워드 스퀘어 1. 이진 영상 문제 0과 1로 이루어진 이진 영상이 2차원 정수 배열 image 에 주어져 있다. x, y 좌표에 위치한 값은 image[x][y] 에 저장되어 있다. 이 이진 영상에는 1로 표기된 검은색 영역이 단 하나 존재하
12월 2주차 코딩 테스트
목차 부분 문자열 배열 안정화 가구 연결 배열 곱 플라스틱 소화 1. 부문 문자열 문제 부분 문자열은 어떤 문자열에서 문자의 순서를 유지하면서, 일부 문자를 제거한 문자열이다. 예를 들어 "acf"는 "abcdef" 의 부분 문자열이지만, "adc"는 "abcdef"의 부분 문자열이 아니다. 문자열 sr
12월 1주차 코딩 테스트
목차 카드 게임 Original 배열 로봇 청소기 3. 카드 게임 문제 당신은 친구와 카드 뒤집기 게임을 하고 있다. 카드 뒤집기 게임은 연속으로 배치된 카드 중에 인접한 2개의 카드가 '앞면( 1 )'일 때 해당 카드를 '뒷면( 0 )'으로 뒤집는 게임이다. 이 게임은 당신이 먼저 시작해서 더 이상 카
11월 3주차 코딩 테스트 Study
목차 제로 카드 게임 세금 납부 그래플러 찾기 미용실 예약 벽 피하기 게임 소수판별 회전방어 등산 최소비용 1. 제로 카드 게임 문제 제돌이와 제순이는 "제로 카드 게임"을 하기로 했다. 제로 카드 게임은 아래와 같은 룰로 진행된다. N개의 카드를 카드 더미에서 뽑는다. 정해진 시간 내에 카드를 두 그룹
11월 1주차 (주말) 코딩 테스트 Study
목차 전투력 비교 연발사격 표적 맞추기 시험문제 학생 전투력 1. 전투력 비교(금) 총 N개의 좌석이 일렬로 나열되어 있다. 또한 1번부터 N번까지 N명의 전사가 존재하며, 각 전사는 하나의 좌석에 배치해야 한다. 이때, 각 전사는 모두 개별적으로 전투력 정보를 가진다. 그리고 전투력 정보는 서로 동일할
11월 2주차 코딩 테스트 Study
목차 전광판 모래 뺏기 게임 최대공약수 중복문자제거 반복 문자 단어게임 계단오르기 버스 정류장 1. Billboard 문제 설명 n개의 문자를 보여주는 크기가 n인 전광판이 있습니다. 전광판의 문자는 오른쪽에서 왼쪽으로 반복해서 흘러가며, 1초에 한 글자씩 흘러갑니다. 예를 들어, 크기가 5인 전광판에