주니어 개발자 남순이

✅ 그리디

• 매 순간 가장 좋아 보이는 선택을 함 → 최적의 해가 아닐 수도 있음
• 특정 조건이 만족하는 경우 최적해를 보장함
• 최적해를 보장하는 경우에만 사용해야 함

✅ 최적해를 보장하기 위한 특성

• 탐욕적 선택 속성
  • 각 단계에서 가장 좋은 것을 선택한다는 것이 전체 문제 최적해가 됨
• 최적 부분 구조
  • 부분 문제의 최적해로 전체 문제의 최적해를 구성할 수 있음

✅ 예시 1 : 거스름돈 문제 ( 그리디로 풀리는 경우)

• 문제 : 4원,2원,1원의 화폐 단위로 13원을 거슬러 줘야 할 때, 가장 적은 동전 개수로 거슬러 주는 방법은?
• 접근 방법
  • 가장 적은 동전 개수를 위해서 화폐가 큰 동전부터 최대한 활용하자
  • 4원, 4원, 4원, 1원 = 13원 , 동전 4개 사용

✅ 예시 2 : 거스름돈 문제 ( 그리디로 풀리지 않는 경우)

• 문제 : 5원, 4원, 1원인 경우, 8원을 거슬러 줘야 할 때 가장 적은 동전 개수로 거슬러 주는 방법은?
• 접근 방법
  • 위와 똑같이 큰 단위 화폐부터 최대한 활용한다.
  • 큰 화폐부터 거슬러 주는 경우 : 5원, 1원, 1원, 1원 → 4개. 하지만 최적해가 아니다.
    • 4원짜리 2개를 거슬러 주면 동전 2개만 사용하게 됨.

☑️ 거스름돈 문제 정리

• 단위가 큰 화폐부터 돈을 거슬러 주는 경우
  • 각 화폐간 단위가 배수관계인경우 (예를 들어 1,2,4 원), 4원은 2원의 조합으로, 2원은 1원의 조합으로 만들 수 있다. 즉 앞의 동전을 최대한 사용해도 뒤의 동전 사용에 영향을 미치지 않는다.
    • 그리디로 최적해 보장 ⭕
  • 배수 관계가 아닌 경우 (5원, 4원, 1원) 5원을 최대한 사용해서 거슬러줬을 때 4원을 사용하지 못하는 경우가 발생. 즉 이후 동전선택에 영향을 미치게 된다.
    • 그리디적으로 최적해 보장 ❌

✅ 예시 2 : 최소 신장 트리(MST)

• 신장트리란?
  • 모든 정점이 간선으로 연결되어 있고, 간선 개수가 정점 개수보다 하나 적은 그래

• 최소신장트리란?
  • 신장트리 중 가중치의 합이 최소인 것
• 최소신장트리 구하기 (프림 알고리즘)
  1. 임의 정점 하나 최소신장트리에 추가
  2. 최소신장트리로 연결된 정점 중 가장 가중치가 적은 정점을 최소신장트리에 추가, 단 순환을 형성하지 않아야 함
  3. 과정 2를 신장 트리 조건 만족할 때 까지 반복

💡코딩테스트에 나오는 그리디 패턴

• 매 순간 가장 좋은 선택을 하면서 해결되는 경우
  • 최소 신장 트리
  • 최단 경로 문제 (다익스트라에서 사용, 벨만포드는 아님)
• 특정 조건을 만족하면서 가장 최대/최소값을 찾는 경우
  • 부분 배낭 문제 (0/1 배낭은 그리디 아님)
  • 스케쥴링 문제

[참고 강의]

코딩테스트 합격자 되기 - C++ [ https://inf.run/t92e1 ]

[참고 도서]

코딩테스트 합격자 되기 - 파이썬 편

[ https://www.yes24.com/Product/Goods/123272392 ]

✅ 동적 계획법

• 복잡한 문제를 단순한 하위 문제로 나눠서 접근하는 방법
• 중복 계산을 줄이기 위해, 이전에 구한 해를 활용함 (메모이제이션)

✅ 이전의 해를 활용해야 효율적인 문제의 조건

• 최적 부분 구조 (Optimal Substructure)
  • 문제의 최적 해결책이 하위 문제의 최적 해결책으로 부터 구성되는 경우
• 중복 부분 문제 (Overlapping Subproblems)
  • 동일한 하위 문제가 여러번 계산 됨

✅ 예시 1. 팩토리얼 - 동적 계획법으로 풀어도 효율 X

✅ 예시 2. 피보나치 수 - 동적 계획법으로 풀면 효율적

✅ 동적계획법을 문제에 적용하려면?

1. 예제 입력으로 출력 만드는 과정을 직접 손으로 작성
2. 과정을 일반화 한다. 이 때 최종해를 구하는 과정을, 이전해를 구하는 과정을 통해 나타낼 수 있는지 확인
3. 2번 과정에서 이전해를 구하는 과정이 중복되는 지 확인

✅ 예시 1 : 계단 오르기

• N개의 계단이 존재하고, 한 번에 1개 혹은 2개의 계단을 오를 수 있음. 계단을 오르는 방법의 총 수는?
• 적용
  1. 예제 입력으로 출력 만드는 과정을 직접 손으로 작성

2. 과정을 일반화 한다. 이 때 최종해를 구하는 과정을, 이전해를 구하는 과정을 통해 나타낼 수 있는지 확인

3. 2번 과정에서 이전해를 구하는 과정이 중복되는지 확인

✅ 정리

• 아래 두 조건을 만족하는 경우 동적계획법으로 접근하면 효율적
  • 중복부분구조
    • 현재 해를 구하기 위해 이전 해가 중복적으로 사용되는지 확인
  • 최적부분문제
    • 현재 해가 이전 해를 활용해서 해결할 수 있는지 확인
• 현재 해가 이전해를 활용해서 해결할 수 있지만, 이전해가 중복되지 않는 경우는 동적계획법으로 풀어도 효과가 없다.
  • 팩토리얼 (최적부분문제 O , 중복부분구조 X)
  • 피보나치 (최적부분문제 O , 중복부분구조 O)

✅ 정렬의 의미

• 데이터를 특정 기준에 따라 순서대로 배치
  • 예시) 오름차순 (작은 값에서 큰 값으로), 내림차순 (큰 값부터 작은 값으로)

✅ 코테에서 정렬이 필요한 이유

• 정렬된 상태에서 동작하는 알고리즘을 사용해야 하는 경우
  • 이진탐색
  • 병합정렬의 병합

✅ 삽입 정렬

• 왼쪽은 정렬된 영역, 오른쪽은 비 정렬된 영역으로 나뉨
• 정렬된 영역이 점점 확장되어 비 정렬된 영역이 없어지는 정렬 방법 
• 정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치로 놓으며 정렬
• 최악의 경우 - 역정렬된 경우. 시간 복잡도 O(N²) 
• 최선의 경우 - 처음부터 정렬된 경우. 시간 복잡도 O(N)   

• 삽입정렬 과정

✅ 병합 정렬

• 리스트를 반으로 나누어 각각 정렬한 뒤 합치는 방식
• 각 부분 리스트를 재귀적으로 정렬. 최종적으로 정렬된 두 리스트를 합쳐서 전체 리스트 정렬
• 시간 복잡도 O(NlogN)
  • 나누는 횟수 logN, 이를 합치는 횟수 NlogN (N개를 병합하는 과정을 logN번 진행)

✅ 힙 정렬

• 힙 : 특정 규칙이 있는 이진 트리
  • 부모 노드가 자식노드보다 항상 크면 최대힙, 항상 작으면 최소힙

✅ 우선순위 큐

• 들어온 순서와 상관없이 우선순위가 높은 원소가 먼저 나가는 큐
• 고려할 점
  • 원소가 계속 들어온 상황에서 정렬 상태를 유지해야 함
    • 기존 대부분 정렬방법은 O(NlogN)
    • 힙정렬을 사용할 경우 삽입/삭제 시 O(logN) 보장 -> 우선순위 큐는 힙 사용

✅ 각 정렬 알고리즘 비교

[참고 강의]

코딩테스트 합격자 되기 - C++ [ https://inf.run/t92e1 ]

[참고 도서]

코딩테스트 합격자 되기 - 파이썬 편

[ https://www.yes24.com/Product/Goods/123272392 ]

✅ 백트래킹의 개념

• 가장 최근에 방문했던 노드로 다시 돌아감 (ex. DFS)
• 완전 탐색하지 말고, 내가 찾는 답일 가능성이 있는 경우에만 탐색한다.

✔️ 백트래킹 알고리즘의 핵심은 "해가 될 가능성을 판단하는 것" 이며, 그 가능성은 "유망 함수" 를 정의하여 판단한다.

✅ 백트래킹을 푸는 과정

• 상태 정의 : 문제의 각 단계에서 가능한 상태를 정의
• 유망 함수(isPromising) : 현재 상태가 유망한지 판단, 유망하지 않으면 더 이상 탐색하지 않음
• 해결책 확인(isSolution) : 현재 상태가 문제의 해결책인지 판단
• 재귀 호출 : 유망한 상태로 이동하면서 문제 해결

✅ 백트래킹 예시 - 부분합

✔️ 문제 : {1,2,3,4} 로 이루어진 집합에서 숫자를 뽑아서 합이 5인 조합 구하기

• 완전탐색으로 풀기 - 각 집합은 뽑거나 뽑지 않을 수 있으므로 아래와 같다
  • 시간복잡도 O(2^n)
  • 모든 경우의 수 탐색 - 총 16번

• 백트래킹으로 풀기
  • 상태 정의 : 현재까지 선택한 숫자들의 합
  • 유망 함수 : 현재 부분 합이 목표 값을 초과하면 유망하지 않다고 판단
  • 해결책 확인 : 현재 부분 합이 목표 값과 일치하는 지 확인
  • 재귀 호출 : 다음 숫자를 선택하여 부분합 갱신

유망 함수 설계

✔️ 현재 조합으로 합이 5가 되면 더 이상 탐색할 필요가 없음 (isSolution == true)

✔️ 해당 숫자를 조합하여 합이 K 이상이 되면 탐색할 필요가 없음 (isPromising == false)

✅ 그래프의 개념

• 노드(vertex) 와 간선(edge)을 이용한 비선형 자료구조
  • 목적에 따라 간선의 가중치나 방향이 있을 수 있음

✅ 그래프의 종류

• 방향성, 가중치, 순환 특성에 따라 종류 구분

✅ 그래프의 구현 - 인접 행렬

• 행과 열의 인덱스로 노드의 값을 나타내고, 배열의 값은 간선의 가중치가 됨
• 노드 대비 간선이 적을 경우 메모리 공간 효율이 좋지 않음

✅ 그래프의 구현 - 인접 리스트

• 특정 시작 노드를 기준으로 연결된 노드들을 리스트로 연결하는 방식
• 실제 그래프의 노드 갯수만큼만 추가하므로 메모리 낭비 없음
• 특정 노드에 모든 노드가 연결된 경우, 탐색시 O(N) 이 될 수도 있음 (드문 케이스)
• 인접리스트 그래프 표현 방식
  • 적절한 노드 정의 - 값(v) , 가중치(w), 노드 (next) 를 묶어서 관리
  • 노드 개수 만큼 배열 준비 (각 배열 인덱스는 시작 노드 의미)
  • 각 배열의 인덱스는 시작 노드를 나타냄, 해당 인덱스에 연결된 노드 추가

✅ 인접 행렬 vs 인접 리스트

• 노드의 개수가 많을 때는 인접 리스트를 써야 함(인접행렬 사용시 메모리 초과 가능성)
• 특정 정점의 간선을 찾는 경우가 많으면 인접 행렬 사용 고려도 괜찮음
• 뭘 써야 할 지 모른다면 인접 리스트

✅ 그래프의 탐색

• 깊이 우선 탐색(DFS)
  • 더 이상 탐색할 노드가 없을 때 까지 일단 간다.
  • 더 이상 탐색할 노드가 없으면 최근에 방문했던 퇴각 후, 가지 않은 노드 방문
• 너비 우선 탐색(BFS)
  • 현재 위치에서 가장 가까운 노드부터 방문하고 다음 노드로 넘어감
  • 모든 노드를 방문할 때 까지 위 과정 반복

✅ 깊이 우선 탐색 구현하기

1. 계속해서 깊이 탐색할 수 있어야 함
2. 더 이상 깊은 곳이 없는 경우, 가장 최근에 방문했던 노드로 돌아감
3. 이미 방문한 노드는 중복해서 방문하지 않아야 함

• 가장 최근에 방문했던 노드로 가는 효율적인 방법
  • 스택 활용 (LIFO)
    • 방문할 노드는 push , 방문한 노드는 pop . 스택의 top 은 가장 최근에 방문한 노드
    • 함수의 call stack 도 stack 과 같이 동작하므로 재귀함수로 구현하는 경우가 많음
    • visited 배열을 활용해서 방문 여부를 확인 후 방문함

✅ 너비 우선 탐색 구현하기

1. 루트노드부터 시작해서, 가장 가까운 노드들부터 방문할 수 있어야 함
   1. 루트노드 방문 -> 1개 간선으로 갈 수 있는 노드 방문 -> 2개 간선으로 갈 수 있는 노드 방문 ... (모든 노드를 방문할 때 까지 반복)

• 가장 가까운 노드부터 방문하는 효율적인 방법
  • 큐 활용 (FIFO)
    1. 시작 노드 push
    2. pop 후에 방문 처리 이후, 현재 노드에서 연결된 노드 중 방문하지 않은 노드 모두 push
    3. 모든 노드를 방문할 때 까지 2. 번 반복

✅ 깊이 우선 탐색 vs 너비 우선 탐색

• 백트래킹은 깊이우선 탐색에만 존재
• 너비우선탐색으로 찾은 해만 최적해를 보장
• 너비우선탐색은 모든 다음노드를 큐에 푸시하므로 깊이우선탐색보다 메모리 사용량이 높음
• 애매하면 깊이우선탐색 먼저 시도

[참고 강의]

코딩테스트 합격자 되기 - C++ [ https://inf.run/t92e1 ]

[참고 도서]

코딩테스트 합격자 되기 - 파이썬 편

[ https://www.yes24.com/Product/Goods/123272392 ]

✅ 집합의 개념

• 순서와 중복이 없는 원소들을 갖는 자료구조

✅ 상호배타적 집합

• 교집합이 없는 집합관계 (집합은 꼭 2개가 아니라 N개일 수도 있음)

✅ 집합 표현하기 - 무엇을 고려해야 할까?

• 특정 집합 원소들이 하나의 집합의 원소라는 것을 알 수 잇어야 함
  • 집합 A = {1,2,3} 일 때 각 원소가 집합 A에 속한다는 걸 알아야 함
• 각 집합 간 다른 집합이라는 것을 알 수 있어야 함
  • 집합 A = {1,2,3} , B = {4,5,6} 일 때 두 집합이 다른 집합이란 걸 알아야 함
• 특정 원소가 어느 집합에 속하는 지 알수 있어야 함
  • 집합 A = {1,2,3}, B = {4,5.6} 일 때 원소 5가 집합 B에 속한다는 걸 확인 가능 해야 함
• 두개의 집합을 하나로 합칠 수 있어야 함
  • 집합 A = {1,2,3}, B = {4,5,6} 일 때 이를 합쳐서 {1,2,3,4,5,6} 만들 수 있어야 

❗️각 집합의 대표 원소를 만들면 해결 된다.

❗️대표 원소 = 루트 노드

• 각 집합에서 가장 작은 원소를 대표원소 (루트노드) 로 한다.
• 대표 원소는 현재노드와 부모노드가 같음
• 배열을 활용해서 나타낼 수 있음(현재노드는 인덱스, 부모노드는 값)
• 부모노드가 없다면 -1로 나타낼 수 있음

✅ 집합의 연산 find

• 특정 노드의 루트 노드를 확인하는 연산
  • 특정 노드로부터, 루트노드가 나올 때 까지 거슬러 올라가면 됨
  • union 연산에서도 활용 

✅ 집합의 연산 find - 경로압축

• 루트노드를 찾는 데 필요한 경로가 깊어질 경우 연산 횟수 증가 => O(N)
• 경로 압축 알고리즘을 활용해 경로의 깊이를 줄일 수 있다.

✅ 집합의 연산 union

• 두 개의 집합을 하나의 집합으로 합치는 연산
• find 연산을 통해 각 집합의 대표원소를 구하고, 루트노드를 하나로 통일
  • 여러가지 방법이 있지만 작은 루트노드 쪽으로 합치는 방법도 있음

✅ 집합의 구현

• 노드의 최대값이 크지 않은 경우 => 배열로 구현
• 노드의 최대값이 큰 경우 => unordered_map 으로 구현

✅ 언제 집합 알고리즘을 쓸까?

• 이미지 세그멘테이션
  • 각 이미지를 의미 있는 부분으로 분할
• 네트워크 연결성 확인
  • 대규모 네트워크에서 두 컴퓨터가 서로 연결되어 있는지 확인

[참고 강의]

코딩테스트 합격자 되기 - C++ [ https://inf.run/t92e1 ]

[참고 도서]

코딩테스트 합격자 되기 - 파이썬 편

[ https://www.yes24.com/Product/Goods/123272392 ]

[해시의 개념]

• 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조
  
  • 값 : 최종적으로 얻고자 하는 정보
  • 키 : 값을 검색하기 위해 활용하는 정보
  • 해시 함수 : 키를 이용해 해시값(인덱스) 로 변경해주는 함수
  • 해시 테이블 : 키와 대응한 값이 저장되어 있는 공간
  • 버킷 : 해시 테이블의 각 데이터

[해시함수]

• 임의의 키를 해시테이블의 인덱스로 변경해 주는 함수
  • 해시 테이블의 크기가 N이라면 해시함수는 0~ (N-1) 사이 값을 내야 함
  • 충돌을 최소화 할 수록 좋은 해시 함수

[자주 사용하는 해시 함수]

• 나눗셈법
  • 키를 소수로 나눈 나머지를 활용

• 곱셈법
  • 나눗셈법은 k가 소수여야 하므로, 테이블 크기가 커지면 큰 소수가 필요
  • 곱셈법은 소수를 활용하지 않고 황금비를 곱하는 방식

• 문자열 해싱
  • 문자열의 아스키코드 값을 활용한 해싱

[해시 충돌]

• 서로 다른 키에 대해 해시 함수 결괏값이 같은 경우 "충돌" 이 발생함
• 충돌을 처리하는 방법 : 체이닝 , 개방 주소법

[언제 해시를 활용해야 하나?]

• 키-값  쌍으로 연관된 데이터가 존재하며, 해당 값에 대한 접근이 빈번한 경우
  • 사전 (단어를 검색해서 뜻을 찾음) , 연락처 (이름을 검색해서 번호를 찾음)
• 중복되지 않는 키를 사용하는 경우
  • 학번이나 집주소 (중복되지 않음)

[참고 강의]

코딩테스트 합격자 되기 - C++ [ https://inf.run/t92e1 ]

[참고 도서]

코딩테스트 합격자 되기 - 파이썬 편

[ https://www.yes24.com/Product/Goods/123272392 ]

스택의 개념

• LIFO (Last In First Out) , 가장 최근에 들어간 원소가 가장 먼저 나오는 자료구조
• 코딩테스트에서 특정 문제가 스택 문제인 지 알아야 한다
  • 스택은 "가장 최근에 들어온 원소"를 봐야할 때 사용
    • 추후 DFS / 백트래킹에서 사용

스택의 ADT (설계도)

• ADT (Abstract Data Type) : 추상 데이터 타입. 세부 사항을 숨기고 사용자에게 필요한 기능만 명시함
• push (삽입 연산) , pop (꺼내는 연산) , isFull (가득 찼는지 확인) , isEmpty (비었는지 확인) 와 같은 연산과 top ( 최근에 삽입한 데이터의 위치를 저장하는 변수) 을 정의

스택의 사용 예시

• 함수 호출 : 함수 호출 시 현재 함수의 실행 상태(context) 를 저장, 새로운 함수로 제어 이동
• 이전 페이지로 가기 : 페이지를 전환할 때 마다 스택에 push , 이전 페이지로 갈 때 pop
• 괄호 짝 맞추기

큐의 개념

• FIFO (First In First Out) , 가장 먼저 들어간 원소가 가장 먼저 나오는 자료구조
• 큐는 "들어온 순서대로" 나갈 때 사용한다.
  • 추후 BFS 에서 사용

큐의 ADT

• push (삽입 연산) , pop (꺼내는 연산) , isFull (가득 찼는지 확인) , isEmpty (비었는지 확인) 와 같은 연산들과 front (가장 먼저 push 된 원소의 위치, 큐의 앞) , rear (가장 최근에 push 된 원소의 위치, 큐의 뒤) 변수를 정의

큐의 사용 예시

• 줄서기
• 요세푸스 문제

[참고 강의]

코딩테스트 합격자 되기 - C++ [ https://inf.run/t92e1 ]