개발왕 양선규

"코딩 테스트 합격자 되기" 교재를 완독했다. 하루에 1문제 ~ 3문제 정도를 푼 결과 완독은 2달 정도 걸렸다. 분량이 700페이지 정도 되기에 이걸 언제 다 읽나 하긴 했지만, 매일 조금씩 늘어가는 스스로를 보니 그렇게 긴 분량도 아니었던 것 처럼 느껴진다. 이 교재는 프로그래머스 문제 + 저자 출제 문제 합쳐서 총 100문제가 담겨 있고, 코딩 테스트에서 중요하게 생각할 점이나 시간 복잡도 계산법 같은 초보자가 놓치기 쉬운 부분을 가장 먼저 짚고 시작한다. 최근 코딩 테스트에서 나오는 빈출 유형들은 대부분 실려 있으나, 이분 탐색 알고리즘이 실려 있지 않다는 것이 조금 아쉽긴 하다. 도서명: 코딩 테스트 합격자 되기평점: 7/10 우선 책을 읽기 전 나의 기반 지식부터 말하겠다. 1년 전 쯤 크래프..

슬라이딩 윈도우 or 투 포인터 문제이다. 나는 슬라이딩 윈도우가 익숙하고 더 직관적이라고 생각해서, 슬라이딩 윈도우 방식으로 풀었다. from collections import defaultdictimport sysinput = sys.stdin.readline"""최장 연속 부분 수열 길이 구하기같은 정수는 K개 까지 허용N: 제공된 수열 길이K: 같은 정수 허용 상한nums: 제공된 수열num_count: 각 숫자 당 개수 세는 딕셔너리, 기본값 int슬라이딩 윈도우딕셔너리 구조 -> 숫자: 개수-> 특정 숫자가 K개가 넘었다면, left는 특정 숫자 위치까지 진행하며 딕셔너리에서 값을 빼고 right는 right + 1 부분부터 다시 진행한다"""N, K = map(int, inp..

그리디 문제이다. 살짝 어려웠다. 난 2가지 방식으로 풀었는데, 의문점이 있다. import sysinput = sys.stdin.readline"""1. 큰 값 순서대로 정렬2. 현재 가장 큰 값 기준으로, 원본 리스트 역순 순회하며 가장 큰 값 찾기3. 찾았다면, 가장 큰 값 포함한 좌측 값 전부 사서 큰값에 팔기4. 원본리스트에서 방금 사용된 값을 전부 없애기5. 반복현재 가장 큰 값 idx가 while문당 1씩 증가하는데, 이거 좀 비효율이다. 이후에 올 큰값들이 지워지면 쓸모없어지기 때문따라서 가장 큰 값 리스트에서도 값들을 지워주고, 항상 0으로 인덱싱 하면 될 것 같은데 귀찮다.[1, 3, 1, 10, 2, 9, 3, 10, 5][10, 9, 5, 3, 2, 1]"""for _ in rang..

그리디 문제이다. 실버 3보다는 좀 더 쉬운 것 같다. 시간복잡도도 고려할 필요 없다. 난 고려하긴 했지만. import sysinput = sys.stdin.readline"""0이 앞에 최대한 많아야 한다1은 앞부터 지우고0은 뒤부터 지우면 되지않나1. 리스트로 받아서 , 지우지 말고 -1로 교체 (지우는 연산 오버헤드 방지)2. 앞부터 -1이 아닐 경우 출력"""S = list(map(int, input().strip()))"""0, 1 개수 세기"""count = [0] * 2 # 0의 개수, 1의 개수 저장할 리스트for num in S: if num == 0: count[0] += 1 else: count[1] += 1"""앞부터 1 지우기"""delete..

구현, 정렬 문제이다. 입력값이 다양하게 주어져서 헷갈리고, 관리해야 하는 데이터가 많아 헷갈린다.그러나 정렬 조건만 제대로 숙지한다면 크게 어렵지 않게 풀 수 있는 문제이다. import sysinput = sys.stdin.readline"""k개의 문제를 풀면 0점 ~ 100점 획득함 -> 팀ID/문제번호/점수 저장한 문제를 여러 번 제출하면, 최고점수가 최종점수 -> 제출안하면 0점팀의 점수는 각 문제 최종 점수의 합점수가 동일한 팀이 있을 경우1. 점수가 같으면, 제출 횟수가 적은 팀이 이긴다2. 점수와 제출 횟수가 같으면, 마지막 제출 시간이 빠른 팀이 이긴다정렬 조건: 점수 높은순, 제출횟수 적은순, 제출시간 빠른순"""for _ in range(int(input())): """ ..

구현, 문자열 문제이다. 비슷한 단어가 될 수 있는 조건을 정확히 찾으면 쉬운 문제인데, 조건 하나를 빠뜨려서 조금 헤맸다. from collections import defaultdictimport sysinput = sys.stdin.readline"""길이가 2이상 차이나면 제외.1. 길이가 1차이나는 경우, 나머지 문자의 개수가 전부 같다면 비슷한 단어이다.2. 길이가 같은 경우, 모든 문자가 같으면 비슷한 단어이다.3. 길이가 같은 경우, 하나의 문자가 다르다면 비슷한 단어이다.-> 이 3가지 외에 만족하는 케이스는 없다."""N = int(input())ref = input().strip()ref_count = defaultdict(int)for key in ref: ref_count[k..

전통적인 그리디 문제이다. 부분 최적해가 전체 최적해가 된다.can_eat 함수의 슬라이싱 부분은, 투포인터나 슬라이딩 윈도우 성질도 띈다. import sysinput = sys.stdin.readline"""N: 식탁의 길이K: K 이하 거리 햄버거 먹기 가능table: 사람과 햄버거의 위치사람 기준 순서대로 왼쪽이든 오른쪽이든 가장 가까운거 먹으면 될거같은데..? 그리디?K가 최대 10이니 가능할거같다. K 햄버거와 사람을 따로 보지 않고, 매핑되는 관계로 간주한다.왼쪽부터 K범위를 순차 탐색하며, 매핑될 경우 두 요소를 방문처리한다."""def can_eat(idx, K): # 기준 (사람 또는 햄버거) point = table[idx] # idx 뒤로 K거리만큼 잘라낸다 (슬라이..

주어진 예산 안에서 요청받은 금액을 배정해 주어야 한다.예산이 충분하다면 요청받은 대로 전부 다 주면 되지만, 예산이 부족하다면 상한가를 정해서 최대한 많은 예산을 배분해야 한다.즉 상한가를 정하고, 모든 예산을 전부 소모한다면 최적의 해다. import sysinput = sys.stdin.readline"""1. 모든 요청을 줄 수 있다면 다 준다2. 상한액을 정해서, 상한액 이상인 요청엔 상한액만 준다. 상한액 이하의 요청은 그대로 준다"""N = int(input())reqs = list(map(int, input().split()))budget = int(input())def calc(limit, arr): """ 상한가를 고려해, 지급해야 할 금액 계산 limit: 상한가 ..

구현, 정렬, 시뮬레이션 문제이다. 모든 학생이 각자 물러선 총 횟수를 구해야 한다. import sysinput = sys.stdin.readlinedef binary_search(child, arr): start = 0 end = len(arr) - 1 result = len(arr) while start end: mid = (start + end) // 2 if arr[mid] > child: result = mid end = mid - 1 else: start = mid + 1 return len(arr) - resultP = int(input())for _ in r..

2018 KAKAO BLIND RECRUITMENT에 출제된 문제이다. 구현, 문자열 문제이고 문제 조건이 크게 어려운 건 아닌데, 구현 문제다 보니까 디테일한 부분에서의 실수가 없도록 주의해야 하는 문제이다. def solution(msg): """인덱스 -> 문자열, 문자열 -> 인덱스 사전 제작""" idx_to_str = [''] + [chr(i) for i in range(ord('A'), ord('Z') + 1)] str_to_idx = dict() for i in range(26): char = chr(ord('A') + i) str_to_idx[char] = i + 1 """메인 로직, 문자열을 전부 압축할 때..