Skip to content

Latest commit

 

History

History

TypeofCodingTest

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 

README.md

Type Of CodingTest

코딩테스트를 유형화해보자(순서는 나동빈님의 유형분석 차트 차용 _ 최다 빈출 순서로)

1. 구현

문제의 요구사항을 주고 프로그램을 작성하시오
모든 경우의 수를 다 계산하시오

파싱, 해싱, 정렬, 시뮬레이션...

  • 목적: 문제 조건을 코드로 작성하여 잘 돌아가냐를 판단
  • 코테에서 구현이란?
    • 문제 상황과 일대일 매칭
    • 보다 효율적으로 짜야하는 것을 목표
    • 최적화와 알고리즘 등 복잡한 코드도 이용할 수 있음

2. BFS, DFS

BFS: 그래프 안에서 움직여야 할 최소 칸의 개수 DFS: 그래프 안에서 묶음을 찾아 탐색

탐색

  • 목적: 특정 조건을 만족하는 상태를 찾기위해 적절한 코드를 작성할 수 있는가

  • 특징

    • BFS: Queue
    • DFS: Recursion(주로 이거 씀) or Stack

  • 핵심: 구현에 초점

    • 부분 상태 탐색(위치 이동_방향벡터, 수) -> 현재 상태 체크
    • 전체 상태 탐색(map) -> N차원 배열 조절
    • Flood Fill = 한붓그리기
    • 트리 순회

  • 알고리즘에 초점

    • 위상정렬
    • 최소신장트리
    • 최단거리

2.1. 방햑벡터

상하좌우, 대각선, 체스 이동..

  • 목적: 좌표선상에서 이동할 때 판단
  • 특징
    • 2차원 또는 3차원
    • 좌표를 생성한 뒤 DFS, BFS
    • x좌표 이동: dx = [-1, 1, 0, 0], y좌표 이동: dy = [0, 0, 1, -1]
dx, dy = [0,-1,0,1], [1,0,-1,0]

x+= dx['ENSW'.index(way)]
y+= dy['ENSW'.index(way)]

for i in range(4):
    dfs(x+dx[i], y+dy[i])

3. Greedy

탐욕 알고리즘

가장 큰, 작은 순서대로

미래 예상 X, 지금 당장 좋은 것만 고르는 것

  • 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형
  • 특징
    • 주로 정렬 알고리즘과 같이 나옴
    • 문제 풀이를 위한 최소한의 아이디어를 도출 후 이것이 정당한지를 검토해야함.
    • 문제 유형을 파악하기 어렵다면 의심해봐야할 알고리즘

4. DP

반복되는 행동과 앞에 계산한 것이 다시 쓰이는 경우들..

동적계획법

  • 목적: 다음 상태를 저장하고, 사용하는 방식(메모이제이션)

  • 무엇을 저장하고 어떻게 저장해야하는가..

  • 푸는 순서

    1. 상태를 정의한다.(초기상태 초기배열 등등)
    2. 점화식을 찾는다(구한다.)
    3. 시간복잡도를 계산한다.
    4. 코딩한다.

  • 푸는 방식

    • Bottom-Up(반복문): 주로 초기화 후 데이터를 저장하면서 나가는 방식을 사용
    • Top-Down(재귀)
    • 시간복잡도는 수가 클 경우 재귀는 위험

  • 사실상 점화식만 찾으면 간단해짐

5. 정렬

~~~하게 정렬하시오.

어쩌면 가장 기본적인..

  • 유형
    • 시간복잡도가 널널X : QuickSort
    • 시간복잡도가 널널: list.sort()
    • 커스텀 정렬
  • 보통은 sort, sorted 쓰면 다 풀림
  • sorted(정렬할 배열, reverse=True or False, key = lambda x:x[1]_ 정렬할 기준)
    • 정렬할 기준이 생기면 (튜플이나 이중 배열에서 N번째 기준) 추가하면 쉬움
  • 시간초과가 나오면 그때부터 quickSort

6. 이진탐색

찾아보고 있으면 yes 없으면 no

선형탐색 중 시간복잡도가 낮음, 반으로 쪼개면서 탐색

  • 가급적이면 코드를 외우기
  • 순차정렬이 되었을 때만 사용가능
  • 같은 숫자가 있는지 판단은 set()으로 판단
  • 재귀 VS 반복문 : 맘대로 but 코드 간결은 반복문

7. 최단경로

Greedy + Dynamic Programming

다익스트라 알고리즘

한 도시에서 다른 도시까지의 최단거리

한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우

  • 순서
    1. 출발노드를 설정한다.
    2. 최단 거리 테이블을 초기화한다.
    3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
    4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
    5. 3, 4 를 반복하여 가능한 모두 방문하도록 한다.
  • 특징
    • 주로 한 방향 그래프일 때가 많음
    • 최단 경로를 현재 저장된 거리와 비교 후 갱신(매번 가장 비용이 적은 노드를 선택)
    • 최소 힙 구조를 이용해 저장(O(ElogV)를 보장)
    • 도착한 해당 노드가 이미 처리됐다면 그냥 넘어감
    • 보통은 최단 거리 테이블, 그래프 연결정보를 담는 테이블, 힙큐를 생성하여 데이터를 넣고 빼는 작업을 진행
    • 저장 공간을 조절: import sys -> input = sys.stdin.readline

플로이드 워셜 알고리즘

1번 노드에서 X를 거쳐 K로 가는 최단거리 (1->X 최단거리 + X->K 최단거리)

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

  • 특징
    • 3중 반복문을 씀(O(N^3))
    • 2차원 리스트에서 모든 경우의 수를 고려하여 넣어짐
    • graph[a][b] = min(graph[a][b], graph[a][k]+graph[k][b])

8. 그래프이론

Union-Find

사이클 판별

  • 순서
    1. 각 간선을 확인하며 두 노드의 루트 노드를 확인
    • 루트 노드가 서로 다르면 Union
    • 같다면 Cycle발생
    1. 모든 간선에서 1번 반복
  • 특징
    • 방향성이 없는 무방향 그래프에서 사용
    • 서로소인 집합 확인
    • 루트 노드를 연결 연결하여 최소의 집합으로 분류

Spanning Tree

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

  • 크루스칼 알고리즘: MST를 찾기위한 알고리즘

Toppology Sort(위상 정렬)

  • 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것

  • 선수과목을 고려한 학습 순서 설정

  • 순서

    1. 진입차수가 0인 노드를 큐에 넣는다
    2. 큐가 빌 때까지 반복
    • 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
    • 새롭게 진입차수가 0이 된 노드를 큐에 넣음

  • 사이클이 발생하지 않음