- 23년부터는 알고리즘(자바and파이썬) 폴더에 모든 문제를 Java 및 Python 언어로 분류해서 저장했습니다.
- 이전 문제들은 위 폴더에서 보실 수 있습니다.
- 22년까지만 작성
- 23년부터 문제 자체는 따로 포스팅 안하고 깃허브에만 저장
- 자바 및 파이썬 알고리즘 공부 시 배우게 된 메소드 등에 대한 기록 보관소
- 링크 추후 등록 예정
- <자체 블로그> 칸에 "Y" : 직접 작성 블로그 포스팅
- <자체 블로그> 칸에 "Y" : 직접 작성 블로그 포스팅 X / 다른 분 블로그 참조 ㅇ
| 순번 | 제목 | 자체 블로그 | 비고 |
|---|---|---|---|
| 001 | 그리디 or 탐욕 (개념) | N | * 탐욕 알고리즘 문제 해결 방법 1. 선택 절차: 현재 상태에서의 최적의 해답 선택 2. 적절성 검사: 선택된 해가 문제의 조건을 만족하는지 검사 3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복 |
| 002 | 다이나믹 프로그래밍 | N | * DP 특징 1. 재귀의 단점(메모리 낭비)을 보완할 수 있는 방식이라 할 수 있다. 2. 일반적으로 구하고자 하는 값을 얻기 위해 이전에 구했던 값들을 활용한다. - 단, 이전에 구했던 값은 리스트에 저장해서 메모리 및 시간 낭비를 방지한다. 3.점화식(예:피보나치)을 통해 구하고자 하는 값을 구할 수 있다. 4.DP 방식에는 크게 상향식과 하향식이 있다. - 하향식 방식보다 상향식 방식이 시스템 측면에서 더 좋다. 5. 문제 중에서 최종적으로 구한 값에 대해서 어떠한 큰 수로 나눈 나머지 값을 출력하라는 형식의 멘트가 나올 경우, 이 문제는 DP와 관련된 문제일 가능성이 매우 높다. - 참고로, 나머지 값을 최종적으로 구한 값에서 출력을 하려고 할 때 시행하지 말고, 애초의 각 리스트 값을 구할 때 나머지까지 구하고 리스트에 저장하는 것이 좋다. - 왜냐하면, 이렇게 해야 메모리 효율 측면에서 좋기 때문이다. (즉, 이렇게 하지 않으면 메모리 초과 판정을 받을 수 있다는 소리이다.) |
| 003 | 재귀의 단점 및 메모이제이션 | N | - |
| 004 | DFS / BFS | N | * DFS(깊이 우선 탐색) 특징 1. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 2.특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘 3. DFS는 스택 구조를 사용한다. 4. 스택 구조는 재귀함수 구조와 동일하다. 5. 인접 행렬과 인전 리스트를 둘 다 사용할 수 있으나, 파이썬에서는 인접 리스트를 활용한다. 6. DFS의 시간 복잡도는 O(N)이다. * DFS의 동작과정 1. 탐색 시작 노드를 스택에 삽입하고 방문처리한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. @ 방문 처리는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것. 방문처리를 함으로써 각 노드를 한번씩만 처리할 수 있다. # BFS(너비 우선 탐색) 특징 1.가까운 노드부터 탐색하는 알고리즘 2. 선입선출 방식인 큐 자료구조를 이용하며, 큐를 풀기 위해 deque 라이브러리를 사용한다. 2. BFS의 시간 복잡도는 O(N)이다. 3. DFS와 BFS의 시간 복잡도는 동일하다지만, BFS가 DFS보다 성능이 상대적으로 좋다. # BFS의 동작과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. |
| - | 해시(기초 & 메서드) | N | - |
| - | 해시(상세 기술) | N | - |
| - | 정렬(선택 & 삽입 & 버블) | N | - 선택, 삽입, 버블 정렬은 알고리즘 간단 - 효율성은 떨어짐 |
| - | 힙(기초 버전) | N | - 힙의 시간 복잡도 : O(log n) - 리스트 > 힙 변환 시간 복잡도 : O(n) |
| - | 힙(심화 버전) | N | - |