도각도각 필기노트

코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 처음 짠 코드 (틀린 코드) 문제를 푼 시점에서 생각해보니, 문제를 제대로 이해하지 않고 짜면서 접근을 바꾸려다보니 시작부터 틀어졌다. course 개수마다 가장 많은 것들을 answer로 내놓아야 한다는 점을 간과하고, 처음엔 모든 조합을 생성해서 table이라는 딕셔너리에 넣고, 개수가 많은 것들을 컷하면 되는 간단한 문제라고 생각했었다. 그래서 모든 가능한 경우를 table ={} 에 넣고 course 개수로 정렬하고, 전체 조합이 다 있는 딕셔너리 안에서 ..

미국여행 후 정말 오랜만에 푸는 거라 dictionary 문법도 다 까먹어서 구글링을 통해 고심하며 푼 나의 코드.. 시간초과 날 것 같은데 걱정하며 돌렸지만 그래도 통과는 했다. 그치만 아무리 봐도 맘에 들지 않는 코드 모범 답안을 분석해봐야겠다. 나도 저렇게 효율적인 코드를 짤 수 있도록..! 내 풀이 def solution(id_list, report, k): answer = [] p_dict = {} # {'신고한 유저': ['신고 당한 유저']} declared = {} # 신고 당한 유저 {'name': num} for idl in id_list: p_dict[idl] = '' declared[idl] = 0 for r in report: p1, p2 = r.split() if p2 in p_..

대표적인 이진탐색, 파라메트릭 탐색 문제였다. mid 값을 답 후보로 두고 start 와 end 를 조정해나가며 푸는 문제였다. import sys k, n = map(int, input().split()) array = [int(sys.stdin.readline().strip()) for _ in range(k)] start = 1 end = max(array) while start

입력이 많은 문제이다. 시간 초과가 나면 input 대신 sys.stdin.readline() 을 사용할 것!! * 처음에는 주어진 숫자들이 순위가 아니라 점수인 줄 알고 문제 이해를 못했었다.. 문제를 잘 읽자!! 우선 첫번째 순위로 정렬을 해준다. 1 4 2 3 3 2 4 1 5 5 그러고 나면 두번째 순위만 따져주면 된다. rank라는 변수에 첫번째 사원의 두번째 순위를 초기값으로 넣어준다. 아래 사람으로 갈수록 첫번째 순위는 전 사람보다 낮기에 두번째 순위가 rank(이전 사원의 순위)보다 커야 선발이 된다. 1 4 2 3 이 두 사람을 비교할 땐, rank=4와 3을 비교하게 된다. 4등보다 3등이 높으므로 두번째 사람은 선발된다. rank는 더 높은 순위의 것으로 업데이트해준다. 4 1 5 5..

일단 숫자(numbers)와 연산자(operators)를 구분해주었다. 보통 구분자를 기준으로 나눌 때 split 함수를 사용하는데, 여기서는 +, - 두 가지로 구분을 해야하기 때문에 import re 를 통해 여러 개 구분자로 split 해주었다. 아래 코드와 같이 numbers = re.split('[+-]', S) 으로 써주었다. split 기준이 될 기호를 '[ ]' 안에 넣는 형식으로 사용한다. 문제 풀이 아이디어 최솟값이 나와야 하므로 +와 -가 있을 때 최대한 -로 계산되게 하는 것이 문제의 핵심이었다. previous에 이전 연산자를 넣고, now에 현재 계산할 연산자를 넣은 다음, 둘을 비교하여 현재 숫자를 더할지 뺄지 결정하였다. (1) previous = +, now = + 그대로 ..

그리디 기출문제 풀이 1. 모험가 길드 사람들의 공포도 리스트를 오름차순으로 정렬 후, 공포도가 작은 사람부터 그룹을 형성해서 그룹이 최대 개수가 되도록 풀었다. n = int(input()) x = list(map(int, input().split())) x.sort() answer = 0 idx = 0 # 현재 사람의 인덱스 while True: num = x[idx] # 현재 사람의 공포도 answer += 1 if idx + num >= n: # 현재 사람의 공포도만큼 수 추가 break # 만약 n을 넘어가면 break else: # 현재 사람의 공포도만큼 인원 수를 추가했을 때 n을 넘지 않는다면 idx += num # idx 조정하여 다음 사람 따지도록 print(answer) 2. 곱하기 ..

다이나믹 프로그래밍 개념과 풀이 방법을 익히자. 부끄럽지만 학과 알고리즘 수업 때 dp 관련 문제들은 정말 이해가 안가서 dp관련 문제들은 과제도 제출 못하고 시험 문제도 못 푼 기억이 있다. 알고리즘에서 중요한 부분을 차지하는 만큼 열심히 공부해서 익히자! 두 가지 속성을 만족해야 다이나믹 프로그래밍을 문제를 풀 수 있다. 1. Overlapping Subproblem : 겹치는 부분 문제 2. Optimal Substructure : 최적 부분 구조 각 부분 문제는 한 번만 풀어야 한다. Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다. 따라서, 정답을 한 번 구했으면, 정답을 어딘가에 메모(배열에 저장)해놓는다. (Memoization) 구현 방법 구현..

www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 여러 개의 숫자들 간의 최대공약수를 구하는 문제이다. 100, 360, 25, 10 간의 최대공약수를 구한다고 하면, gcd(100, 360) = 20 gcd(20, 25) = 5 gcd(5, 10) = 5 이런 식으로 앞에 두 수의 gcd를 구하고, 결과로 나온 그 gcd값과 다음 수와의 gcd를 구하고, 이런 방식으로 반복하여 여러 수들 간의 gcd를 구한다. def gcd(..