S E P H ' S

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 처음엔 단순히 dfs를 생각했다가 경우의 수가 많아질 수 있다와 1칸, 2칸 ~ N칸 늘어나게 되더라도 몇 칸마다 채워주는 규칙은 똑같지 않나? 라는 생각에 DP가 떠올랐다. 점화식 구하는 것은 DP 문제 중에 기초 중에 기초였지만 경우의 수를 1,000,000,007로 나누는 것을 DP 배열에 저장할 때 모두 해줘야 했다. 앞으로 저런 제한사항이 있다면 주의해서 과정에 꼭 넣는 것을 빼먹지 말아야겠다. public class 타일링_2xn { public int solution(int n) { i..

우선순위 큐(Priority Queue) 힙(Heap) 자료구조를 기반으로 구현된다. 힙은 노드를 활용하여 링크드리스트 처럼 구현하는 방식이 있고 배열을 활용하는 방식이 있는데 힙의 특성상 배열을 이용하는 것이 훨씬 구현이 편리하다. 우선순위 큐는 힙의 특성을 이용해서 '우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료 구조'이다. 우선순위 큐에서 사용하는 힙의 특성은 '부모 노드는 항상 자식보다 우선순위가 높다'는 성질이다. 이를 활용하여 힙에서는 부모노드를 제거해가면서 우선 순위가 높은 순대로 뽑혀 나오는 것으로 구현했었다. 다만 주의해야할 것은 우선순위 큐가 힙이고 힙이 우선순위 큐는 아니라는 것이다. 힙은 '최솟값 혹은 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 ..

연결리스트 덱 (LinkedList Deque) 배열 덱 다음으로 다루려고 했던 내용이었는데 힙을 급하게 정리해봐야 할 필요가 있어서 힙 다음 순서로 연결리스트 덱을 다루게 됐다. 기본적으로 양방향 연결리스트, 더블 링크드리스트의 개념을 그대로 사용한다. 배열 덱에서와 마찬가지로 구조를 다시한번 짚고 넘어가자. 배열과 다르게 연결리스트를 사용하기 때문에 index로 관리되는 것이 아니라 node 단위로 구성된 객체를 서로 연결하여 구성되어 있다. 양방향 연결리스트를 바탕으로 구현될 것이기 때문에 구조를 다시 한번 보자. 노드는 노드의 데이터, 이전 노드, 다음 노드를 가리키는 변수들을 갖고 있다. 또한 구조는 offer는 기본적으로 offerLast 즉, 마지막에 더해지며 첫번째에 삽입할 수 있는 off..

Heap (Using Array) '우선순위 큐'가 힙 자료구조를 이용하여 구현되기 때문에 힙을 다뤄보려고 한다. 힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'다. 먼저 완전이진트리를 이해해야 한다. 기본적으로 트리의 구조를 먼저 이해해보자. 위의 이미지 같은 자료구조를 Tree 구조라고 한다. 트리에 대해 더 자세히 알아보자 부모노드(parent node) : 자기 자신(노드)과 연결된 노드 중 자신보다 높은 노드를 의미 자식노드(child node) : 자기 자신(노드)과 연결된 노드 중 자신보다 낮은 노드를 의미 루트노드(root node) : 뿌리 노드라고도 하며 루트 노드는 하나의 트리에선 하나만 존재하고 부모 노드가 없다. 최상위 노드이다. 단말노드(..