Please enable JavaScript.

Coggle requires JavaScript to display documents.

이것이 코딩 테스트다 - Coggle Diagram

- - - - 일종의 점화식
  - - - 큰 문제를 해결하기 위해 작은 문제 호출
        
        예: 재귀식 피보나치
        
        기법
        
        메모이제이션(memoization)
        
        한 번 구한 결과를 메모리 공간에 메모 후 다시 호출하여 가져오는 기법. 동의어: caching(캐싱)
        
        다이나믹 프로그래밍외에도 다양하게 쓰이며, list, dict 등 다양한 자료형으로 쓰임
        
        dict의 경우 비연속적 자료형에 주로 쓰임
        
        저장용 리스트를 memoization
    - - 작은 문제부터 차근차근 답 도출
        
        예: 반복문 피보나치
      - 다이나믹 프로그래밍의 일반적인 실행방식
        
        재귀 호출회수의 한계와 리소스 사용량(오버헤드)때문에 권장됨
      - 저장용 리스트를 DP table
  - - - $$ a_{n} = a_{n-1} + a_{n-2}, a_1 = 1, a_2 = 1 $$
      - 재귀식 피보나치
        
        시간복잡도
        
        $$ O(2^n) $$
        
        다이나믹 적용시
        
        $$ O(n) $$
  - - - 다이나믹 유형을 알아보는 것이 중요
        
        완전탐색으로 접근시 오래 걸리면 다이나믹
    - - 재귀로 만든 뒤, 메모이제이션 적용이 쉬운 접근
        
        호출 한계를 증가시켜 재귀한계 완화
        
        import sys strecursionlimit()
      - BottomUp방식으로 짜진다면, BottomUp으로 짤 것
    - - 1로 만들기
      - 바닥공사
        
        타일링 문제
      - 개미전사
      - 효율적인 화폐구성
- - - - 시뮬레이션 문제
    - - 완전 탐색 문제
        
        일반적으로 데이터개수가 100만개 이하다.
    - - 시뮬레이션 문제
    - - 시뮬레이션 문제
- - - - 스택
        
        선입후출 구조
        
        파이썬에서는 리스트로 구성 후 append(), pop()을 이용하여 구현 가능
      - 큐
        
        선입선출 구조
        
        파이썬에서 구현 시 별도의 라이브러리 이용
        
        from collections import deque
        queue = deque()
        
        리스트로 변형 가능
        
        list(queue)
      - 핵심 함수
        
        삽입
        
        오버플로
        
        삭제
        
        언더플로
  - - - 종료조건을 명시하여 무한재귀함수 방지
        
        파이썬에서는 무한 재귀함수를 최대 호출 횟수로 막는 제한조건이 있다.
        
        이를 스택을 이용한 함수처럼 동작하도록 변경해주는 라이브러리로 제한을 벗어날 수 있다.
      - 수행시 스택 자료 구조와 같이 선입후출방식
        
        스택자료구조 이용시 편리함(예: DFS)
  - - - 인접하다
        
        두 노드가 간선으로 연결 된 것
    - - 인접 행렬( Adjacency Matrix)
        
        2차원 배열로 그래프의 연결 관계를 표현하는 방식
        
        python에서는 2차원 리스트로 표현
      - 인접 리스트(Adjacency List)
        
        리스트로 그래프내 노드의 연결 관계만을 표현하는 방식
        
        python에서는 2차원 리스트로 표현
- - - - 시간만 충분하면 언제나 답을 찾음
      - 시간 복잡도
        
        $$ O(N) $$
      - 리스트 안 특정한 데이터를 찾기 위해 앞에서 부터 데이터 하나씩 확인
    - - 방법
        
        step1
        
        정렬 후 시작점 [0], 중간점 [len(array)//2], 끝점[len(array)] 정하고 준점과 찾는 값을 비교
        
        step 2
        
        찾는 값이 중간점보다 작은면 큰 부분(중간점부터 끝점)을 버리고(크면 작은 부분을 버리고), 작은 부분에서 중간 점 이전을 새로운 끝점으로 선정하고 새 중간점을 선정한다.
        
        step3
        
        찾는 값을 얻을 때까지 step1~step2를 반복한다.
      - 시간복잡도
        
        $$ O(\log N) $$
      - 특징
        
        배열 내부 데이터가 정렬되어 있어야만 사용 가능
        
        탐색범위를 절반씩 좁혀가며 탐색
        
        많이 이용되고 빠른 탐색법이니 코드 자체를 외우는 것을 권장
        
        탐색의 위치를 나타내는 3개의 변수(시작점, 중간점, 끝점)를 이용
  - - - 테이터베이스(RDMS) 정렬구조
        
        계층적이고 정렬된 데이터에 적합
      - 부모 노드, 자식 노드 형태
      - 최상단은 루트 노드
      - 최하단은 단말 노드
      - 일부 트리를 떼어내면 서브 트리
    - - 이진 탐색 트리
        
        특징
        
        1개의 부모 노드로부터 2개의 자식 노드가 존재
        
        크기 관계는 $$ 좌측 자식 노드 < 부모 노드 < 우측 자식 노드 $$
        
        탐색 과정
        
        찾는 값과 부모 노드의 크기를 비교하며(작으면 좌측, 크면 우측) 자식쪽으로 탐색
  - - - readline()이용 권장
        
        import sys
        sys.stdin.readline().rstrip()
  - - - 파라메트릭 서치(parametric search)
        
        전형적인 이진탐색 유형의 문제
- - - - 노드
      - 간선
    - - 인접 리스트
        
        공간복잡도
        
        $$ O(E) $$
      - 인접 행렬
        
        공간복잡도
        
        $$ O(V^2) $$
  - - - 최소힙
      - 분류
        
        수학
        
        무방향 그래프
        
        컴퓨터 공학
        
        방향 그래프
      - 신장트리
        
        하나의 그래프 내에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프(트리의 조건이기도 하다)
        
        최소신장트리 알고리즘
        
        크루스칼 알고리즘
        
        알고리즘
        
        간선 데이터를 비용따라 오름차순으로 정렬
        
        간선이 사이클을 발생시키는지 하나씩 확인
        
        사이클이 발생하지 않는 경우, 최소신장트리 포함
        
        사이클이 발생하는 경우 최소신장트리에 포함시지키 않는다.
        
        모든 간선에 2.과정 반복
        
        특징
        
        2 more items...
        
        시간 복잡도
        
        $$ O(E \log E) $$
        
        1 more item...
        
        최소비용으로 만들 수 있는 신장트리를 찾는 알고리즘
    - - 추가 개념
        
        서로소 집합
        
        공통원소가 없는 두 집합
      - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
      - 조작
        
        union(합집합)
        
        2개의 원소가 포함 된 집합을 합치는 연산
        
        find(찾기)
        
        특정한 원소가 어떤 집합인지 확인
      - 표현
        
        트리 자료구조
      - 알고리즘
        
        union 연산 확인
        
        A와 B의 루트노드 A, B를 각각 찾는다
        
        A를 B의 부모노드로 설정한다(B가 A를 가리키도록-일반적으로 더 작은 원소를 A`로 한다)
        
        모든 union(합집합)연산을 처리 할 때까지 1.과정을 반복
        
        이를 통해서 최종루트노드와 서로소 집합이 결정
        
        첫 구현 코드
        
        시간복잡도
        
        $$ O(VM) $$
        
        V는 노드 개수
        M은 union연산 개수
        
        시간 복잡도 개선 코드
        
        경로 압축 기법 적용
        
        시간복잡도
        
        $$ O(V + M(1 + \log_{2- \frac{M}{V}} V)) $$
      - 사이클 판별
        
        무방향 그래프 내에서
        
        알고리즘
        
        각 간선 확인, 두 노드의 루트노드 확인
        
        루트 노드가 서로 다르면, 두 노드에 대하여 union연산
        
        루트 노드가 서로 같다면, 사이클이 발생한 것
        
        그래프 내 모든 간선에 대해 1.과정 적용
        
        방향 그래프 내에서
        
        DFS 적용
  - - - 순서가 정해져 있는 일련의 작업을 차례대로 수행시 사용
      - 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'
    - - 진입차수
        
        특정한 노드로 들어오는 간선의 개수
    - - 진입차수가 0인 노드를 큐에 넣는다.
      - 큐가 빌 때까지 다음 과정 반복
        
        큐에서 원소를 꺼내 해당노드에서 출발하는 간선을 제거
        
        새로이 진입차수가 0이 된 노드를 큐에 넣는다
      - 큐에서 빠져나간 노드를 순서대로 출력
    - - 여러개의 답이 존재가능
      - 모든 원소를 방문하기 전 큐가 빌 경우, 사이클이 존재
        
        일반적인 위상정렬 문제에서는 사이클이 없다
        
        사이클이 발생하는 경우는 부록 참조
    - - $$ O(V+E) $$
        
        V는 노드, E는 간선
  - - - 서로소 집합 알고리즘
    - - 최소신장트리 문제
    - - 위상정렬 알고리즘 문제
- - - - 리스트 크기 제약
        
        1,000,000
        
        약 4MB
        
        10,000,000
        
        약 40MB
        
        1000
        
        약 4kb
    - - 2000만번 정도의 연산
        
        Pypy3 지원시 이용하여 향상가능
- - - - 탐색 시작노드를 스택에 삽입 후 방문 처리
        
        방문하지 않은 인접노드가 있으면 그 인접노드를 스택에 삽입 후 방문처리(일반적으로 낮은 번호부터 처리)
        
        방문하지 않은 인접노드가 없으면 이전 노드를 꺼낸다.
        
        전체 노드 중 방문하지 않은 노드가 없을 때까지 반복한다.
  - - - 탐색 시작노드를 큐에 삽입하고 방문 처리
        
        큐에서 노드를 꺼내 해당노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하여 방문처리(일반적으로 낮은 번호부터 처리)
        
        더 이상 수행 할 수 없을 때까지 반복
    - - 일반적인 경우 실제 수행시간이 DFS보다 짧다.
- - - - 퀵정렬(quick sort)
        
        피벗(pivot)
        
        교환을 위한 기준
        
        분할 방식
        
        호어분할(houre partition)
        
        방법
        
        part 1
        
        피벗 설정 후 리스트 왼쪽에서 피벗보다 큰 데이터, 리스트 오른쪽에서 피벗보다 작은 데이터 찾은 후 서로 교환, 서로의 값이 엇갈릴 때, 작은 데이터와 피벗 위치 교환
        
        part 2
        
        피벗을 기준으로 나눠진 각 2개의 리스트에도 part 1의 과정 반복
        
        part 3
        
        모두 정렬 될 때까지 생성된 리스트에 이전 과정 반복
        
        시간 복잡도
        
        $$ [O(N\log N), O(N^2)] $$
        
        $$ O(N \log N) $$
        
        분할이 이루어지는 과정이 진행될 수록 크게 감소되는 과정, 정렬이 덜 되있을 수록 빨라진다
        
        $$ O(N^2) $$
        
        이미 정렬이 되어있으면 매우 느림
      - 삽입정렬(insertion sort)
        
        방법
        
        위치를 정한 인덱스를 기준으로 새 원소 위치를 결정하는 과정을 N-1번
        
        시간복잡도
        
        $$ [O(N), O(N^2)] $$
        
        거의 정렬된 상태에서 최적의 시간복잡도
      - 선택정렬(selection sort)
        
        시간 복잡도
        
        $$ O(N^2) $$
        
        방법
        
        가장 작은 데이터를 앞으로 보내는 과정 N번
    - - 계수정렬 (count sort)
        
        방법
        
        원소의 최대, 최소값을 모두 담을 수 있는 리스트 생성
        
        리스트 내 모든 데이터 초기화
        
        데이터를 하나씩 확인하여 값과 동일한 인덱스를 하나씩 증가
        
        인덱스로 정렬된 형태를 출력
        
        조건이 맞으면 사용가능한 매우 빠른 알고리즘
        
        조건
        
        데이터의 크기 범위가 정수형태로 표현 가능
        
        가장 큰 데이터와 가장 작은 데이터의 차가 1000000 미만일 때 효과적
        
        복잡도
        
        시간 복잡도
        
        $$ O(N + K) = [O(N), O(N \log N)] $$
        
        K는 데이터 중 최대값
        
        공간 복잡도
        
        최대, 최소가 항상 데이터로 잡히므로 빠르지 않은 경우도 있다
        
        동일한 값이 여러 개 일 경우 빠르다
        
        데이터 특징 모르면 퀵정렬 사용이 더 낫다
        
        코딩 테스트에서는 일반적으로 데이터값이 1000만을 넘지 않으니 유용할 가능성이 높다
  - - - 퀵정렬과 삽입정렬의 하이브리드(병합정렬)
        
        대체로 빠르니 되도록 써라
    - - key값으로 매개변수를 설정 가능하여 내부 튜플 정렬에 이용가능
  - - - 예제: 위에서 아래로
    - - 예제: 두 배열의 원소 교체
    - - 예제: 성적이 낮은 순서로 학생 출력하기
- - - - 이용법
    - - 디버깅용
  - - - 가입했음
- - - - 조건
        
        음의 간선은 없어야 한다
      - 원리
        
        1.출발 노드 설정
        
        2.최단 거리 테이블 초기화
        
        3.방문하지 않은 노드 중 최단거리가 가장 짧은 노드 선택
        
        4.해당 노드 거쳐 다른 노드로 가는 비용 계산하여 최단거리 테이블 갱신
        
        3과 4를 모든 노드가 실행될 때까지 반복
      - 방법
        
        쉬운 구현, 느린 속도
        
        순차 탐색 이용
        
        노드 개수가 5000개 이하일 시 적용 가능
        
        시간 복잡도
        
        $$ O(V^2) $$
        
        V는 노드의 개수
        
        어려운 구현, 빠른 속도
        
        특징
        
        힙 자료구조 이용
        
        자료구조상 특성
        
        낮은 삽입, 삭제 시간복잡도
        
        2 more items...
        
        언어마다 다른 우선순위
        
        3 more items...
        
        우선순위 큐를 구현하기 위한 자료 구조
        
        2 more items...
        
        최소신장트리와도 유사
        
        현재 가장 가까운 노드 저장 목적으로만 이용
        
        최소힙 이용시 낮은 값 먼저 삭제로 적합
        
        쉬운 구현의 get_smallest_node부분을 우선순위큐가 하는 방식
        
        시간복잡도
        
        $$ O(E \log V) $$
        
        E 는 간선 개수, V 는 노드 개수
      - 특징
        
        각 노드에 대한 현재까지의 최단거리 정보를 항상 1차원 리스트에 저장 계속 갱신
        
        현재 노드 기준 매번 주변 간선 확인
        
        한 단계당 하나의 노드에 대한 최단거리 확실히 찾아낸다
        
        일종의 그리디 알고리즘
    - - 특징
        
        모든 지점에서 다른 모든 지점까지 최단경로를 모두 구해서 2차원 리스트에 저장
        
        일종의 다이나믹 프로그래밍
        
        점화식
        
        $$ D_{ab} = min(D_{ab}, D_{ak} + D_{kb}) $$
        
        총 시간 복잡도
        
        $$ O(N^3) $$
      - 방법
        
        노드수에 맞춰 2차원 리스트 생성 후 같은 노드 값은 0으로 간선으로 연결된 곳에는 거리 값을 입력하고, 연결 안 된 곳은 무한으로 입력
        
        노드를 지정하여 그 노드를 거쳐가는 간선의 합을 앞서의 거리 값과 비교하여 최소값으로 대체(점화식 이용)
        
        모든 노드에 적용하여 2차원 리스트 갱신 후 출력
        
        의문점: 거쳐가는 노드가 2개 이상일 경우 저렴해지는 경우 반영될까?
        
        각 노드 거치는 최단거리가 갱신되므로 반영이 된다.
  - - - 플로이드 워셜
    - - 데이크스트라