1. 해시란? Set 자료구조의 특성을 살펴보기 전에 Hash의 개념을 먼저 정리해보겠습니다. 해시 함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수입니다. 이때, 매핑하기 전 입력 데이터의 값을 키(Key), 매핑 후 출력 데이터의 값을 해시코드(HashCode), 매핑하는 과정 자체를 해싱(Hashing)이라 부릅니다. 해시의 특징은 다음과 같습니다. 동일한 입력 값에 대해서는 항상 동일한 출력 값이 보장된다. 출력 데이터 값을 가지고 원본 입력 데이터의 값을 알아낼 수 없다. 일반적으로 해시 함수는 그리 복잡하지 않은 알고리즘으로 구현되기 때문에 CPU, 메모리 자원을 크게 소비하지 않는다. 입력 값의 범위보다 출력 값의 범위가 좁기 때문에 다른 입력 데이터에 대..
1. 개요 배열의 장단점은 다음과 같습니다. 장점 항목 접근 속도가 빠르고 일정하다. 배열의 원소들은 모두 연속된 메모리 위치에 저장되기 때문에 인덱스를 통해 가장 빠르게 원소를 참조하거나 변경할 수 있다. 단점 사용하기 전에 배열 크기를 지정해야하고, 지정한 크기로 고정된다. 정해진 크기를 넘겨서 데이터를 저장하려 한다면, 더 큰 크기의 배열을 새로 할당받아 사용해야 한다. 삽입/삭제가 힘들다. 배열의 중간에 원소를 삽입/삭제할 경우, 나머지 원소들의 연속적인 순서를 맞추기 위해 삽입/삭제가 이루어진 위치 뒤의 모든 데이터들을 모두 한 칸씩 앞으로 당기거나, 뒤로 밀어야한다. 원소들을 모두 옮기는데 드는 시간복잡도는 O(n)이다. 메모리를 한 덩어리로 차지하므로, 배열 크기가 클 경우 배열 전체를 위한..
1. Index란? 혹시 테이블에 데이터를 저장할 때 특정 컬럼을 기준으로 정렬하여 저장하고싶다는 생각을 해보신적 있으신가요? 🤔 그런게 왜 필요하냐구요? 알고리즘을 공부해보신 분들은 아실겁니다.. 탐색의 전제는 정렬이라는 것을요 ! 만약에 '이름'이라는 컬럼이 있고 제가 홍길동이라는 이름을 가진 데이터를 검색하고싶을 때, '이름'을 기준으로 정렬이 되어있다면 맨 뒷쪽의 'ㅎ'부터 찾아나가면 될 것입니다. Index는 바로 이런 특정 컬럼을 기준으로 정렬하여 데이터를 저장해놓고 싶을 때 사용합니다. 2. Clustered Index란? 아래와 같이 DB에 10개의 데이터를 저장한다해보겠습니다. 위와 같은 데이터를 SQL문을 통해 DB에 저장하게되면, 내부적으로 아래와 같은 Data Page 단위로 저장됩..
문제 풀이 개인적으로 많이 어려웠던 문제. 해당 문제에서 요구하는 요구사항은 크게 2가지다. 주어진 맵(윷놀이판)을 어떻게 표현할 것인가? 10개의 턴에 대한 4개의 말 순서 배치는 어떻게할 것인가? (순열 --- 백트래킹 알고리즘 이용) 먼저 첫 번째 요구사항을 보자. 주어진 윷놀이판을 1차원으로 보기 쉽게끔 나타내면 다음과 같다. 위의 1차원 구조에서 포인트는 10, 20, 30은 두 가지 방향을 가진다는 것이다. 그럼 노드가 가져야할 정보는 다음과 같다. 해당 칸의 점수, 해당 칸이 비었는지(다른 말이 있는지), 지름길(파란 방향)이 있는지, 도착점인지 배열에 담아도 되지만, 그보다는 연결 리스트로 담는게 좀 더 직관적이라 생각한다. ( 개인적으로 아래와 같이 연결 리스트를 만들어 사용해보는건 처음..
문제 풀이 문제를 단순화해보자. 예를 들어, 주어진 문자열이 다음과 같이 2개 주어졌다면 ABC BCDE 위의 문자열에서 사용된 문자는 A B C D E ---> 5개다. 즉, 0~9까지의 수열에서 5개의 부분수열을 구하는 문제로 바라볼 수 있다. 입력 문자열과는 별도로 어떤 문자들이 사용되었는지 파악이 필요한데, 아래와 같이 List 자료구조에 하나씩 순차적으로 담는다. for (int i = 0; i < N; i++) { words[i] = br.readLine(); // 입력 문자열 for (int j = 0; j < words[i].length(); j++) { if (!alpabetList.contains(words[i].charAt(j))) { alpabetList.add(words[i].ch..
문제 풀이 N개의 수열에서 M개의 수열을 찾는 N과 M 문제와 비슷하다. 0~9의 고정된 수열이 있고, 주어진 부등호 조건을 만족하는 수열을 찾으면 된다. DFS 탐색의 깊이(인덱스)가 주어진 부등호의 갯수+1을 만족한다면 해당 수열은 부등호 조건을 만족하는 수열이다. 조건에 만족하는 모든 수열을 list에 모두 저장한 후, 정렬한 다음 처음과 마지막 값을 출력한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { private static BufferedReader br = new BufferedReader(n..
문제 풀이 개인적으로 되게 어려웠던 문제였다. 풀이를 보면서도 많은 시간 고민했다. 첫 번째로 고민했던건 주어지는 가로선의 정보를 어떤 식으로 저장할까였다. 그동안 풀었던 문제는 대게 칸으로 주어졌기 때문에 별 생각없이 map[y][x] 에 저장하면 됬지만, y축과 x축이 칸이 아닌 선으로 주어져서 고민했는데, 그냥 아래처럼 칸이라 생각하고 똑같이 저장하면 되겠다라고 생각이 들었다. 위의 그림에서 최상단 좌측을 (1, 1)이라 두고, 값이 저장되는 세 가지 경우를 나눴다. 0 : 해당 칸에는 가로선이 없다. 1 : 해당 칸을 기준으로 우측으로 연결되는 가로선이 있다. 2 : 해당 칸을 기준으로 좌측으로 연결되는 가로선이 있다. 1번 높이의 1번과 2번 세로선을 연결하는 가로선이 있다면, map[1][1]..
[백준 6549 : JAVA] 히스토그램에서 가장 큰 직사각형 / 세그먼트 트리 +분할정복
2020.11.02
문제 풀이 해당 문제는 두 가지 방법으로 풀 수 있다. 스택 세그먼트 트리 + 분할정복 해당 풀이는 두 번째 방법이다. 먼저, N=7의 길이를 가지는 수열에 대해 각 세그먼트 트리의 노드에 저장될 구간은 다음과 같다. 세그먼트 트리는 구간 합에 대한 문제를 통해 처음 배우기 때문에 각 노드에 어떤 값을 저장해야할지 감이 오지 않을 수 있다. (난 그랬다..) 세그먼트 트리에서의 핵심은 구간에 대한 어떤 값을 저장한다는 것이다. 이제 루트 노드에 1~7번째 구간에 대한 값을 저장해야하는데, 어떤 값을 저장해야할까? 첫 번째로 생각해볼 수 있는 값은 '넓이' 값이다. 최소 높이를 따라야하기 때문에 1~7번째 구간에서의 넓이 값은 (가로: 1 * 7) * (세로: 1) = 7 이다. 그런데, 넓이를 구하기 위..
슬라이딩 윈도우 알고리즘은 투 포인터 알고리즘과 개념이 유사하다. 투 포인터 알고리즘 같은 경우 left와 right라는 처음과 끝을 가리키는 포인터가 서로 독립적으로 움직이는데에 반해, 슬라이딩 윈도우 알고리즘은 처음과 끝을 가리키는 포인터가 서로 같이 움직인다. 슬라이딩 윈도우라는 이름 그대로 고정된 윈도우가 슬라이딩하는 것처럼 움직인다. 처음과 끝에 대해서 삽입과 삭제가 빈번히 이뤄지기 때문에 디큐(Deque) 자료구조가 대게 같이 사용된다.
문제 풀이 문제를 이해하는데 시간이 좀 걸렸다. 최단 경로에서 고도 차가 아니라, 가장 낮은 고도차(피로도가 가장 적은)를 구하는 문제. 먼저, 입력받은 고도에 대해 중복없이 배열(리스트)에 저장한 후, 정렬한다. 정렬된 고도 값을 담은 1차원 배열에 대해 투 포인터를 잡고, BFS 탐색 조건을 건다. 1) 다음으로 탐색할 땅의 고도가 투 포인터로 잡은 최저 고도보다 크거나 같고, 최고 고도보다 작거나 같다. 위의 탐색 조건으로 탐색을 끝낸 후, 모든 집을 방문했는지 여부를 확인한 다음 고도 차를 저장해 나간다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java...
문제 풀이 투 포인터 알고리즘 기본 유형에 속하는 문제다. 해당 문제에서 유심히 봐둬야할 것은 모듈러(%) 연산을 통해 N-1을 넘어가는 인덱스부터는 0으로 계산되도록 처리한 부분이다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); private static int N, d, k, c; private static int[] arr..
1차원 배열이 주어졌을 때, 특정 연속된 구간의 합이 M이 되는 경우의 수를 구하려면 어떻게 해야 할까? 가장 단순하게 생각해볼 수 있는 방법은 2중 반복문을 돌리는 것이다. public class Main { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 2, 5, 3, 1, 1, 2}; // 크기가 10인 1차원 배열 int m = 5; // 연속된 구간의 합이 5인 경우를 찾는다. int count = 0; for (int i = 0; i ..