혼종 꼬지마루

문제 이름 한번 잘 지었네..... f**k만 몇번을 외쳤던가.... A+등급을 딸 때 풀었던 문제라 쉽게생각하고 건드렸다가 문제 출력조건이 조금 달라서 맞왜틀 이러고 1시간을 날려먹은 문제 문제 조건도 애매모호한 부분이 있고, 출력 답의 예시라도 설명을 해줬으면 좋았을 문제.... 먼저 출력은 2가지만 생각하면 된다. 정상 종료, loop로 인해 정상종료가 불가능한 경우 정상 종료는 문제가 없는데 loop를 설정하는거에서 문제가 많다.... 일단 풀이를 차근히 해보도록 하겠다. 먼저, 이 문제의 핵심은 [, ]일때 점프하는 index를 어떻게 잘 정해주는가이다. 간단히 stack으로 해결할 수 있다. 일단 명령어를 입력받고, 순회하며 stack으로 쌍을 지어 점프 포인트를 만들어 주면 된다. 그 외에는..

TRIE란 TREE를 응용한 문자열 알고리즘이다. Wiki에서는 hash map을 대신할 수 있다고 되어 있는데 실제로 그렇다. 단순하게 이진트리가 아니라, 문자열을 순차적으로 순회하며 tree를 구성해주게 되는데, trie를 사용하는 장점 중 하나는 저장과 동시에 정렬이 된다는 점이다. 삼성전자 상시 역량테스트를 준비하면서 hash를 공부하는 사람들이 많은데, 사실 데이터양이 많아질수록 직접 구현한 hash일수록 index충돌이 많이 일어나서 생각보다 AutoK를 하는 경우가 생길것이다. 물론 hash에 충돌이 안나게하는 여러가지 기법이 있지만.... key값이 그리 길지 않다면 trie를 hash처럼 사용하는 것을 선호하는 편이다. 위의 그림(Wiki 참조)과 같이 문자를 하나의 key값으로 삼으며 ..

Heap이란 입력으로 들어온 데이터를 2진 트리의 형태로 나타내어 순서대로 정렬? 해주는 것이라고 생각하면 쉬울 것이다. 자식 노드에 있는 값은 항상 부모노드의 값보다 작아야(혹은 정렬기준에 따라 커야) 함으로 입력과 동시에 정렬이 된다. Heap을 사용하는 가장 대표적으로 사용하는 우선순위 queue, heap sort가 있다. 그 중에서도 heap sort를 구현해 보았으며, 정렬 기준을 함수로 선언하여 던져주는, 즉, algorithm 헤더에 있는 sort와 최대한 비슷하게 구현해보았다. 정의된 시간 복잡도는 heap sort는 O(nlogn)이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464..