빌려온 가나디

이번 코테 벼락치기하면서 느낀 거. dfs bfs 는 그래프에서만 쓰이는 게 아니다~ㄴ 진짜 몰 랐 어 DFS 는 탐색 (검색) 문제에서 "한 경로 끝까지 들어갔다가 다시 돌아오는 방식" 이다.즉, 모든 경우의 수/경로를 전부 확인해야 할 때 자주 쓴다.깊게, 끝까지 탐색하는 것이다. (재귀/스택) 반면에 BFS 는 "가까운 것부터 차례차례 넓혀 나가는" 탐색이다.넓게, 가까운 곳에서부터 탐색하는 것이다. (큐)최단거리 문제에 자주 사용된다. DFS경로 전체 탐색, 경우의 수 세기, 연결 요소 찾기, 순열/조합그래프/트리 탐색DFS 는 한 갈래 끝까지 갔다가 못 가면 돌아오는 (backtracking) 방식이라, 트리/그래프 구조에 잘 맞음경로 찾기/모든 경우 탐색미로 탐색, 백트래킹 문제(N-Queen..

먼저 문제를 보면구명보트에는 한 번에 두 명까지만 탈 수 있고무게 합이 limit 을 넘으면 안 된다.이때 필요한 최소 보트 수를 구하라그리디란, 매 순간 가장 최적의 선택을 해나가는 알고리즘이다. 이건 나도 알고 있다. 전체 최적해가 아니라 매 순간 "좋아 보이는 선택" 을 하는 것이다. 이 문제에서의 그리디 전략은 다음과 같다.제일 무거운 사람은 반드시 태운다.이 사람과 가장 가벼운 사람을 짝지을 수 있으면 최선이다.보트 수를 최소화하려면 무거운 사람은 최대한 가벼운 사람과 함께 타야 보트의 낭비가 없기 때문이다. 가장 무거운 사람과 가장 가벼운 사람을 알려면 어떻게 할까? 배열을 정렬하고, 양 끝에 포인터 두 개를 둔다. 이후 조건에 따라 이동시키며 문제를 해결한다. 정렬된 people 배열:[i]..

네이버 코테 전날 알고리즘을 1 도 모르면서 벼락치기 라도 해보겠다고 BFS 문제를 허겁지겁 풀다가 토마토에서 막혀버렸다... 밤은 늦었고 내일 코테는 어차피 글렀고... 어차피 경험 삼으려고 신청한 거고... 하며 답답한 마음으로 집에 가는데 서러워져서 울었다 ㄹㅇ임그니까 BFS 란 그래프나 트리에서 가까운 노드부터 탐색해 나가는 알고리즘이다. BFS 는 같은 레벨 (거리) 에 있는 노드를 먼저 다 본 다음, 그 다음 레벨로 넘어간다. BFS 알고리즘을 작성할 때의 특징큐(Queue) 자료구조 사용최단 거리 문제에 자주 쓰임방문한 노드를 다시 방문하지 않도록 visited 배열을 사용동작 방식시작 노드를 큐에 넣고 방문 표시큐에서 노드를 꺼냄해당 노드와 연결된 (방문하지 않은) 노드들을 큐에 추가하고 ..

알고리즘 기초를 풀면서 수학 문제만 풀다가 나도 남들이 말하는 dp 문제라는 걸 풀게 됐다! 뿌듯해요 Dynamic Programming 은 동적 프로그래밍이다. 복잡한 문제를 작은 문제로 분해하여 해결하는 알고리즘 기법 중 하나이다. 분할 정복과 유사하며 중복되는 부분 문제가 발생할 때 한 번만 계산하고 그 결과를 메모이제이션하여 다른 비슷한 부분 문제들이 다시 발생할 때 메모이제이션한 결과를 가져와 재활용한다.  동적 프로그래밍을 적용하기 위해서는 두 가지 조건을 만족해야한다. 전체 문제의 최적해가 부분 문제의 최적해로부터 구해질 수 있어야 하는 최적 부분 구조 (Optimal Substructure) 와 부분 문제가 중복되어 여러 번 반복 계산되어야 하는 중복되는 부분 문제 (Overlapping ..