코딩테스트 썸네일형 리스트형 [프로그래머스(Programmers)/Level2](Python)가장 큰 정사각형 DP를 이용해 박스를 나눌수 있는 최소크기(1*1은 예외로 처리하고, 2*2 부터)로 나눠서 우측 하단이 1 일때만 둘러쌓인 값들 중 최솟값에 +1 한값을 우측 하단에 넣어준다.(다음 연산에도 앞전 계산값을 이용하기 위해서) 추가적으로 _max에 바뀌는 값들중 최댓값을 제곱해서 리턴하면 원하는 결과값이 나오게 된다. 처음에 완전탐색으로 풀었는데 당연하게도 시간초과가 떠서 더 쉬운방법을 생각하던 중, 동적계획법(DP)로 푼 알고리즘을 찾았고, 아이디어를 따와서 풀었다. 동적계획법에 관한 공부도 해야할 것 같다. 더보기 [프로그래머스(Programmers)/Level2](Python) 카펫 노란색 타일의 약수들을 구해서 ((ex) 노란색타일이 24 장이라면 (1,24) (2,12) (3,8)...... 이런식이다.) 곱해서 해당 노랑타일의 수가되는 약수 쌍중 각각을 가로,세로 길이로 가정하고 가로*2+세로*2+4(코너 4장(왼쪽위 오른쪽위 왼쪽아래 오른쪽아래))의 값이 brown타일의 갯수와 같으면 그 약수 쌍을 return한다. 방법만 떠오르면 바로 풀 수 있는 문제였다. 더보기 [프로그래머스(Programmers)/Level2](Python) 라면 공장 stock이 버틸수 있는 dates중 (stock-dates[i]>=0)가장 큰 dates의 순번에 해당하는 supplies[i]를 찾기위해 반복하며 힙큐에 넣어주고, 더이상 stock이 버틸 수 없으면 제일큰 공급량을 stock에 더해준다.(힙큐에서 pop으로) 이 과정을 k가 stock보다 클 때 까지 반복하면 최소의 공급량을 return하게 된다. 처음에 힙큐의 원소를 꺼내서 stock에 더해주는 과정해서 한번 시행하면 heapq를 리셋시켜줘서 답이 안나왔다. 생각을 잘 못했던것 같다.(이왕 공급을 받을거면 무조건 제일 많은량을 받는게 맞다->힙을 초기화시키면 큰 값이 사라지는 경우가 있다 라는 생각을 간과했다.) 이런식의 풀이를 생각해내는게 상당히 까다로웠고 다시한번 heapq를 배울수 있었다. 더보기 [프로그래머스(Programmers)/Level2](Python) 타겟 넘버 itertools에서 제공하는 product를 사용하기위해 가능한 모든값(양수 또는 음수)를 하나에 리스트에 담아 리스트의 원소들로 쭉 넣어놓고 product를 사용하여 모든 경우의 수를 리스트에 담은 뒤, 각각의 리스트들을 합치고 타겟넘버에 해당하는 수의 갯수를 세어줘서 리턴한다. 처음에 재귀를 이용한 dfs로 풀려다가 사소한 실수들 때문에 오류가나서 구글링을 하던 도중 product라는 것을 찾아 사용했다. python에서의 *,map에 대해 좀더 심도있게 공부할 수 있었던 문제다. 더보기 [프로그래머스(Programmers) Level2](Python) 위장 dict를 만들어서 옷의 종류별로 갯수를 넣는데 dic.get(a,b) 라는건 a가 key인데 dict안에 이 a라는 키의 value가 존재 하지 않으면 b를 리턴해주겠다. 라는 뜻이고 이를 이용해 for문 한바퀴를 돌면서 종류별로 갯수를 담은 뒤, value들에 1을 더한 값(해당 종류의 옷을 안 입을수도 있기 때문에) 을 곱해주고 마지막에 -1한 값을 return해준다.(완전 발가벗은 경우는 없기 때문에) 비교적 간단한 문제였다. 이문제 역시 꼼꼼히 조건을 읽어보면 쉽게 해결할 수 있는 문제인 것 같다. 더보기 [프로그래머스(Programmers)/Level2](Python) 구명보트 정렬을 한 뒤, 리스트의 맨 앞원소랑 맨 뒤의 원소를 더해준 값이 limit을 초과하면 뒤의 값만 빼주고 count증가, 초과하지 않으면 앞 뒷 값을 모드 빼주고 count증가를 시켜준다.(시간복잡도를 고려해서 deque를 사용) len(q)가 1일땐, 예외적으로 빼주고 카운트를 증가시켜주고 종료한다.(보트의 limit은 사람몸무게 최대값 보단 크기 때문에 별다른 조건없이 풀린다.) 비교적 쉬웠고, 이전 문제에서 다뤘던 deque를 복습할 수 있어서 좋았던 문제다. 더보기 [프로그래머스(Programmers)/Level2](Python) 숫자 야구 숫자3개로 만들수 있는 전체순열을 Permutation으로 만들고 하나씩 주어진 숫자들+스트라이크횟수+볼횟수 와 비교하며 다르면 전체 순열에서 제거하는 식으로 문제를 풀었다. 위의 코드는 비교해서 strike와 ball횟수가 같으면 True를, 다르면 False를 리턴하는 check함수의 코드와 main함수에서 그 결과를 바탕으로 False는 제거한다. 전역탐색으로 쭉 반복하면 결국 리스트에는 조건과 맞는 수 들만 남게 된다. for문을 돌면서 리스트의 길이가 점점 줄어들때, all_numlst[:]이런식으로 :가 없으면 에러가 난다는 사실을 깨달았고, 이 문제를 어떻게 코딩할지 정말 막막해서 이게 정답일까? 하고 풀었더니 맞았다. 때로는 무식한방법이 적용될 때도 있다는 사실을 깨달았다. 추가로 구글링 .. 더보기 [프로그래머스(Programmers)/Level2](Python) H-Index 총 몇편의 논문이 있는지가 제일 중요하므로 논문 편 수를 높은 순으로 하나씩 줄여가며 각각의 논문들이 논문의 편 수 이상이면 count를 늘려주고 만약 count가 _max를 넘어가면 H-Index가 최대가 되므로 리턴하면 알맞은 답이 나온다. 처음에 문제이해를 잘못 해서 인용 횟수를 기준점으로 두고 풀었는데, 논문의 갯수를 기준으로 잡고 푸니까 (어차피 논문 갯수와 인용횟수 둘 다 조건에 필요한 사항들인데 논문의 갯수가 훨씬 적을 가능성이 높으므로) 잘 풀렸다. 항상 잘 풀리지 않으면 다른 방법을 생각하는 연습을 해야겠다고 느꼈다. 더보기 이전 1 2 3 4 5 6 7 다음
