알고리즘 검색 결과

해당 글 51건
bfs나 dfs에서 component를 왜 구하는지 알아보고 응용해 봅시다.

오랫만입니다. 가희와 함께 하는 3회 코딩 테스트 때문에 작년 연말부터 글이 꽤 뜸하게 올라왔습니다. 이것이 어제 끝났으니, 문제들을 하나 하나씩 리뷰해 보도록 하겠습니다. bfs나 dfs를 배우다 보면, 방향성이 없는 (다시 말해서, 양방향 간선만 있는) 그래프에서Component 라는 것이 나오게 됩니다. 이 문제가 대표적인 예입니다. 이것을 bfs나 dfs로 찾을 수 있다고 하는데요. 이것을 왜 찾을까, 찾아서 어디에 써 먹을 건지. 이 두 가지 의문에서 나온 것이 제가 출제한 가희와 베개 문제입니다. 아래 그림을 보면 Component는 2개가 있어요. 여기에 있는 간선들은 양방향으로 연결된 친구들입니다. 1번에서 bfs를 돌려 봅시다. 1번을 큐에 넣어볼까요? 그러면 큐에는 1만 들어가 있을 거..
자료알고/알고리즘 2022. 1. 24. 16:10
in place 알고리즘에 대해서 간단하게 알아봅시다.

정렬 알고리즘을 배우면서, stable 한지 그렇지 않은지는 많이 본 거 같습니다. 그런데 in-place 한지 여부도 분명 다룬 거 같았습니다. 그런데, 저는 이 부분에 대해서 잘 신경을 쓰지는 않았는데요. 쉽게 간과할 정도로 무지했던 셈입니다. 정리할 겸 겸사겸사 알아보도록 하겠습니다. 먼저, in place 알고리즘은 추가적인 메모리를 쓰지 않는 알고리즘? 그런데 아주 약간의 메모리를 써도 되는 알고리즘 정도로 문서에서 언급하고 있어요. 제가 보는 교과서에서는 constant한 공간을 쓰면 in-place 알고리즘이라고 언급하고 있습니다만, 대충 인풋 크기에 비해 정말 작은 메모리를 쓴다. 정도로만 이해하고 넘어가셔도 좋겠네요. 대충 input size가 500만 정도라고 생각해 보면, int나 l..
자료알고/알고리즘 2021. 9. 27. 04:21
왜 위상 정렬을 이용하면 그래프 사이클이 있는지 판단할 수 있을까요?

그래프에 사이클이 있는지 없는지 판단하는 방법 중 하나는 위상 정렬을 이용하는 것입니다. 어떻게 이용한다는 것일까요? 방향성이 있는 그래프에서, indegree가 0인 게 하나도 없다면 사이클이 있다고 판단합니다. 물론, indegree가 0인 노드가 있는데 사이클이 있는 경우도 있습니다만, 이건 글의 말미에 잠깐 다루겠습니다. 먼저, 아래와 같이 조건을 제한해 보겠습니다. 방향성이 있는 그래프에서 아래 조건이 성립합니다. 이 경우, indegree 값이 0인 노드가 존재하지 않는 그래프에 대해서 판단하는 것 보다는 조금이나마 더 쉽습니다. 사이클이란, i에서 i로 가는 경로를 의미합니다. 제한된 조건을 만족하는 노드 갯수가 n인 그래프를 생각해 봅시다. 일단 indegree 값이 1이므로, 나가는 것이..
자료알고/알고리즘 2021. 5. 3. 06:45
알고리즘 시간 복잡도 대강 분석하는 방법을 예제를 통해 알아봅시다.

시간 복잡도를 어떻게 대강 분석할까요? 실행 시간을 보고, 추정을 하시면 됩니다. 정말 괴랄한 복잡도가 아니라면, O(n), O(n^2), ... 등은 어느 정도 맞아 떨어집니다. 저는 java에서 메서드를 실행하는 데 걸린 시간을 측정할 때, System.nanoTime()을 이용하는 편입니다. 이것은 정밀한 시간 측정을 해 주지는 못합니다만, 어느 부분에서 시간 초과가 날 수 있는지 후보해를 추릴 수 있습니다. 질문이 하나 들어왔습니다. M자리 수와 N자리 수를 BigInteger로 곱하였습니다. M, N은 30만 자리 정도 되었다고 합니다. 10진수로 M자리 수라면, 32bit 2진수가 10진수 9자리와 대응이 됩니다. 그래서, bit 연산을 잘 이용하면 M과 N이 최대 30만자리까지 나오니까, (..
자료알고/알고리즘 2021. 4. 3. 02:24
진법 변환 알고리즘을 구현해 봅시다.

진법 변환은 어떻게 하면 좋을까요? 사실 익숙한 것이지만, 막상 코테에 나오면 당황할 법 합니다. 단독으로 나오기도 하지만, 문제를 푸는 과정에서 등장하기도 합니다. 0보다 큰 정수 n을 b진법 (b는 1보다 큰 정수)으로 바꾸는 방법을 알아보도록 하겠습니다. 그리고, AssertionError를 떨구는 것도 같이 알아보겠습니다. 먼저, 23을 10진법으로 변환하는 알고리즘을 생각해 봅시다. 그러면 먼저 23을 10으로 나눠야 할 겁니다. 그러면 몫이 2가 나오고, 나머지가 3이 나옵니다. 여기서 우리는 나머지 3을 취합니다. 몫이 2가 아니니, 2를 10으로 나누어서 몫과 나머지를 다시 구해야 합니다. 그러면 몫이 0이고, 나머지가 2입니다. 몫이 0이 되었으니 여기서 끝내면 되겠군요. 나머지는 3, ..
구현 2021. 3. 25. 07:00