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

알고리즘14

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.

티스토리툴바