TIL_Algorithm

알고리즘 스터디

꾸준함을 이기는 법은 없다! 하루 3문제씩!

• 백준알고리즘
• 프로그래머스

TIL_이코테

• 그리디 : 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘
  • 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
  • 문제유형 파악 어려움 => 그리디 알고리즘 의심 => 다이나믹 프로그래밍 or 그래프 알고리즘 등
• 구현 : 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램(소스코드)으로 작성하기 (문법!)
  • 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
  • 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행
• DFS/BFS : 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘
  • 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
  • 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조
    • 스택 : FILO or LIFO
    • 큐 : FIFO
    • 재귀 함수 : 자기 자신을 다시 호출하는 함수 (재귀 함수 스택의 자료구조를 이용 & 종료 조건 필요)
    • 그래프 : 노드(정점)와 간선으로 표현 => 1, 2차원 배열을 그래프 형태로 생각하여 문제 풀이 - 2차원 배열에서 탐색 문제를 만나면 그래프 형태로 바꿔서 풀이
  • DFS(Depth-First Search) : 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘, 최대한 멀리 있는 노드를 우선으로 탐색하는 방식
    • 스택 & 재귀함수
  • BFS(Breadth-First Search) : 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
    • 큐
  • 경로탐색 유형 (최단거리, 시간)
  • 네트워크 유형 (연결)
  • 조합 유형 (모든 조합 만들기)
• 이진 탐색 : 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘
  • 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
  • 이진 탐색 : 반으로 쪼개면서 탐색하기 / 변수 3개(시작점, 끝점, 중간점) / 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교
    • 전제조건: 데이터 정렬
    • 2가지 구현 방법
      • [1] 재귀 함수 이용
      • [2] 반복문 이용
    • 이분 탐색의 범위는 무엇으로 할지
    • 이분 탐색의 기준을 무엇으로 할지
    • 자료구조
      • 트리 : 노드와 노드의 연결로 표현
        • 이진 탐색 트리 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
• 다이나믹 프로그래밍 : 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 (수열, 피보나치 수열) => 계산된 결과는 별도의 메모리 영역에 저장
  • 수열 => 배열 또는 리스트로 표현 (파이썬에서는 리스트 자료형이 연결 리스트의 기능을 포함)
  • 중복되는 연산을 줄여 연속된 많은 데이터를 처리
  • 구현
    • 메모이제이션 기법 : 한 번 계산한 결과를 메모리 공간에 메모하는 기법 => 캐싱
    • DP 테이블 : 결과 저장용 리스트(또는 배열)
    • 탑다운(하향식) : 재귀 함수 사용, 메모이제이션 사용
    • 보텁업(상향식) : 반복문 사용, DP 테이블 사용
  • 조건
    • [1] 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제에서 구한 답을 모아서 큰 문제를 해결할 수 있다.
    • [2] 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다.
  • 다이나믹 프로그래밍 vs 분할 정복 : 중복되는 부분 문제 차이
• 최단 경로 : 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 (가장 짧은 경로를 찾는 알고리즘)
  • 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우
  • 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우
  • 그래프 이용하여 표현 (노드와 간선으로 표현)
  • 최단 거리 알고리즘
    • [1] 다익스트라 최단 경로 알고리즘
      • 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
      • 음의 간선이 없을 때 정상 작동
      • 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것
      • 그리디 알고리즘으로 분류됨 => 매 상황에서 가장 비용이 적은 노드를 선택
        • [1] 출발 노드 설정
        • [2] 최단 거리 테이블을 초기화
        • [3] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
        • [4] 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
        • [5] 위 과정에서 3과 4번을 반복
        • => 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며 리스트에 계속 갱신한다는 특징이 있음 => 이런 1차원 리스트를 최단 거리 테이블이라고 함!
        • 방문 하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인 -> 4번 과정을 수행 => 그리디 알고리즘
      • 구현
        • 방법 1) 구현하기 쉽지만 느리게 동작하는 코드
        • 방법 2) 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드
    • [2] 플로이드 워셜 *
    • [3] 벨만 포드 알고리즘
  • 그리디 알고리즘 & 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다는 특징