알고리즘 공부하면서 정말 많이 접했었고 들었던 용어가 바로 DFS와 BFS이다.대충 어떤 차이가 있는지는 알겠고 어떻게 동작하는지도 알겠는데 막상 문제를 풀어보려니 막막해서 정리하게 되었다.트리나 그래프에서 한 경로로 최대한 깊숙이 탐색하다가 다시 돌아와 다른 경로로
탐욕법(greedy algorithm)을 이용하여 네트워크(가중치가 있으면서 방향이 존재하는 그래프)의 모든 노드를 잇는 최소 비용을 구하는 알고리즘① 간선들을 가중치의 오름차순으로 정렬② 정렬된 간선들을 하나씩 선택하되 사이클을 형성하지 않는 간선만 선택③ 해당 간선
임의의 시작 노드에서부터 출발해 인접한 노드를 추가함으로써 모든 노드를 잇는 최소 비용을 구하는 알고리즘① 시작 노드를 MST 집합에 포함② 앞 단계에서 만들어진 MST 집합에 인접한 노드들 중 최소 간선으로 연결된 노드를 선택해 트리 확장③ 위 과정을 트리가 (노드
문제를 풀면서 생각의 전환이 필요하거나 새로운 접근 방법이 필요한 경우를 여기에 정리해보자.방향 바꾸기앞에서부터 생각하다가 막히면 뒤에서부터 생각해보기방향이 바뀌면 계산 단계가 줄어들 수 있다.두 개의 인덱스를 찾는 문제이중 for문은 시간을 많이 소요하지만 해결책일수
다이나믹 프로그래밍 뭔지 알겠다! → 코테 박살내러 간다! → 하지만 박살나는 건 나였다아는 것 같은데 항상 시도할 때마다 벽을 느꼈던 다이나믹 프로그래밍 기본기가 부족하다고 항상 느껴왔던 터라 이참에 알고리즘의 기본들을 하나하나 박살내보기로 마음먹었다.LeetCode
DP가 어떤 경우에 사용될 수 있는지 저번 글을 통해 알아봤다.이번에는 본격적으로 문제를 DP적으로 접근하는 방법 에 대해 공부하자.GeeksforGeeks - How to solve a Dynamic Programming Problem ?특정 조건 하에 최대의, 최소
DP가 무엇인지 DP 문제를 어떻게 해결하는지 공부한 뒤로 약 일주일 정도 백준에서 20개 정도의 DP 문제를 풀어보았다.결론부터 말하자면 전보다는 확실히 늘었지만 아직 수많은 연습이 필요하다는 점을 뼈저리게 느낄 수 있었다.아직은 쉬운 문제들(백준 난이도 기준 Sil
정렬 알고리즘은 원소들을 번호순이나 사전 순서와 같이 일정 순서대로 열거하는 알고리즘이다. 정렬이 이루어져야 탐색, 병합 등 다른 알고리즘의 최적화로 이어질 수 있다.면접을 보다 보니 알고리즘의 특성 및 복잡도에 대해 확실히 해야겠다는 생각이 들어 오늘부터 알고리즘을
이분 탐색 그림이진 탐색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의로 선택해, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로
알고리즘 공부 - Union-Find