JoonDevBlog

백트래킹에서 매우 유명한 N-Queen문제를 풀었다. 몇 달 전에 머리 싸매면서 DFS, BFS이론을 공부한 뒤에 백준에서 골드4 N-Queen을 바로 접했을 때 벽을 엄청 느꼈었는데, 최근에 알고리즘을 고민하며 푸는 맛에 좀 재미가 들렀고, N-Queen문제를 프로그래머스에서 다시 접하게 되어 각잡고 풀어보았는데 풀려서 접근 과정과 코드를 기록하려고 한다. N-Queen 프로그래머스 링크 N-Queen 백준 링크 접근) 이미 실패했던 경험을 통해 유명한 DFS 백트래킹 문제임을 이미 알고있긴 했으니 DFS 백트래킹을 어떻게든 사용하여 구현하는데에 초점을 두었다 (솔직히 문제를 보자마자 아~ 백트래킹이구나~ 알아챌 자신은 없다.) 재귀의 형태던 while(stack.length>0)의 형태던 반복을 돌아..

Heap은 Data가 마구 모여져있는것인데, 그 중 특징을 가지게 한것이 Max Heap과 Min Heap이다. Maxtree란, 각 node가 자신의 child보다 크거나 같은것. (child가 하나든, 두개든) Max Heap: 완전 이진트리이면서 maxtree인것. Min heap : parent가 children보다 작거나 같은것. max heap은 root가 최댓값. min heap은 root가 최솟값. Priority Queue: 내가 어떤 값을 매기는데, 그 중 가장 큰 값을 매긴 애를 찾아낼 수 있는 구조. maxheap을 한번 만들면, 맨 위에 최대값이 있고, pop했을 경우 다음 최대값이 root가 되게 설정함. Complete binarytree덕분에 log(n) 의 시간복잡도로 데이..

스택은 다음과 같이 데이터를 차곡차곡 집어넣어(Push) 맨 위의 데이터부터 Pop을 하는 자료구조이다. 키보드에서 입력된 스트로크를 저장한다거나, Ctrl+Z명령어를 통해 우리가 실행한 명령들을 Undo하기 위해 기억해놓는것 정도를 예시로 들 수 있다. Queue의 경우, 이러한 형태를 띈다. 줄서기, 혹은 선입선출이라고 생각하면 된다. 자료를 추가할때는 Enqueue로 Back부분에 한칸씩 추가해주고, 자료를 빼줄때는 Dequeue로 빼주면서 다음 데이터가 Front가 되는것이다. 그러나 컴퓨터의 메모리에서 데이터를 추가할때마다 계속 Back을 한칸씩 밀면 엄청나게 긴 배열이 생겨 메모리가 낭비되거나, 배열의 끝에 막혀버릴 수도 있다. 그래서 이 큐를 개선시킨것이 원형 큐이다. 그림에서 원형 큐에 1..

[문제] 다음의 infix notation을 postfix notation으로 변경하고자 한다. 매 character를 읽을 때마다 stack의 내용을 적고, 그렇게 변하거나 변하지 않는 이유도 함께 적으시오. a*(b+c/d)-e a*바로 뒤에 괄호가 있다. 즉 a출력후 괄호 사이의 bcd도 바로 이어서 출력. 그 후 top부터/ + *으로 쌓여있는걸 출력해야겠지? 아, 중위연산을 후위연산으로 바꿀때는 연산자를 stack에 저장해야한다. 하여 출력값은 abcd/+*e-이다. 이 문제를 풀면서 괄호의 우선순위가 어느정도인지 헷갈렸다. a*(b+c/d)-e가 아니라a*(b/c+d)-e 였다면 어떻게 달라지는거지? 큰 차이가 없다. 괄호의 닫는 부분까지는 어쨌든 push를 계속 해줘야하고, 괄호를 닫고 난 ..