코테 유형 분석하기(DFS, BFS, 스택, 큐, 힙, DP..)

시간복잡도는 매우 중요하다.
문제에서 주어진 N을 문제의 힌트라고 생각하기!

DFS

• 삼성 역량테스트에 가장 많이 출제됨
• 사이클이 존재할 경우
• 한 가지 정점과 연결된 모든 정점을 탐색하는 경우(일반적인 DFS 알고리즘 사용)
• 이동할 때마다 가중치가 붙을 때는 DFS로 구현하기
• DFS는 해에 도착하면 탐색을 종료하기 때문에 최단 경로라는 보장이 없다. 최단 경로는 무조건 BFS!

=> x를 루트로 하는 트리에서, x의 모든 자식값을 더해주는 함수

=> visited 배열을 자주 사용하는데, 예를 들어 graph[1][2] 가 있을 때 1에서 2를 방문했다면, 2에서 1을 방문하는 것을 방지하고자 할 때 사용한다. 만약 방지하지 않는다면, 무한루프가 발생할 수 있다. 단방향이라면 할 필요는 없다.

 

BFS

• 재귀를 사용하지 않는다.
• 최단 경로를 이용하는 문제에 사용한다.
• 답이 되는 경로가 여러 개라고 하더라도 최단 경로를 보장한다.
• 해가 반드시!! 존재해야 한다. 해가 없다면 끝내지도 못한다.
• queue보다 deque를 사용하는 것이 더 좋다. (시간 복잡도를 위해서)
• pop()은 끝까지 다 확인을 한 후 빼주니까 시간복잡도가 O(n)이고, popleft()는 왼쪽에서 바로 한 개를 빼면 돼 O(1)이다. → 최대한 popleft 사용하기!

while queue:
	현 위치 = popleft()
    
    for i in range(n): (다음 노드 가져와서)
    	다음 노드가 조건(방문 안했거나, 문제 조건)에 맞으면 :
        queue.append(다음 노드)

 

스택 & 큐

• 구현할 때 자주 사용되는 자료구조(스택 : DFS, 큐 : BFS)
• 선입선출, 후입선출

stack =[1,2,3]
top = stack[-1]

스택에서 원소를 제거하지 않고, top에 있는 원소만 가져오고 싶을 때 이렇게 선언할 수 있다.

파이썬에서 스택을 사용할 때는 별도의 자료형이 필요없이 list로 사용 가능하다.

 

힙

• 우선순위를 고려할 때 사용되는 자료구조(큰 수부터..)모든 과목의 점수를 A 이상으로 만들기 위해 추가해야 할 과목의 최소 횟수를 RETURN

 

다이나믹 프로그래밍

• 점화식과 비슷함
• Bottom-up, Top-down
• N이 커서 시간초과가 발생할 때 사용하는 알고리즘

 

브루트포스(완전탐색)

• 모든 경우를 다 탐색하는 알고리즘
• DFS, BFS를 같이 공부해놓으면 좋음
• 빈출 문제 : 미로찾기

 

이분탐색(파라메트릭 서치)

• 카카오에서 자주 출제하는 유형
• 시간초과 나면 이분탐색으로 접근하기
• 정렬이 되어 있는지 먼저 확인할 것! 정렬이 안 되어 있다면 정렬부터 해주기!

 

유니온 파인드

• 집합에 노드를 포함하는 Union 연산
• 노드의 루트 노드를 찾는 Find 연산

 

투 포인터, 슬라이딩 윈도우

• 배열 문제를 해결하는 동안 인덱스 2개를 사용할 때 이중 for문을 사용하면 시간 초과가 나는 경우가 있음. 이럴 때 사용할 수 있는 알고리즘
• while문 하나만 사용하기 때문에 시간 초과 해결할 수 있음

 

투 포인터

• 2개의 포인터를 사용
• start와 end 포인터 두 개를 두고, 조건에 맞춰 end ++1, start ++1 하는 방법
• 유형은 크게 두 가지임(대상이 되는 배열이 1개 / 대상이 되는 배열이 2개)