한켤레

Hashmap(해시맵)이란? Hashmap(해시맵)은 맵 인터페이스를 구현한 대표적인 map 컬렉션이다. 맵 인터페이스를 상속하기 있기에 map의 성질을 그대로 가지고 있다. map은 키와 값으로 구성된 entry 객체를 저장하는 구조를 가지고 있는 자료구조인데, 여기서 키와 값은 모두 객체이다. 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없다. 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다. 해시맵은 이름 그대로 해싱을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 지닌다. 해시맵은 내부에 Key와 Value를 저장하는 자료 구조이다. 해시맵은 해시 함수를 통해 Key와 Value가 저장되는 위치를 결정하므로, 사용자는 그 ..

Hashtable(해시테이블)이란? 해시테이블은 해시 함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 인덱스 또는 주소 삼아 데이터를 Key와 함께 저장하는 자료구조이다. 단순하게 Key - Value로 이루어진 자료구조이다. 데이터가 저장되는 곳을 버킷, 슬롯이라고 한다. Hashtable(해시테이블)의 구성 - Key 고유한 값, 해시 함수의 Input이 된다. Key 값을 그대로 저장소의 색인으로 사용할 경우 Key의 길이만큼의 정보를 저장해야할 공간도 따로 마련해야하기 때문에(Key의 길이가 제각각 일 수 있음) 고정된 길이의 해시로 변경한다. - Hash function(해시 함수) Key를 고정된 길이의 Hash로 변경해주는 역할을 한다. 서로 다른 Key가 Hashing 후 같은 Ha..

연결리스트(LinkedList)란? 연결리스트란 Collection 프레임워크의 일부이며 java.util 패키지에 소속되어있다. 이 클래스는 데이터가 연속된 위치에 저장되지 않고 모든 데이터가 데이터 부분과 주소 부분을 별도로 가지고 있다. 데이터는 포인터와 주소를 사용하여 연결하는데 이때, 각 데이터는 노드라고 불리며 배열에서 자주 삽입, 삭제가 이루어지는 경우에 용이하여 ArrayList보다 선호된다. 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없기 때문이다. 하지만 ArrayList보다 검색에 있어서는 느리다는 단점이 있다. 인덱스가 없기 때문이다. 따라서, 특정 요소에 접근하기 위해서 순차 탐색이 필요로 하여 이가 탐색 속도를 떨어지게 한다. 연결리..

문제 시작 -> 실행 -> cmd를 쳐보자. 검정 화면이 눈에 보인다. 여기서 dir이라고 치면 그 디렉토리에 있는 서브디렉토리와 파일이 모두 나온다. 이때 원하는 파일을 찾으려면 다음과 같이 하면 된다. dir *.exe라고 치면 확장자가 exe인 파일이 다 나온다. "dir 패턴"과 같이 치면 그 패턴에 맞는 파일만 검색 결과로 나온다. 예를 들어, dir a?b.exe라고 검색하면 파일명의 첫 번째 글자가 a이고, 세 번째 글자가 b이고, 확장자가 exe인 것이 모두 나온다. 이때 두 번째 문자는 아무거나 나와도 된다. 예를 들어, acb.exe, aab.exe, apb.exe가 나온다. 이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야 그 결과가 나오는지를 출력하는 문제이다. 패턴에는 ..

문제 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0] × B[0] + ... + A[N-1] × B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다. S의 최솟값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다. 출력 첫째 줄에 S의 최솟값을 출력한다. 예제..

ArrayList란? 자바의 List 인터페이스를 상속받은 여러 클래스 중 하나이다. 일반 배열과 동일하게 연속된 메모리 공간을 사용하며 인덱스는 0부터 시작한다. 배열은 크기가 고정이지만 ArrayList는 크기가 가변적으로 변한다. 내부적으로 저장이 가능한 메모리 용량(Capacity)이 있으며 현재 사용 중인 공간의 크기(Size)가 있다. 만약 현재 가용량(Capacity) 이상을 저장하려고 할 때 더 큰 공간의 메모리를 새롭게 할당한다. JAVA(자바)의 경우 메모리 공간이 1.5배씩 늘어난다. 예시 코드 import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] arg..

배열(Array)이란? 배열은 연관된 데이터를 모아서 관리하기 위해서 사용되는 데이터 타입이다. 변수가 하나의 데이터를 저장하기 위한 것이라면 배열은 여러 개의 데이터를 저장하기 위한 것이라고 할 수 있다. 배열(Array)의 한계 배열을 생성할 때 크기를 정해야 함 (배열에 담을 데이터의 수가 정확하지 않을 때 크기를 정하기 애매함, 배열의 크기를 작게 하면 원하는 만큼의 데이터를 담지 못할 수 있고 크게 한다면 메모리가 낭비될 수 있음) 프로그램을 작성하다보면 배열 중간에 데이터를 삽입하거나 제거해야하는 경우가 생기는데 배열은 변경만 할 수 있음 배열의 원소 값을 중복없이 관리하기 힘들다 -> JAVA의 Collection으로 관리하면 해결 가능 배열(Array)의 예시 코드 /* 배열(array) ..

Queue(큐)란? Queue(큐)는 사전적으로 "줄을 서다"를 의미한다. 줄을 서서 기다린다는 것처럼 먼저 들어오면 데이터가 먼저 나가는 형식이다. 일명 FIFO(FirstInFirstOut) 방식이다. Queue(큐)의 앞 부분인 front 는 삭제 연산만 수행하고, 뒷 부분인 rear 은 삽입 연산만 수행한다. Queue(큐)의 예시 컴퓨터 버퍼에서 주로 사용 여러 개가 한꺼번에 입력이 들어갔을 때 대기열을 만들어 순차적으로 처리할 때 사용 은행 창구 번호표 대기 : 빠른 번호표를 가진 사람이 먼저 업무를 봄 프린터 출력 : 가장 먼저 대기열에 오른 프린트가 먼저 출력 컴퓨터 운영체제의 테스크 스케쥴링 : 가장 간단한 형태의 선입선 처리 스케쥴링 정책 너비 우선 탐색(BFS) 알고리즘 Queue(큐..

Stack(스택)이란? 사전적으로 Stack(스택)은 '쌓다', '더미'라는 의미를 가지고 있다. 데이터의 중복이 허용되며, 순차적으로 데이터를 접근하면서, 이전 데이터와 신규 데이터가 같을 때 연산이 이루어지는 문제에서 사용된다. List(리스트) 인터페이스에서 구현되는 클래스이다. Stack(스택)은 후입선출(後入先出), 즉 Last In First Out - LIFO 특성을 가지는 자료구조이다. 마지막에 추가된 데이터가 가장 먼저 나오는 특징이다. Stack(스택)은 프링글스 통을 떠올리면 된다. 통에 과자를 넣을 때는 먼저 넣겠지만, 꺼내는 것은 가장 위에 있는 것을 꺼내기 마련이다. Java(자바)는 java.util.Stack 클래스를 통해 Stack(스택) 동작을 제공한다. Stack(스택)..

문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을..