알고리즘 & 코딩 테스트 검색 결과

해당 글 31건

[알고리즘 중급 1/3] 그리디 알고리즘

결정 할 때, 그 순간에 가장 최적인 방법( 기준을 내가 잡아야 함 )을 선택하면서 답을 찾아간다. 그 순간에 최적인 방법을 선택한다고 해서, 답이 최적이라고 보장할 수는 없다. 어떤 문제가 그리디 라는 것을 어떻게 증명할 것인가? 두 동전 회의실 배정 행렬 어떤 코딩 테스트 문제를 만났을 때, 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민하자. 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 그때는 다이나믹 프로그래밍(DP)이나 그래프 알고리즘 등으로 문제를 해결할 수 있는지 재차 고민해보자. 처음 문제를 만났을 때는 이것저것 다양한 아이디어를 고려해야 한다. 가장 먼저 10원짜리로만 모두 거슬러 주도록 코드를 작성하면 어떻게 되지..
알고리즘 & 코딩 테스트/code.plus 2021. 10. 25. 22:52

[알고리즘 중급 1/3] 분할 정복 (이분 탐색 / 병합 정렬(merge sort) / 퀵 정렬(quick sort)

분할 정복 - 분할 정복은 문제를 2개 또는 4개 이상의 작은 부분 문제로 나눈 다음 (분할) 다시 합쳐 정답을 구할 수도 있음. (정복) - 분할 정복이 dynamic programming 과 가장 다른 점은, 부분 문제가 중복되지 않는 다는 것이다. dp 에서는 부분 문제들이 중복되어 memoization 을 통해 중복을 제거했다면, 분할 정복에서는 부분 문제 끼리 중복이 없기에 부분 문제를 1번씩만 풀면 된다. 이분 탐색 가장 중요한 분할 정복 알고리즘이다. 리스트의 크기가 N 이라면, 정렬되어 있는 리스트에서 값을 빠르게 찾는 알고리즘 - 시간 복잡도 : O(lgN) 아래 배열에서 4를 찾아보자. 찾으려는 값(4) 와 M 중간값(7) 을 비교해보면, 찾으려는 값(4) 가 더 작기 때문에 -정렬되어..
알고리즘 & 코딩 테스트/code.plus 2021. 10. 9. 22:09

[기초] 시뮬레이션

배열 돌리기 3 시뮬레이션 : 문제에 나와있는 대로만 그대로 구현하는 문제이다. 배열 돌리기 3 시뮬레이션 문제에서 나타나는 특징 중 하나는, 동작이 동시에 일어나는 것이다. 하지만, 코딩을 동시에 할 수는 없기에 어떤 동작이 어떻게 일어나야 하는지를 선행 조사 해두고 그 후에 한번에 동작을 실시한다. 톱니바퀴 문제에서 잘 드러난다.
알고리즘 & 코딩 테스트/code.plus 2021. 10. 4. 19:33

[기초] BFS

BFS-1 DFS 나 BFS 나 임의의 정점에서 시작하여 모든 정점을 방문한다. 라는 목적은 같다. 이것만이 목적이라면 어떤 것을 택해도 좋다. 하지만, BFS 만이 특별히 이용되는 경우가 있는데, 모든 가중치가 1일 때, 최단 거리를 구하는 알고리즘일 때 이다. (만약, 가중치가 1이 아니라면 다익스트라 알고리즘 을 사용한다.) 단, 가중치와 비용은 같아야 한다. 숨바꼭질 숨바꼭질4 BFS-2 제한 조건에 따라서, 정점을 나누어서 생각해야할 수 있다. 아래의 이모티콘 문제를 보면, 제한 조건이 다르기 때문에 정점을 나눠서 구현했다. 여기서는, 정점을 "이차원으로 만듦"으로써 나누었다. 이모티콘 숨바꼭질3 알고스팟
알고리즘 & 코딩 테스트/code.plus 2021. 10. 3. 10:19

[기초] 그래프의 탐색

그래프의 탐색의 목적 : 한 정점에서 시작해서 연결된 모든 정점을 한 번씩 방문하는 것. (DFS, BFS) - 방문 순서를 어떻게 결정하는 것이냐에 따라 DFS, BFS 는 다르다. DFS 와 BFS 1260 연결 요소 연결 요소는 DFS / BFS 탐색 둘 다 이용해서 구할 수 있다. DFS 가 시작한다는 것은 연결 요소를 찾았다. 라는 것과 같다. 연결 요소의 개수 11724 이분 그래프
알고리즘 & 코딩 테스트/code.plus 2021. 10. 2. 17:01