백준 2661 좋은 수열 문제는 숫자 1,2,3을 이용하여 수열을 만드는 대신 인접한 수열이 동일한 패턴을 가지면 나쁜 수열에 해당되어 이 나쁜 수열이 아니면서 가장 작은 값을 가지는 수열을 찾아내는 문제이다. 예를 들면 12131212라는 수열을 보면 앞의 7자리 1213121까지는 문제가 없는 수열이지만 뒤에 2라는 숫자가 오게되므로 12/12라는
백준 2579 계단 오르기는 전형적인 dp 문제이다. 이 문제에서의 조건은 돌을 올라가는데 연속 3개의 계단을 밟을 수 없고 계단을 오를때는 1점프 혹은 2점프밖에 할 수 없다는 것이다. 그리고 마지막 계단에 왔을 때 밟아온 계단의 점수를 최대화 하는 것이 문제이다. 이 문제의 핵심은 연속 3개의 계단을 밟을 수 없다는 것이다. 즉 1 2 3 4 라는
DisJointSet은 집합을 나타낼 수 있는 간단한 자료구조이다. 집합은 어떠한 원소들이 하나의 공통 요소에 의해 묶여 있다는 것을 말한다. 위의 그림을 보면 p q r s는 X라는 요소에 묶여 있고 1 2 3 4 5 는 Y라는 요소에 묶여 있다. 즉 이를 구현하기 위해 생각해보면 각 원소들은 X나 Y라는 요소를 가리키고 있다고 생각하면 편하게 된다.
HashTable 또는 HashMap이란 키값을 이용하여 값을 저장하는 구조로 키값을 해시함수에 넣어 인덱스로 변환한 후 테이블에 접근해 저장하는 자료구조이다. 해시테이블은 해시함수를 통해 테이블의 인덱스를 계산하고 이 값을 통해 테이블에 직접 접근하기 때문에 O(1)의 빠른 접근시간을 가지고 있다. 위 그림을 보면 왼쪽에 사람의 이름에 해당하는
우선순위 큐는 Heap의 구조를 이용해 정렬을 수행하는 이진 트리 구조이다. Heap은 원소를 삽입시 가장 큰 원소가 루트 노드에 오도록 노드의 위치를 재배열한다. 이 재배열을 하는 과정은 매번 O(logn)의 시간복잡도를 가지게 된다. 우선순위 큐를 구현하면서 가장 큰 두가지의 기능인 Push와 Pop의 기능을 생각해보자. Push 연산을 하게 되
Stack은 Last In-First Out의 자료구조로 가장 나중에 들어온 원소가 가장 먼저 나오게되는 자료구조이다. Stack은 top이라는 포인터 변수를 두어서 push, pop하며 이 top포인터를 조절하도록 구현된다. Stack 자료구조는 주로 재귀 호출에 주로 사용되게 되고 재귀 호출로 불린 함수는 가장 나중에 불린 함수가 가장 먼저 실행되
Queue는 First in First out의 자료구조로 가장 먼저 들어온 원소가 가장 먼저나가는 선입선출 구조이다. 순서대로 처리해야 할 일을 큐에 집어 넣고 처리할 때 주로 사용되며 알고리즘에서 BFS를 주로 큐를 이용해 구현한다. 12345678910111213141516171819202122232425262728293031323334353637
Linked List는 노드 들간의 연결된 포인터들로 구성되는 자료구조이다. 배열과 같이 원소가 선형으로 저장된다는 특성이 있지만 배열과는 달리 중간에 원소의 삽입 삭제가 가능하고 중간에 있는 원소에 접근하기 위해서는 Head에서부터 순차적으로 접근해서 찾는 방식을 취할 수 밖에 없다. 배열과 Linked List는 다음과 같은 차이점을 가지고 있다.
Database Index1. 인덱스란?데이터베이스에서 원하는 데이터를 검색하기 위해서는 Full-Scan, 인덱스를 통한 검색이 가능하다. DB의 데이터는 삽입된 순서로 정렬되지 않은 형태로 물리적으로 저장되기 때문에 인덱스가 없을 경우 Full-Scan을 통해 자료를 찾아야 하는 비용 발생이 생긴다. n의 시간이지만 데이터가 수억 단위를 넘어가면 효율이
JavaScript 스코프 JavaScript에서 스코프란 변수가 어느 지역에서 유효한 것을 의미하는 중요한 개념이다. JavaScript는 함수를 기반으로 설계 되었기 때문에 기본적으로 함수 레벨의 스코프를 따르게 되는데 이는 C++, JAVA의 변수 유효범위와는 차이를 보인다. 123456789void getArea(bool condition,i