고코딩

그래프(Graph) 그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결관계를 표현한다. 단순히 정점,노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조라고 할 수 있다. Ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목 등 그래프와 트리의 차이점 오일러 경로 그래프에 존재하는 모든 간선(edge)을 한번만 통과하면 다시 정점(vertex)으로 돌아오는 그래프를 말한다. 그래프에 존재하는 모든 정점에 연결된 간선의 갯수가 짝수일때만 오일러 경로가 존재한다. 그래프(Graph)와 관련된 용어 정점(Vertex): 위치라는 개념. 노드(node)라고도 부름 간선(edge): 위치 간의 관계. 즉, 노드..

문제 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다. 출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 ..

코딩테스트 문제를 풀다가 막히는 문제가 있었다. 내가 지금까지 배운 여러가지 자료구조를 생각해보았지만 딱히 올바른게 떠ㅎ오르지 않아서 힌트를 보았다. 힌트를 보니 '이분 탐색, 해시를 사용한 집합과 맵' 이라는 힌트가 있었다. 해시 예전에 배운것 같은데 정확한 개념이 떠오르지 않고 구현도 할줄 몰랐다. 애초에 이게 자바에서 어떻게 사용해야하는지에 대한 개념도 없었다. 항상 배운것들은 그때마다 정리를 해놔야 까먹지 않는데 늦은 정리를 해보자. 해시? 해시테이블? Hash 단어부터가 너무 어렵다. 코딩은 영어로 되어있다보니 단어로 유추하기도 힘들다. 그래서 두 개념의 차이점을 아는 것이 가장 중요한것 같다. 차이점을 알아야 제대로 쓸 수 있으니까. 해시테이블은 해시함수를 사용하여 키를 해시값으..

문제 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그..

Disjoint set? Disjoint set은 서로 중복되지 않는 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 교집합이 존재하지 않는 둘 이상의 집합을 말하고 데이터 집합을 다룰때 유용하게 쓰인다. 분리집합은 자식 노드가 부모 노드를 가리키는 형태이다. 또한 교집합입 없는 집합이기 때문에 차집합 연산이 있지 않다. 오직 Union-Find알고리즘을 사용하며 배열, 연결리스트, 비트벡터 등으로 이용하여 구현할수 있지만 구조는 트리구조를 가지게 된다. Union 연산 두개의 집합을 합한다. 각 집합의 부모 값을 얻어와 한쪽 부모가 다른쪽 부모를 가르키게 해 한개의 부모만 있는 집합을 만든다. 결국 한개의 집합에는 하나의 부모만을 가지게 된다. //N은 원소들을 넣은 배열 pub..

문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 ..

항상 문제를 풀때마다 힙(heap)에 대한 개념이 많이 헷갈려서 포스팅한다. 다른 분의 블로그에 매우 잘 정리된 포스팅을 가져와 정리해서 쓴 글이다. 힙(Heap) 힙은 이진트리의 일종이다. 반정렬 상태(정렬된 상태가 아니다)이며, 완전이진트리와는 다르게 중복값이 허용된다. 삽입/삭제는 트리 구조이기 때문에 O(logN)이므로 매우 빠르다. 보통 우선순위 큐가 힙으로 많이 구현되는데, 배열과 리스트보다 효율적이다. 힙은 최대힙, 최소힙으로 나뉘어진다. 최대힙은 부모노드가 자식노드보다 큼 이라는 특징을 가지고 최소힙은 부모노드가 자식노드보다 작음 이라는 특징을 가지고 있다. 이러한 특징으로 힙에 값을 넣게 되면 최소힙에서는 최소값 순으로, 최대힙에서는 최대값 순으로 값을 얻을수 있다. 힙 자료구조는 보통 ..

문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는..

문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 예제 입력1 예제출력1 7 3 정답 import java.io...

문제 정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여덟 가지이다. push_front X: 정수 X를 덱의 앞에 넣는다. push_back X: 정수 X를 덱의 뒤에 넣는다. pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 덱에 들어있는 정수의 개수를 출력한다. empty: 덱이 비어있으면 1을, 아니면 0을 출력한다. front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에..

문제 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다. 이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여..

순회는 이진 트리에 있는 모든 노드를 한번씩 방문하여 노드가 가지고 있는 데이터를 처리하는 것이다. 여기서 처리라 함은 노드 안의 데이터를 출력할 수도 있고, 데이터 값을 변환할수도 있다. 순회의 종류에는 총3가지가 있다. 전위순회 중위순회 후위순회 현재 노드를 방문하여 데이터를 읽는 작업을 D또는 V라고 한다. 현재 노드의 왼쪽 서브트리로 이동하는 작업을 L이라고 한다. 현재 노드의 오른쪽 서브트리로 이동하는 작업을 R이라고 한다. 전위 순회 전위 순회의 순서는 현재노드(V) -> 왼쪽 서브트리(L) -> 오른쪽 서브트리(R) 순으로 순회 한다. VLR 이라고도 부른다. 전위 순회로 트리를 순회하면 방문하는 노드의 순서이다. 중위 순회 중위 순회의 순서는 왼쪽 서브트리(L) -> 현재노드(V) -> 오..