주니어 개발자 남순이

✅ 동적 계획법

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

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

• 최적 부분 구조 (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 ]

✅ 집합의 개념

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

✅ 상호배타적 집합

• 교집합이 없는 집합관계 (집합은 꼭 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 ]

우연한 기회로 인프런에서 코딩테스트 합격자 되기 스터디원 모집 공고를 보고 신청하게 되었다.

열심히 공부해서 스터디가 끝난 후에는 코딩테스트에 자신감이 붙을 수 있도록 노력해야지..

그리고 올해 안에 이직도 성공할 수 있기를! 🍀

[알고리즘]

📝 알고리즘 : 어떠한 문제를 해결하기 위한 일련의 규칙이나 절차

다음 조건을 충족해야 한다.

- 정밀성 : 변하지 않는 명확한 작업 단계를 거쳐야 함

- 유일성 : 각 단계마다 명확한 다음 단계를 거쳐야 함

- 타당성 : 구현할 수 있고 실용적이어야 함

- 입력, 출력

- 유한성 : 일정한 시간 내에 결과를 도출해야 함 (무한루프 X)

- 일반성 : 모든 입력들에 대해 적용할 수 있어야 함 (특정한 경우에만 적용된다면 일반성을 만족시키지 않음)

📝 알고리즘의 성능 측정 방법

• 연산 횟수 측정 - 코드가 동일하면 연산횟수가 모두 동일하므로 객관적 지표로 사용 가능함. 연산횟수는 환경에 영향을 받지 않으나 입력값에 따라 달라질 수 있음
  
  • 예시) 입력값에 따른 연산 횟수가 일정하지 않은 경우

#include <iostream>

using namespace std;

void solution(int n) {
	if(n%2 == 0) {
    	for (int i = 0; i < n*n; ++i) {
        	cout << i << endl; 
        }
    } else {
    	for (int i = 0; i <= n; ++i) {
        	cout << i <<endl;
        }
    }
}

위 코드에서 연산횟수를 구하면 N이 짝수인 경우 N^2, N이 홀수인 경우 N 이 되므로 연산횟수가 일정하지 않다.

코딩테스트에서는 최악의 경우를 기준으로 연산횟수를 정한다.

입력값에 따른 연산횟수를 측정해서 알고리즘의 성능을 지표로 나타내는 것을 시간복잡도 라고 한다.

[점근적 표기법]

• 정확한 연산횟수가 아닌, 연산횟수의 추이를 활용해 시간복잡도 표기
• 최악의 경우를 고려해서 점근적 표기법으로 나타내는 것을 빅오표기법이라고 한다.
  
  • 방법
    1. 다항식에서 가장 많이 영항을 미치는 항을 남기고 제거
    2. 마지막 남은 항의 계수를 제거

[점근적 표기법의 코딩테스트 활용 방법]

• 주어진 입력값의 크기를 통해 어느 정도 시간복잡도 까지 허용되는지 추측 가능
• 구현 시 어떤 자료구조/알고리즘을 선택할 지 명확히 할 수 있음
• 구현한 코드가 시간초과 발생할 것인지 미리 파악 가능

[참고 강의]

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