자료알고 검색 결과

해당 글 130건
sort 함수의 custom compare 함수를 구현할 때 어떤 점도 조심해야 할까요?

요새 졸리네요. 코딩 테스트를 개최하면서 여러 코드를 보았는데요. 2회 코테가 의외로 1번부터 막히는 경우가 많았는데요. 아마도 정렬과 비교 함수의 메커니즘에 대해서 익숙하지 않아서 그러셨을 겁니다. strict weak ordering은 이펙티브 자바에서도 언급하는 주제이니 다른 조심해야 할 점을 언급해 볼게요. 이 질문과 이 질문은 제가 오늘 쓰려는 글과 관련이 깊습니다. 결론부터 말하자면, 정렬 문제에서 전처리 할 부분을 미리 전처리 하고 오면 로직이 단순해 집니다. 그러면 실수할 여지도 적습니다. 그리고 크기가 n인 배열을 정렬할 때 키 2개를 비교하는 compare 함수는 O(nlogn)번 호출됩니다. 이 글에서는 compare 함수가 어떻게 동작하나요? 에 대해서는 다루지 않습니다. 어떻게 정..
자료알고/알고리즘 2021. 11. 10. 00:42
리버스 가희와 프로세스 : 상황 도식화를 잘 시켜 봅시다.

가희배 코딩테스트 1회에서 나온 7번 문제는 가희와 프로세스 문제의 결과값이 주어졌을 때, 거꾸로 인풋 값을 만들어 보라는 문제였습니다. 항상 가능한 경우만 주었기 때문에 쉬울 거라고 생각했습니다. 그런데, 실제로 대회 때 문제를 푸신 분들은 그리 많지 않았고 골드 1로 평가되는 기염을 토하게 되었습니다. 사실 불가능한 경우까지 출력하라고 했는데, 진짜 그렇게 출제 했다면 100% 플레급으로 뛰었을 거라 생각합니다. 그러면 무엇이 이렇게 어렵게 만들었을까요? 문제에서 설명하는 알고리즘을 단순화 하는 것이 제일 어렵지 않았나 싶습니다. 게다가 실행 결과를 가지고 가능한 입력값을 만들라고 하니 당황할 수 밖에 없었을 겁니다. 사실 제가 맞닥트렸어도 매우 당황했을 겁니다. 일단, 가희와 프로세스의 나온 입력 ..
자료알고/알고리즘 2021. 11. 1. 04:31
heap 자료구조에 build를 어떻게 linear time에 끝낼까요?

오랫만에 자료구조 시간으로 돌아왔습니다. heap 자료구조는 다들 익숙하실 겁니다. 그리고 힙을 build 하는 연산을 힙 사이즈가 n이라면 O(n)에 할 수 있다는 이야기는 예전부터 들어왔어요. 그런데 어떤 원리로 그것을 할 수 있을까요? 자바에도 PriorityQueue가 있으니, 이 클래스의 내부 소스를 까보면서 이야기 해 보도록 하겠습니다. 문제 상황은 임의의 순서로 배열되어 있는 array를 heap 조건에 맞추어서 build 하는 것입니다. 그에 맞게 코드를 짜 보았습니다. PriorityQueue에 list를 넘겨주었는데요. Collection을 받았기 때문에, 아래 메서드가 호출될 겁니다. 아래에 나와있는 코드를 보겠습니다. 여기서 보면 List는 SortedSet도 아니고, Priorit..
자료알고/자료구조 2021. 10. 13. 14:50
in place 알고리즘에 대해서 간단하게 알아봅시다.

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

이번 시간에는 Longest Substring Without Repeating Characters 문제를 풀어보면서, 어떻게 시간 복잡도를 분석하는지 보도록 하겠습니다. 이 문제는 길이가 5만 이하인 문자열에서, 문자가 반복되지 않는 가장 긴 부분 문자열을 찾는 문제입니다. 문자열에 들어갈 수 있는 문자는 알파벳, 숫자, symbol, 그리고 space 문자입니다. 보통, 이렇게 주기 보다는 CodePoint는 아스키 코드 범위 내에 있다. 혹은 유니코드 범위 내에 있다. 이런 전제를 까는 게 더 좋기는 한데 넘어가 봅시다. 이모지 같은 것들 때문에 태클이 들어올 여지가 있습니다. 저 또한 문제 제작했을 때 간과했던 부분이기도 합니다. 문자열에 들어갈 수 있는 문자 집합이 작을 때에는 어떨까요? 놀랍게도..
자료알고/알고리즘 2021. 8. 27. 20:47