Problem Solving 🔥/프로그래머스

Problem Solving 🔥/프로그래머스
[프로그래머스] 무지의 먹방 라이브 / 우선순위 큐(힙)
https://programmers.co.kr/learn/courses/30/lessons/42891# 우선순위 큐 문제입니다. 예를 들어 foods_time이 [3, 4, 5, 6, 7, 8, 9, 10] 이라고 해봅시다. 이 정보만 주어졌을 때 가장 작은 값인 3, 그리고 배열의 길이 7 이니 21초 후에는 [1, 2, 3, 4, 5, 6, 7] 이 됨을 알 수 있겠죠? 즉 N초(가장 작은 값 x 배열의 길이)후의 결과를 가장 작은 값, 배열의 길이로 알 수 있는 것입니다. 그리고 가장 작은 값 => 우선순위 큐 임은 알고리즘을 조금 풀어보신 분들은 쉽게 눈치채셨겠죠?? 가장 작은 값 x 배열의 길이로 계속 점프를 해줍니다. 그런데 이 값이 이제 K초 후를 넘어가는 경우 멈춰줍니다. 그 때부터는 모듈..
→2021.05.03
Problem Solving 🔥/프로그래머스
프로그래머스 / 2018 KAKAO 자동완성 / 파이썬 / 트라이
programmers.co.kr/learn/courses/30/lessons/17685 Trie 자료구조를 안다면 쉬운 문제이고 모르면 어려운 문제입니다. Trie 자료구조를 조금 변형하여 쉽게 구현할 수 있었습니다. Trie에 cnt를 추가해주면 쉽게 풀 수 있습니다. cnt는 같은 루트를 공유하는 경우를 나타냅니다. cnt가 1이라면 더 이상 찾아볼 이유가 없습니다. 그리고 cnt는 문자열 길이를 넘을 수 없음에 유의합니다. class Trie: def __init__(self): self.root = Node() def insert(self, s): node = self.root for c in s: if c in node.child: node.child[c].cnt += 1 else: node.c..
→2021.05.03
Problem Solving 🔥/프로그래머스
[프로그래머스] 매출 하락 최소화 / 파이썬 / DP
programmers.co.kr/learn/courses/30/lessons/72416 확실히 어렵네요.. 개인적으로 2021 카카오 문제중 가장 어려웠고, 알고리즘 공부를 열심히 해야겠다고 느꼈던 문제입니다.. DP문제인데, 생각보다 구현방법이 잘 안떠올라 답안을 보았습니다. 우선 Root는 1번이니, 1번부터 탐색을 시작합니다. 케이스는 두가지 입니다 1) dp[n][1] => n번 사람이 선발되는 경우 2) dp[n][0] => n번 사람이 선발되지 않는 경우 1번 케이스의 경우에는 쉽게 생각할 수 있는데요. n번의 매출액을 더하고 n번의 자식들이 선발이 되든, 안되든 최소값만 선택하면 됩니다. 2번 케이스의 경우 조금 까다롭습니다. n번의 매출액을 더하지 않고, n번의 자식들이 선발이 되든, 안되..
→2021.05.02
Problem Solving 🔥/프로그래머스
[프로그래머스] 실패율 / Python
크게 어려운 부분은 없는 문제였습니다. 정렬 후 이진탐색을 통해 쉽게 풀 수 있는 문제입니다. programmers.co.kr/learn/courses/30/lessons/42889# 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr from bisect import bisect_left, bisect_right def solution(N, stages): answer = [] P = len(stages) # 사람 수 stages.sort() for i in range(1, N+1): idx1 = bisect_..
→2021.04.07
Problem Solving 🔥/프로그래머스
[프로그래머스] 순위 검색 / Python
https://programmers.co.kr/learn/courses/30/lessons/72412# 효율성 부분에서 어려운 문제였습니다. 이진탐색을 떠올려야 하고, 이진탐색을 하려면 Value값을 모두 정렬해야하는데, 역시 오랜만에 풀려니 오랜시간이 걸렸습니다. 한 유저당 4가지 정보를 가지고 있으니 한 유저는 2^4으로 총 16개의 Query에 속합니다. 이 Query를 정렬한 후, 이진탐색으로 풀면 되는 문제였습니다. 코테를 볼 때 이런 문제를 보면, 효율성 부분 개선을 하려면 코드를 전부 바꿔야 해서, 멘탈이 흔들릴 수 있겠네요. 생각을 많이하고 문제풀이 시작을 하는 습관을 길러야겠습니다. from bisect import bisect_left, bisect_right from collectio..
→2021.04.06
Problem Solving 🔥/프로그래머스
[프로그래머스] 쿠키 구입 / 파이썬
https://programmers.co.kr/learn/courses/30/lessons/49995 은근히 까다로운 문제였다. 결국 고민을 얼마 안하고 정답을 보긴 했다.. 당연히 누적합 문제인 줄 알았는데, 누적합이라고 보기는 조금 애매한 코드가 가장 효율적인 코드였다. 알고리즘은 투포인터에 가깝다고 보면 될 것 같다. 풀이 방법은 하나의 기준 점을 정하고, 동생과 형이 그 기준 점으로부터 쭈욱 더해 나가는 것이다. 동생의 쿠키가 더 많으면, 형의 쿠키를 증가 형의 쿠키가 더 많으면 동생의 쿠키를 증가.. 반복한다. def solution(cookie): answer = 0 for i in range(len(cookie)-1): left, right = i, i+1 lsum = rsum = 0 lfl..
→2021.02.22
Problem Solving 🔥/프로그래머스
[프로그래머스] 3 x n 타일링 / 파이썬
programmers.co.kr/learn/courses/30/lessons/12902# 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr 처음에는 너무 쉽게 생각했다. 처음 생각한 점화식은 dp[i] = dp[i-2] * 3 + dp[i-4] * 2 였다. 하지만 오답이 난 순간 무언가를 빼먹었나 라는 생각을 하게되었고, 나름 쉽게 규칙을 찾을 수 있었다. 우선 n이 홀수인 경우를 생각해보자 3 x 홀수 => 홀수 이다. 즉 홀수인 경우는 홀수가 나오므로, 길이가 2인 타일들로는 채우는 것이 불가능함이 자명하다. 짝수인 경우를 생각해보자. 짝수를 n이라고 가정해보자. 우선 2개로 만들 수 있는건 그려보면 3개가 나온다. 그러니 n-2개로 만들 수 있는 수 * 3으로 만들 수 있다. ..
→2021.02.16
Problem Solving 🔥/프로그래머스
[프로그래머스] 지형 이동 / 파이썬 / MST(최소신장트리)
programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 예전에 백준에서 풀어본 문제랑 비슷해서, 크게 어렵지는 않았습니다. 어렵지는 않은데, 구현이 조금 귀찮은 문제라고 볼 수 있겠네요. 우선 문제 예시에 있는 그림에서 쉽게 힌트를 찾았는데, 바로 이동할 수 없는 영역간의 구분입니다. 저는 이를 대륙(land)이라고 표현했습니다. 그리고 각각의 대륙마다, 번호..
→2021.02.14
Problem Solving 🔥/프로그래머스
[프로그래머스] 하노이의 탑 / 파이썬
https://programmers.co.kr/learn/courses/30/lessons/12946# 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대 programmers.co.kr 재귀함수를 처음 배웠을 때, 백준에서도, 종만북에서도 보았던 하노이의 탑 문제입니다. 하지만 1~2년만에 다시 보니, 또 어떻게 푸는지 감이 안오더라구요.. 고민하고.. 고민하고.. 고민하다가 풀었습니다 ㅠㅜ 개인적으로는 어려운 문제라고 생각합니다.. 재귀함수를 의미론적으로 접근해야했습니다. from으로부터 to까지 (n)개의 원판을 넘..
→2021.02.12
Problem Solving 🔥/프로그래머스
[프로그래머스] 길 찾기 게임 / 파이썬 / 자료구조(트리)
https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 풀이 자료구조를 적절히 사용하는지를 묻는 문제였던 것 같다. 이진트리를 한 번 구현해 본 경험이 있으면 쉽게 풀 수 있는 문제였다. 우선 높이별로 한 번 정렬을 한 다음에, 이진트리에 계속 추가하는 형식으로 문제를 풀었다. 딱히 설명이 필요없을 듯 하다.. import heapq as h import sys sys.setrecursionlimit(100000) a..
→2021.02.12

• 이전
• 1
• 2
• 3
• 4
• 다음