welcome!

이 문제는 비교적 구현의 성격이 강한 문제이다. 해당 문제에 대해 포스팅을 남긴 이유는 삼성 B형과 성격이 비슷하기에 골랐다. 입력으로 들어온 단어들을 내 사전 (Trie) 로 저장해놓고, 4*4 배열을 규칙에 따라 순회하면서 생성된 단어를 Trie에서 탐색하는 것이 해당 문제의 풀이이다. 이 풀이 서술은 조금은 일반적인 서술로써, 구현에 대해 조금 구체적으로 이야기 해보려 한다. 1 트라이 with memory allocation 대부분이 알고있는 Trie 의 형태로써 Trie 노드가 자식 노드의 주소를 가지고 있는 것이다. 그리고 동적으로 관리하기 때문에 new, delete를 동반한다. 아래는 해당 문제에 대한 Trie 풀이 소스이다. 해당 문제 자체가 올림피아드 성격의 대회 문제이기에 구현성이 강..

문제보러가기https://www.acmicpc.net/problem/6549 히스토그램에서 가장 큰 직사각형 흥미로운 문제다 생각의 진행은 다음과 같다.Main Think.[l ,r] 특정 구간내의 가장 큰 직사각형은 무엇인가? 김 : 가장 높이가 낮은 것을 기준으로 *(r-l+1) 가로길이 를 하면된다. 정 : 그렇겐 할 수 없다. 그렇게 푼다면 O(n)의 솔루션이 가능하다. 반례는 쉽게 구할 수 있다. 가로 길이가 2인 것을 직사각형 set을 생각하고 h 배열이 다음과 같다고 해봐라 [1, 1,000,000] 가장 큰 직사각형은 2인가? 1,000,000 인가? 김 : 내 솔루션이 틀렸다는걸 이해했다. 그러면 다음과 같이 해보자. 이건 조합문제라고 생각한다. 어쨌든 모든걸 시도하지 않으면 정답을 찾을..

문제보러가기https://www.acmicpc.net/problem/1620 이진검색 AVL 트리를 이용하여 해결했다.정답소스보러가기https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/1620.cc

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6pTXqsXUDFAWS 홍준이의 사전놀이 난이도 : D5 (하지만 기본적인 Trie data structure implemetation이었다) 트라이 자료구조를 통해 수행했다. 만약 트라이가 뭔지 모른다면 제가 정리한 포스팅이 있습니다 클릭 클릭 온라인 커뮤니티에서 들었는데, 가장 현명했던 방법은 단어를 insert 하면서 각 노드를 cnt++ 해주는것이 나중에 임의의 문자열 S에 해당하는 단어가 몇개있는지 체크해주는 것이였다. 나는 재귀를 통해 word 를 체크하였고, 그 방법은 최악의 경우의 연산수는 26^10 ( S

내가 제일 약한 자료구조문제 http://codeforces.com/problemset/problem/911/E 자료구조문제는 자료구조를 응용해서 푸는 문제이긴한데, 그 동작이 영 익숙치 않다. 이번 문제는 다음과 같다. 한 개의 큐와 한 개의 스택를 이용해 하나의 배열로 정렬하여 두어야한다.문제는 그림으로 그려보면 대충 다음과같다.1과 2의 동작을 할 수 있는데 array에 반드시 sorting 되어야한다.그래서 문제 이름이 stack sorting 이다. 그래서 sorting 이 될수 없으면 -1을 반환해야한다. 문제가 여기까지이면 nice이다. (그래도 까다롭고 어려울 듯)그런데 문제는 이 요구사항에서 한 걸음 더 나가는데, 배열 size가 n이라고 할 때 단 k만 주어진다. 그래서 문제 input..