AlgorithmTraining

백준 및 프로그래머스 풀이 모음집

---

문제집

1. DFS/DFS
2. 시뮬레이션(구현)
3. DP, DP2
4. 다익스트라, 벨만포드, 플로이드-워샬
5. 그래프, 크루스칼, 위상 정렬
6. 그리디

---

Dynamic Programming (DP)

0. 합이 가장 큰 부분수열
1. LCS : BOJ-9251
2. 동전 : BOJ-9084
3. 동전1 : BOJ-2293
4. 동전2 : BOJ-2294
5. 가장 긴 증가하는 부분 수열4 : BOJ-14002
6. 가장 큰 정사각형 : BOJ-1915
7. 팰린드롬? : BOJ-10942
8. ★색상환 : BOJ-2482
9. 자두나무 : BOJ-2240
10. 암호코드 : BOJ-2011
11. 욕심쟁이 판다:DFS+memoization (최장길이) : BOJ-1937
12. 내리막 길:DFS+memoization (경로 수) : BOJ-1520
13. 내리막길: DFS+Memoization: BOJ-1520

    해당 문제는 매우 좋은 문제이다.
    내리막길의 경로의 수를 총합해서 구해줘야한다.
    
    해당 문제의 아이디어는 재귀호출 시 자동으로 메모이제이션 기능을 활용할 수 있다는 점에 있다.
    >> dp 를 모두 -1 로 초기화 해준다
    >> -1 이면 초기값이므로 DFS 진행, -1이 아닌 0이상의 수라면 경로이므로 계속 탐색을 한다..
    >> dp[x][y] += dfs(x,y); 형태로 이전에 왔던 길을 기록해둔다. (Memoization) 활용.
    

14. []
    7-A. DP 정리

---

그래프 (Graph)

다익스트라 (Dijkstra)

1. 최소비용 구하기2 : BOJ-11779
2. 최단경로 : BOJ-1753
3. 트리의 지름 : BOJ-1167
4. 특별한 최단 경로 : BOJ-1504
5. 알고스팟 : BOJ-1261
6. 파티 : BOJ-1238_C++
7. 녹색 옷 입은 애가 젤다지? : BOJ-4485_C++_10분정도걸림

밸만포드 (Bellman-Ford)

1. 오민식의 고민 : BOJ-1219, BOJ-1219(2)

플로이드-워샬 (Floyd-Warshall)

1. 플로이드 : BOJ-11404

위상정렬 : (Topological)

1. ARM Craft : BOJ-1005
2. 최종 순위 : BOJ-3665
3. 작업 : BOJ-2056

크루스칼 : (Kruskal)

1. 행성 터널 : BOJ-2887 + BOJ-2887 간선 최소화 과정 풀이 설명
2. 전기가 부족해 : BOJ-10423

---

수학 (math)

1. 벡터 매칭|Combinations+math.sqrt() : BOJ-1007
2. 신기한 소수 : 소수판별 root까지 : BOJ-2023_C++
3. 놀이 공원 : SetUnion 문제 : BOJ-1561

---

구현 (Realizng)

1. 뱀 : BOJ-3190
2. 럭키스트레이트 : BOJ-18406
3. 치킨배달 : BOJ-15686
4. 문자열압축 : PS-60057
5. 자물쇠와 열쇠 : PS-60059
6. 기둥과 보 설치 : PS-60061
7. 하늘에서 별똥별이 빗발친다 : BOJ-14658
8. 어른 상어 : BOJ-19237
9. 감시 : BOJ-15683_C++
10. 나무 재테크 : BOJ-16235_C++
11. 치즈 : BOJ-2638_C++
12. 구슬 탈출2 : BOJ_13460_c++
13. 2048(Easy) : BOJ-12100_c++, BOJ_12100_c++II
14. 로봇 청소기 : BOJ-14503_c++
15. 톱니바퀴 : BOJ-14891_c++
16. 경사로 : BOJ-14890_c++
17. 사다리 조작 : BOJ-15684_c++ => 실수 교훈
18. 드래곤 커브 : BOJ-15685_c++ => 회전문제에 대한 교훈
19. 미세먼지 안녕! : BOJ-17144_c++
20. 낚시왕 : BOJ-17143_c++ 좌표이동 관련 구현 테크닉
21. 이차원 배열과 연산자 오버로딩 : BOJ-17140_c++ 연산자오버로딩, 범위실수
22. 게리멘더링 2 : BOJ-17779_C++ 복잡한 구현 재풀이 추천
23. 새로운 게임2 : BOJ-17837
24. 원판 돌리기 : BOJ-17822_회전 포인터 풀이 교훈
25. 주사위 윷놀이 : BOJ-17825_어려운 구현문제, 실수다수유발
26. 모노미노도미노2 : BOJ-20061_c++
27. 스타트 택시 : BOJ-19238_c++, BFS 탐색에 대한 교훈이 있음
28. 컨베이어 벨트 위의 로봇 : BOJ-20055_C++
29. 마법사 상어와 파이어볼 : BOJ-20056_C++ 실수다수, 문제이해부족
30. 마법사 상어와 토네이도 : BOJ-20057_C++
31. 마법사 상어와 파이어스톰 : BOJ-20058_C++
32. 상어 초등학교 : BOJ-21608_C++, 연산자오버로딩
33. 상어 중학교 : BOJ-21609_C++
34. 마법사 상어와 비바라기 : BOJ-21610_C++
35. 마법사 상어와 블리자드 : BOJ-21611_C++(어려운 구현, 문제지문 설명미흡)
36. 주사위 굴리기 2 : BOJ-23288_C++_BFS Memoization 팁
37. 주사위 굴리기 : BOJ-14499_C++
38. 온풍기 안녕! : BOJ-23289_C++_중요한 실수함
39. 마법사 상어와 복제 : BOJ_C++
40. 어항 정리 : BOJ-23291_C++
41. 큐빙 : BOJ_5373_C++_어려운구현
42. 벽 부수고 이동하기 3: BOJ-16933_C++
    -- BFS에서는 Queue와 for문 특성상 다익스트라처럼 거리체크를 할 필요가 없다. 이는 벽 부시기 알고리즘에서도 통용된다.
    -- visited[11][1000][1000] 을 visited[10][1000][1000] 으로 두고 틀렸다. 범위 체크에 조금 더 여유를 부리는 것도 좋다.
43. 확장 게임 : BOJ-16920_C++
    -- 반복해가며 BFS 를 돌리는 문제인데 시간초과 위험이 있다.
    -- 마치 경계를 확장해나가는 형태처럼 새롭게 추가되는 녀석들만 추가하면 되었다.

---

탐색 (Searching)

BFS (Breadth Find Searching)

1. 토마토 : BOJ-7576
2. 불! : BOJ-4179
3. 아기 상어 : BOJ-16236
4. 적록색맹 : BOJ-10026_C++
5. 연구소 3 : BOJ-17142_C++ 조합구현 + 반례처리
6. 벽 부수고 이동하기 : BOJ_2206_C++ 벽을 부신케이스 vs 안 부시긴 케이스 visit 따로구현
7. 벽 부수고 이동하기2 : BOJ-14442_c++

DFS (Depth Find Searching)

1. 청소년 상어 : BOJ-19236
2. 연구소 : BOJ-14502(combinations), BOJ-14502(재귀함수)
3. 테트로미노 : BOJ-14500

---