138일자 - TIL

 

 

자료구조 & 알고리즘

GitHub - ji-hoooon/datastructureandalgorithms: Data Structure 구현 및 Algorithms 작성

1. 완전 탐색

1. 15651번. N과 M (3)
   • 중복순열 : 중복을 허용해서 순서 있게 나열하기
2. 15649번. N과 M (1)
   • 순열 : 중복없이 순서 있게 나열하기
3. 155652번. N과 M (4)
   • 중복조합 : 중복을 허용해서 고르기
4. 15650번. N과 M (2)
   • 조합 : 중복없이 고르기
5. 14888번. 연산자 끼워넣기
6. 9663번. N-Queen

연습문제

1. 1182번. 부분수열의 합
2. 1795번. 암호 만들기
3. 13663번. N과 M (9)

2. 정렬

1. 특성
   1. 같은 정보들은 입접해 있다.
   2. 각 원소마다, 가장 가까운 원소는 자신의 양 옆 중에 있다.
   3. N개의 원소를 정렬하는 것은 O(NlogN)의 시간 복잡도를 가진다.
2. 기본 자료형 정렬 - Dual-Pivot Quick Sort : in-place
   • 정렬 과정에서 N에 비해 충분히 무시할만한 메모리만 추가로 사용한다.
   • 1부터 N까지 사용한다면, 동등한 위상의 원소들의 순서관계를 보장하지 않으므로,
   • Arrays.sort(a, 1, N+1)을 이용해 정렬을 수행해야한다.
3. 객체 정렬 - Time Sort :stable
   • 동등한 위상의 원소들의 순서 관계가 보장된다.

기본 문제

1. 10825번. 국영수
2. 1015번. 수열 정렬
3. 11652번. 카드
4. 15970번. 화살표 그리기

연습문제

1. 1181번. 단어 정렬
2. 20291번. 파일 정리

3. 이분 탐색

정렬이 되어있지 않은 수열과 탐색 대상 X가 갖는 질문 - O(N)

1. X가 존재하는가
2. X[이하, 이상, 초과]의 원소는 몇개가 있는가
3. X랑 가장 가까운 원소는 무엇인가

정렬이 되어 있는 수열과 탐색 대상 X가 갖는 질문 - O(logN)

• 이분 탐색으로 같은 질문을 더 빠르게 해결할 수 있다.

이분 탐색 구현을 위한 변수

1. L := 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스
2. R := 탐색할 가치가 있는 범위의 오른쪽 끝 인덱스
3. Result := 탐색한 X의 위치
4. 탐색 목표 := X이하의 원소 중에 가장 오른쪽에 있는 원소
   • L=1, R=9, M=(L+R)/2=5 -> A[M]과 X를 비교
   • L<=R이면 계속 반복, 즉 L>R이면 종료
   • A[M]<X -> L = M+1=6, R=9
   • A[M]>=X -> L=1, R = M-1=4;
   • N이 10만일 때, 10만과 16으로 시간 복잡도의 엄청난 차이가 존재하게 된다.

이분 탐색 주의 할점

1. 정렬하지 않는 경우
2. L, R, M, Result를 사용해 부등호를 잘못 사용하는 경우
3. L, R의 범위를 잘못 설정하거나, Result의 초기값을 잘못 설정하는 경우

기본 문제

1. 7795번. 먹을 것인가 먹힐 것인가
2. 2470번. 두 용액

연습 문제

1. 1920번. 수 찾기
2. 1764번. 듣보잡
3. 3273번. 두 수의 합
4. 10816번. 숫자 카드 2

이분 탐색의 아이디어 - 매개변수 탐색

1. 매개변수를 만들기
2. 만든 매개변수로 문제에 해당하는 YES/NO 조건 만들 수 있는가?
3. 정렬된 상태인지 확인하고 정렬이 필요하면 정렬한다.
4. 바꾼 문제가 더 풀기 쉬우면, 매개변수 탐색 수행해서 해결
   • 정렬하고, 매개변수를 정렬했으니까 왼쪽부터 차례대로 결정하고, 이분탐색한다.
   • O(NlogN), O(N), O(logX) = O(NlogN+NlogX)

기본 문제와 해당하는 연습 문제

1. 2805번. 나무 자르기
   1. 1654번. 랜선 자르기
   2. 2512번. 예산
2. 2110번. 공유기 설치
   1. 2343번. 기타 레슨
   2. 6236번. 용돈 관리
   3. 13702번. 이상한 술집
   4. 17266번. 어두운 굴다리

Advancedㅊ

1. 1300번. K번째 수
2. 1637번. 날카로운 눈

4. 두 포인터

1. 정답을 찾기 위해 찾는 영역(or 과정)을 줄일 수 없을까?
2. 필요한 부분만 (or 빠르게) 탐색
3. 정답을 찾기 위해 탐색해야하는 영역을 줄여서 꼭 필요한 부분만 탐색하도록 하자.
4. 부분합
5. 두 용액
6. List of Unique Numbers
7. 좋다
8. 고냥이

연습문제

1. 수들의 합 2
2. 수열
3. 귀여운 라이언
4. 배열 합치기
5. 수 고르기
6. 두 수의 합
7. 세 용액

5. 그래프 탐색 (DFS & BFS)

인프런

기초 (재귀함수, 트리, 그래프)

1. 재귀함수 (스택프레임)
2. 이진수 출력 (재귀 함수)
3. 팩토리얼
4. 피보나치 재귀 (메모이제이션)
5. 이진트리 순회 (DFS)
6. 부분집합 구하기 (DFS)
7. 이진트리 레벨탐색 (BFS)
8. 송아지 찾기1 (BFS)
9. Tree의 말단 노드까지 가장 짧은 경로 (DFS)
10. Tree의 말단 노드까지 가장 짧은 경로 (BFS)
11. 그래프와 인접 행렬
12. 경로탐색 (DFS)
13. 경로탐색 (인접리스트)
14. 그래프 최단 거리 (BFS)심화

백준

1. 기본 구현
   • 1260번. DFS와 BFS
2. 격자형 그래프
   • 2667번. 단지번호 붙이기
   • 1012번. 유기농 배추
   • 11724번. 연결 요소의 개수
   • 4963번. 섬의 개수
   • 3184번. 양
3. 일반 그래프
   • 2606번. 바이러스
   • 11403번. 경로 찾기
   • 11725번. 트리의 부모 찾기
   • 13023번. N명의 친구
4. 그래프로 만들기
   • 2251번. 물통
   • 1697번. 숨바꼭질
   • 1389번. 케빈 베이컨의 6단계 법칙
   • 5567번. 결혼식
5. 멀터 소스 BFS (시작점이 여러개인 BFS)
   • 14502번. 연구소
6. 최소 이동 거리 BFS
   • 2178번. 미로 탐색
   • 7562번. 나이트의 이동
   • 2644번. 촌수 계산
   • 18404번. 현명한 나이트
7. 더블 BFS
   • 3055번. 탈출 (멀티소스 BFS이기도 함)
   • 7569번. 토마토

6. 트리

키워드

1. 두 정점 사이의 경로가 존재하고, 사이클이 존재하지 않는 경우만 고려한다.
2. 정점과 정점 사이를 잇는 N-1개의 간선이 존재하며, 모든 정점은 연결되어 있다.
3. 정점들이 모두 연결되어 있고, 사이클이 없는 그래프, 정점의 개수는 N이고 간선의 개수는 N-1개

아래의 특성 중 2개 이상 만족할 경우 트리

1. 모두가 연결되어 있어서 어떤 두점을 골라도 간선을 타고 서로 이동 가능
2. 사이클이 존재하지 않음
3. 정점 개수 |V| = 간선 개수 |E|+1

트리와 루트 트리

1. 트리에는 루트가 존재하는 경우와 루트가 존재하지 않는 경우가 존재
2. 트리가 존재하는 경우, 트리의 깊이를 기준으로 루트로부터의 거리에 대한 조건을 참고해 문제를 푼다.
3. 루트트리에는 조상, 자식, 형제, 말단 노드가 존재한다.
4. 일반적인 알고리즘 문제에서는 루트 트리를 이용한다.
5. |V|=|E|+1이므로, 인접행렬로 만든다면 |V|의 제곱으로 공간복잡도 낭비

백준

1. 구현 (루트가 없는 트리에서 루트 만들기)
   • 11725번. 트리의 부모 찾기
   • 4803번. 트리
2. DFS를 이용하는 동적계획법
   • 1068번. 트리 (단말 노드의 개수(BFS/DFS)로도 가능)
   • 15681번. 트리와 쿼리
   • 14267번. 회사 문화1
3. BFS
   • 1991번. 트리 순회
   • 5639번. 이진 검색 트리
   • 9489번. 사촌
   • 20364번. 부동산 다툼
4. LCA (최소 공통 조상)
   • 3584번. 가장 가까운 공통 조상
   • 1240번. 노드 사이의 거리
5. 최소신장트리 (크루스칼 알고리즘)
   • 15900번. 나무 탈출 (BFS도 가능)