Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- airflow.cfg
- 가상환경
- Django
- 데이터베이스
- airflow
- TCP
- 데이터 파이프라인
- sql
- dockerfile
- 종류
- 정리
- http
- Docker
- 데이터 웨어하우스
- 파이썬
- linux
- AWS
- PYTHON
- 데이터 엔지니어링
- 데브코스
- TIL
- 운영체제
- 컴퓨터네트워크
- S3
- Go
- HADOOP
- redshift
- 컴퓨터 네트워크
- 자료구조
- 데이터엔지니어링
Archives
- Today
- Total
홍카나의 공부방
[DE 데브코스] 04.15 TIL - 팀미팅 1차, 반성.., 코딩테스트 문제 풀이(Heap, DFS/BFS, DP) 본문
Data Engineering/프로그래머스 데브코스
[DE 데브코스] 04.15 TIL - 팀미팅 1차, 반성.., 코딩테스트 문제 풀이(Heap, DFS/BFS, DP)
홍문관카페나무 2023. 4. 15. 17:46토요일은 딱히 TIL을 작성하지 않아도 되는 날이나,
평일에 학습 시간이 부족했기 때문에 주말을 이용해서 추가 학습을 진행했다.
멘토님의 이야기와 팀 미팅 1차
- 멘토님께서 본인이 DE로 취직하시기 전에 하루 루틴, 취업 준비 과정, 코테 대비 등에 대한 경험을 말씀해주셨다.
- 확실히 공부 시간을 고3 처럼 정말 많이 가져가셨다. 나는 반성해야겠다.(1)
- 그리고 고3 마냥 정해진 시간에 공부하고, 운동하고, 취침하는 루틴을 충실히 세우셨다.. 또 반성해야겠다.(2)
- <빅데이터를 지탱하는 기술>, <데이터 파이프라인 핵심 가이드> 등의 책도 추천해주셨다.
- 가장 중요한 공부는 CS 기본기라고 강조해주셨다. 티스토리에 네트워크-OS 정리하다가 말았는데 반성해야겠다.(3)
- 짧은 시간이었지만 반성에 반성에 반성을 하는 계기.. 좀 더 치열함을 가지고 여유를 놔줘야겠다.
Heap 문제 풀이
- 프로그래머스의 <더 맵게> 라는 Lv.2 Heap 문제를 풀이했다.
- (해설을 듣기 전) scoville을 오름차순으로 정렬하고, 앞에 원소가 K보다 작다면 popleft()로 2개 뺀다음에 섞은 음식으로 만든다.
- (해설을 듣기 전) 섞은 음식은 list를 탐색하여 적절한 위치에 넣는다.
- (해설을 듣기 전) 앞에 원소 체킹 반복.
- (해설을 듣기 전) len(scoville)이 2보다 작은데, K값 보다 원소가 작다면 return -1
- 위는 O(n^2)로 시간초과 나기 딱 좋다. min Heap을 이용한 알고리즘을 생각해보자.
- 힙의 삽입, 삭제 연산과 필요에 따라서 heap[0], heapify 등을 이용하면 되겠다.
- 힙의 삽입, 삭제 연산은 O(log N)의 시간 복잡도를 가지고, heapify는 O(N log N)이 든다.
- 이 문제는 힙을 이용하여 최소 값을 꺼내고, 최소 값이 K보다 크거나 list의 길이가 0이 될때는 예외처리.
- 그렇지 않으면 2번째 수도 pop으로 꺼내서 새로운 원소로 만들고 이를 heap으로 넣는다.
- 이를 쭉 반복한다. ( 반복문의 종료 조건은 min > K 거나, len(list) == 0이다. )
- 위 힙을 이용한 풀이는 O ( N log N ). -> heapify 연산이 지배한다.
- 문제에 대한 답안 코드는 다음과 같다.
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while True:
# heap을 이용해서 최소값을 꺼낸다.
min1 = heapq.heappop(scoville)
if min1 >= K:
break
elif len(scoville) == 0:
answer = -1
break
min2 = heapq.heappop(scoville)
newval = min1 + min2 * 2
heapq.heappush(scoville, newval)
answer += 1
return answer
DFS/BFS
- 프로그래머스의 <여행경로> 라는 Lv.3 탐색 문제를 풀이했다.
- 내가 제일 좋아하는 유형이다. DP처럼 점화식 생각하느라 머리가 빠지지도 않는다. 쉽게 말하면 만만하다.
- DFS는 보통 stack을 이용할 수 있고, BFS는 Queue를 이용해서 풀이할 수 있다.
- 위 문제는 모든 간선을 거치는 것이 핵심이다. 모든 정점 방문이 아니고.
- 그래프는 사전을 이용하여 각 노드에서 출발하는 엣지의 집합을 표현할 수 있다.
- 예시로 { ICN : [ATL, SFO], ATL : [ICN,SFO] } 이런식으로..
- 단, 리스트의 경우 뒤에서부터 제거하는게 좀 더 효율적이므로, 알파벳의 역순으로 정리한다.
def solution(tickets):
dic = {}
for t in tickets:
dic[t[0]] = dic.get(t[0], []) + [t[1]]
for d in dic:
dic[d].sort(reverse=True)
print(dic)
#DFS
stack = ["ICN"]
answer = []
while len(stack) > 0:
top = stack[-1]
if top not in dic or len(dic[top]) == 0:
answer.append(stack.pop())
else:
stack.append(dic[top][-1])
dic[top] = dic[top][:-1]
return answer[::-1]
다이나믹 프로그래밍(DP)
- 프로그래머스의 <N으로 표현> 이라는 Lv.3 DP 문제를 풀이했다.
- 부분해가 전체 문제의 해가 되는 알고리즘이다.
- 피보나치 수열을 구하는 문제들이 보통 DP로 구현하는 대표적인 유형이다.
- 피보나치 문제를 재귀로 구현하면 200% 시간초과가 발생하기 때문에 ex) f(100) = f(99) + f(98) : 지수시간
- 다이나믹 프로그래밍으로 divide and quanquer 방식을 이용하곤한다.
- f(0) = 0, f(1) = 1, for i in range(2:N+1): f(i) = f(i-1) + f(i-2) 와 벌써 쉽다!
- 다이나믹 프로그래밍을 적용한 알고리즘은 복잡도가 선형함수의 형태로 나타난다. (기껏해봐야 O(N))
공부하며 어려웠던 내용
- 여전히 알고리즘 문제 풀이에서 좀 더 효율적인 최적의 알고리즘을 찾아내는건 쉽지 않게 느껴진다.
- DFS/BFS는 나에게 익숙한 유형임에도 불구하고 lv.3 문제는 풀이법을 스스로 생각해내지 못했다.
- 특히 재귀를 이용한 DFS에 익숙한 나머지 스택 방법을 이해하는데 시간이 좀 걸렸다.
반응형
'Data Engineering > 프로그래머스 데브코스' 카테고리의 다른 글
[DE 데브코스] 04.18 TIL - 웹 스크래핑을 위한 HTTP 기초 (0) | 2023.04.18 |
---|---|
[DE 데브코스] 04.17 TIL - HTML (0) | 2023.04.17 |
[DE 데브코스] 04.14 TIL - ChatGPT 특강, 코딩테스트 연습(Hash, Greedy, Sort) (0) | 2023.04.14 |
[DE 데브코스] 04.13 TIL - Queue, PQ, Tree, Binary Tree, BST, Heap (0) | 2023.04.13 |
[DE 데브코스] 04.12 TIL - 자료구조 中 정렬, 탐색, 재귀 기초, Linked List, Stack, 후위 표기식 (2) | 2023.04.12 |