본문 바로가기
  • 시 쓰는 개발자

백준17

11/20 스터디 [ tip ] 같이 공부하는 분께서 알려주신 건데, 일차원 배열만을 고집하기 보다는 이차원 배열도 적당히 섞어가며 생각해보면 좋은 답이 나올 수 있다고 하셔서, dp문제를 다음 2가지 방법으로 생각해보는 연습을 해보면 좋을 듯 하다. 1. 하나의 배열을 가지고 값을 추적하면서 값 업데이트. 2. 이중배열을 사용해서 각각의 경우의 수를 따지기. 1463 1로 만들기 여느 dp 문제가 그렇듯, 코드는 간단한데 이것을 생각해내기가 매우 어려웠다. 이 문제를 못푼 가장 큰 이유는 내가 dp문제를 풀 때 항상 top down 식으로 생각했던 것이었다. 첫번째 수와 두번째 수가 주어지면 점화식을 세우기 수월하므로 이것을 bottom up 상향식 풀이로 풀었어야 했는데 무조건 값 n에서 시작해서 내려가려고 하다보니 .. 2022. 11. 21.
코딩 문제들 느낀점 list[index+1]나 list[index-1] 처럼 다룰 때는 쉽게 out of index 나곤 함. for문을 length - 1까지만 돌리는 것들이 하나의 방법이 됨 ★★중요★★ 코드 작성할 때 주의할 것은 경계값이다. 시작지점과 끝지점에서도 정상작동 하는지 체크하는 게 중요. 안그러면 IndexError: list index out of range 가 쉽게 난다. ex. index가 0일때, 1일때 혹은 끝 인덱스일 때 등등. 테스트 케이스에서 입력값이 1억처럼 큰 경우도 있으니 for문 돌릴 때 혹은 list 초기화 할 때 함부로 입력값만큼 돌리게끔 해놓으면 안됨 그럼 시간이나 메모리 초과 날 수도 있다. 3번과 같은 맥락으로, 그래서 무지성 리스트로 풀 게 아니라, 가지고 있는 값들을 어떻.. 2022. 11. 17.
11/16 스터디 1149 RGB 거리 약간 greedy처럼 생각해서 풀었는데, 1번째는 그 다음 2,3번째만 더할수 있고 2번째는 1,3번째만, 3번째는 1,2번째만 더할 수 있는 것을 이용해서 매번마다 최소인 것들만 더해주는 식으로 진행하였다. 경우의 수가 3가지밖에 없기 때문에 하나씩 다 진행해도 상관없다고 생각했고, 마지막에 나온 3개의 값들 중 가장 작은 값을 선택하면 됐다. n = int(input()) lst = [] for i in range(n): lst.append(list(map(int, input().split()))) for i in range(1, n): lst[i][0] += min(lst[i-1][1], lst[i-1][2]) lst[i][1] += min(lst[i-1][0], lst[i-1.. 2022. 11. 16.
11/14 스터디 9461 파도반 수열 DP문제의 핵심은 점화식 만들기인 것 같고 그걸 얼마나 그럴싸하게 만들어내느냐가 관건인듯하다. 이 문제는 점화식을 만들기 쉬워서 풀 수 있었다. 단순히 f(n) = f(n-1) + f(n-5)만 찾아내면 풀 수 있었는데 f(n)이 정말 여러 형태로 나올 수 있었기 때문에 어렵지않게 해결할 수 있었다. n = int(input()) tri = [0] * 101 # 여기 100으로 한거때문에 런타임에러 .... tri[1] = 1 tri[2] = 1 tri[3] = 1 tri[4] = 2 tri[5] = 2 for i in range(n): t = int(input()) for j in range(6, t+1): if tri[j] == 0: tri[j] = tri[j-1] + tri[j.. 2022. 11. 14.
11/09 스터디 1931 회의실 배정 정말 막막했던 문제였는데, key point는 2가지 정도였다고 본다. 1) 회의 시간이 짧은 게 중요 2) 회의가 끝나는 시간이 서로 같다면, 회의 시작 시간으로 정렬. 왜냐하면 1~2와 2~2도 가능하기 때문. 그래서 일단 회의 시작 시간으로 정렬하고, 끝나는 시간에 대해 한번 더 정렬을 하면 2번조건을 만족하면서 회의 시간이 짧은 게 위로 올라온다고 생각했다. 이를 lambda함수로 정렬했고 가장 위로 정렬된 회의를 일단 한다고 가정해 cnt를 1로 놓고 시작했다. 그래서 처음 회의가 끝나는 시간이 다음회의가 시작되는 시간보다 "작거나 같을 때" 회의를 할 수 있으므로 cnt를 1 늘려주고, 새로운 회의로 다시 비교를 하기 위해 end에 넣어주었다. 이를 반복한다. n = in.. 2022. 11. 9.
11/07 스터디 11047 동전 0 정렬을 하면 시간초과, 안하면 통과되는 문제였다. 그래서 오름차순으로 입력된다는 조건을 이용해서, money_list[n-i]로 입력받아서 내림차순으로 저장되게 하였다. 그렇게 하면 정렬할 필요가 없어서 통과할 수 있었다. 그 뒤로는 전형적인 동전 문제처럼, 5만원을 최대한 넣어보고(몫으로 반환), 그다음은 1만원, 다음 5천원 .... 을 계속 반복해서 동전의 개수를 세어서 반환하였다. import sys n, money, = map(int, input().split()) money_list = [0] * n for i in range(1, n+1): money_list[n-i] = int(sys.stdin.readline().strip()) cnt = 0 i = 0 while mo.. 2022. 11. 7.
11/02 스터디 10816 숫자카드2 핵심 Counter import sys from collections import Counter # 해당 원소들이 몇번 등장했는지 카운팅해서 dict로 반환 n = int(input()) # 숫자카드 n개 cardlist = list(map(int, sys.stdin.readline().strip().split())) m = int(input()) # 정수 m개 numlist = list(map(int, sys.stdin.readline().strip().split())) count = Counter(cardlist) for i in range(m): if numlist[i] in count: print(count[numlist[i]], end = ' ') else: print(0,.. 2022. 11. 7.
코딩테스트 시간초과 해결법 (백준) 1. 코드를 PYPY3로 돌려본다. pypy3도 파이썬으로 만든거지만 속도도 빠르고 문법이 동일해서 pypy3로 바꿔주기만 하면 된다. 2. 입력을 받을 때 input()대신에 sys.stdin.readline()을 사용하자. 거의 2배는 빠르다고 한다. input()은 rstrip()을 적용해 반환하기 때문에 느리다. ※ 주의) sys.stdin.readline()는 \n도 받아오기 때문에 항상 .strip()을 해줘야한다. 3. 반복문 줄이기, 특히 중첩 for문 4. 재귀함수를 쓰는 경우, 메모이제이션 기법을 활용해보자. ▶ 이전에 계산한 값을 중복 계산하지 않기 위해 저장해놓는 기법. 팩토리얼이나 피보나치수열 처럼 기존에 한번 계산을 했던 것이 나중에 반복적으로 다시 나올 때 사용하면 효율적이다... 2022. 10. 28.

티스토리툴바