[AI class day 4] 파이썬 코딩테스트 문제 풀이 TIL

*3일차에 이어서 알고리즘 문제 풀이를 하고 있다.

2번 문제 같은 경우에는 너무 어렵게 느껴졌다.

다른 문제들은 몇 가지 중요한 key point만 잡으면 풀 수 있겠다 싶었는데, 2번 문제의 경우는 해설과 모범 답안을 보고도 헤매는 느낌.

--> 기본기가 너무 없는 것 같아서 <파이썬 알고리즘 인터뷰> 라는 책을 사서 읽고 있는 중인데, '다이내믹 프로그래밍'은 복잡하고 어렵다는 구절이 나왔다. 내가 헤맨 2번이 바로 다이나믹 프로그래밍. 지금 이해 못하더라도 조금 위안을 얻었다. 일단 넘어가고 좀 더 쉬운 것들 부터 이해하려고 노력하려 한다.

 

1. 힙 Heap 대표 문제 풀이 : 더 맵게

힙은 특정 특성을 가지고 있는 완전 트리의 한 종류 (최대 힙/ 최소 힙)

 

참고 : 힙 정리 

 

*섞어서 새로운 음식을 만들어 내는 공식이 있는데, 모두 섞어봐도 원하는 수가 되지 않으면 -1를 리턴한다.

--> 모두 섞는 경우 --> (n-1)회 반복해야 한다

--> 섞을 때 마다 정렬도 해야 한다 --> O(n)

--> 섞고 정렬까지 하면 문제의 복잡도 --> O(n^2)

--> 최소/ 최대 원소를 빠르게 꺼내야 복잡도가 줄어든다 

--> 최소 힙 / 최대 힙 (힙의 삽입/삭제의 복잡도는 O(logN))

 

*참고 heapq

파이썬에서 힙을 이용할 수 있는 라이브러리

import heapq

 

#파이썬 힙 라이브러리 활용
import heapq
L= [3,1,4,2,6,8,9]
heapq.heapify(L) #리스트 L로부터 min heap 구성
m= heapq.heappop(L) # min heap L에서 최소값 삭제(반환)
m

>> 1

heapq.heappush(L,1.5) #min heap L에 원소 x 삽입
heapq.heappop(L)

>>1.5

2. 동적 계획법(Dynanmic Programming) 대표 문제 풀이 : N으로 표현

 

숫자 N을 최소로 써서 원하는 target의 숫자를 만드는 과제

--> 1회, 2회, 3회... 로 늘려가면서 시도한다

--> 1회 쓸 때 경우의 수, 2회 쓸 때 경우의 수, 3회 쓸 때 경우의 수를 구하는데

--> 3회의 경우에 수는 (1회 (4칙연산) 2회) + (2회(4칙연산)1회) 이다

 

 

 

 

 

*참고 동적 계획법이란?

• 주어진 최적화 문제를
  • 재귀적 방식으로 보다 작은 부분의 문제로 나누고
  • 부분 문제를 풀고 이 해를 조합하여
  • 전체 문제의 해답에 이르는 방식
  • 알고리즘의 진행에 따라 탐색해야할 범위를 동적으로 결정 --> 탐색 범위 한정이 가능함

--> 동적 계획법 적용의 예 

ex> 피보나치 수열

f(0) = 0 f(1) = 1

f(2) = f(1) + f(0) = 1

f(3) = f(2) + f(1) = 2

...

복잡도는 선형함수의 형태가 된다

 

ex> 배낭 문제 

매우 널리 알려진 DP 문제라고 한다.

꼭 풀어봐야겠다.

 

3. 깊이/ 넓이 우선 탐색 (DFS / BFS) 대표 문제 풀이 :  여행경로

 

사실 한붓 그리기 문제이다.

-> 깊이 우선 탐색을 응용해서 푼다

-> 이 문제는 한붓 그리기가 가능함을 보장하고 있다

-> 시작은 항상 ICN

-> 모든 정점 방문이 아니라 모든 간선 지나게 하고 그 순서를 결정하는 과제

-> 한 정점에서 선택할 수 있는 간선이 두개면 ? 알파벳순

-> 한 번 갔던 간선은 지워가면서 진행 (재귀적인 한붓 그리기)

-> 스택은 파이썬 리스트를 활용해서 구현(리스트[-1]을 .pop()하면 LIFO 구현 가능

 

참고 : 깊이/ 넓이 우선 탐색 정리

 

* 배경지식 DFS & BFS

• 그래프 (트리는 그래프의 한 종류다)
  • 정점vertex, node과 간선edge, link
  • 유향directed 그래프와 무향undirected 그래프 (트리는 directed graph)
  • cyclic graph와 acyclic graph
• 스택 stack
• 큐 queue
• 깊이 우선 탐색 (DFS)
  • 한 정점에서 인접한 모든(아직 방문하지 않은) 정점을 방문하되, 
  • 각 인접 정점을 기준으로 깊이 우선 탐색을 끝낸 후 다음 정점으로 진행
  • 재귀적 성질
  • 스택 이용
  • 스택을 이용하여 어느 정점에서 DFS를 하고 있는지 기억하고 되돌아 감
• 넓이 우선 탐색 (BFS)
  • 한 정점에서 인접한 모든(아직 방문하지 않은) 정점을 방문하고
  • 방문한 각 인접 정점을 기준으로 방문한 순서에 따라 또다시 너비 우선 탐색을 진행
  • 큐 이용 
  • 큐를 이용하여 어느 정점에서 BFS를 해야 하는지 기록하고 진행함

이해를 돕기 위한 유튜브 영상

 

1. 그래프

www.youtube.com/watch?v=fVcKN42YXXI

 

2. DFS와 BFS

www.youtube.com/watch?v=_hxFgg7TLZQ

www.youtube.com/watch?v=oDqjPvD54Ss

 

 

큐로 작동하는 방식을 그림으로 보여줘서 이해하기 쉬웠다.

 

www.youtube.com/watch?v=7fujbpJ0LB4