고양이 두 잔

목차 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러 개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 $-2^{31}$보다 크고, $2^{31}$보다 작다. 출력 ..

파이썬으로 알고리즘을 풀다가 enumerate()라는 내장함수를 만나게 되었다. 이 함수의 역할은 순회 가능한(iterable) 객체(리스트, 튜플, 문자열 등)를 입력받아 인덱스와 해당 요소를 동시에 포함하는 iterator를 반환한다. 이를 이용해 반복문에서 인덱스와 요소를 동시에 다룰 수 있으며, 필요하다면 딕셔너리와 같은 자료형으로 매핑할 수도 있다. 바로 코드로 예를 들어보자. fruits = ['apple', 'banana', 'orange'] # 리스트의 인덱스와 값을 출력 for index, fruit in enumerate(fruits): print(index, fruit) 0 apple 1 banana 2 orange 시작 인덱스를 0이 아닌 1로 지정하는 것도 가능하다. fruits ..

목차 Index 인덱스란 말 그대로 색인이다. 여기선 주어진 데이터베이스에서 원하는 자료를 빨리 찾을 수 있도록 도와주는 일종의 자료구조라 할 수 있다. 원하는 테이블의 컬럼(둘 이상도 가능하다)에 인덱스를 생성한다는 말은 데이터베이스 내부에서 해당 컬럼이 저장된 주소값을 가지는 자료구조를 테이블과 논리, 물리적으로 독립된 구조로 설계하는 것을 가리킨다. 이때 생성되는 인덱스는 컬럼의 값과 물리적 주소를 키/밸류로 가지는 구조를 가지며, 이를 이용해 빠른 탐색이 가능해진다. 참고로 인덱싱을 하지 않은 테이블의 경우, 원하는 값을 얻어내기 위해 모든 테이블을 스캔하는 Table Scan을 실행하며, 이는 최악의 경우 O(n)의 시간복잡도를 가지게 된다. 더 나가기 전에 장/단점과 인덱싱을 사용하기 좋은 환..

Hash 배열은 빠른 검색 속도를 가지고 있으나 삽입/삭제 시 많은 비용이 소모된다. 이를 극복한 LinkedList는 삽입/삭제의 비용이 적지만 데이터가 많아질수록 검색에 비용이 많이 든다. 해시는 이를 극복하기 위해 도입된 개념이다. 해시, 해시 함수(Hash Function)란 임의의 길이를 갖는 임의의 데이터를 받아 고정된 길이의 데이터를 리턴하는 단방향 함수를 말한다. 가장 쉬운 예로는 나머지 연산자(%)가 있을 수 있겠다. 해시 함수의 특징은 아래와 같으며, 비교적 간단한 알고리즘으로 시스템 자원을 덜 소모한다, 즉 해시값 생성에 많은 시간이 들지 않는다. 해시값을 해독할 때는 많은 시간이 든다. 같은 입력 값에 대해선 같은 출력 값이 보장되며, 출력 값은 고르게 분포한다. 입력값이 아주 조금..

문제 숫자 카드는 정수 하나가 적혀 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어 있다. 이 수..

으로 구현한 다른 정렬: [Java+Python]삽입 정렬(Insert Sort) [Java+Python]버블 정렬(Bubble Sort) [Java+Python]선택 정렬(Selection Sort) [Java+Python]병합 정렬(Merge Sort) [Java+Python]힙 정렬(Heap Sort) [Java+Python]카운팅 정렬(Counting Sort) 퀵 정렬은 1959년 영국에서 태어난 정렬 방식이다. 직관적인 이름대로 일반적으로 비슷한 속도의 병합 정렬, 힙 정렬보다 빠른 성능을 나타내며 힙 정렬과 추가적인 메모리를 요구하지 않기 때문에 자원 이용에 이점이 있다. 다만 안정 정렬이 아니라는 단점이 있어 파이썬에서는 도입하지 않고 있다고 한다. 추가로 데이터 접근 시간이 오래 걸리는 ..

으로 구현한 다른 정렬: [Java+Python]삽입 정렬(Insert Sort) [Java+Python]버블 정렬(Bubble Sort) [Java+Python]선택 정렬(Selection Sort) [Java+Python]병합 정렬(Merge Sort) [Java+Python]퀵 정렬(Quick Sort) [Java+Python]카운팅 정렬(Counting Sort) 힙 정렬은 말 그대로 힙 자료구조를 이용해 정렬하는 방식을 말한다. 왜 힙 트리가 아니라 힙 자료구조라고 하냐면.. 힙 트리는 구현될 때 주로 배열을 이용하기 때문이다. 힙 트리에 대해선 지난번에 정리해둔 글이 있으니 참고. 2022.09.28 - [Development/Java] - [Java]자료구조 - 힙 트리(Heap Tree) ..

공부를 하고 프로젝트를 하면서 노드라는 단어를 참 많이 듣기도 했고 쓰기도 했다. 그래도 그림자를 따라다니는 기분을 지울 수가 없어서, 내가 사용하는 범위 안에서만 정리하고 가자. 시작하기 전에, 노드는 맥락과 분야에 따라 굉장히 다양한 의미를 가지며, 내가 정리한 것은 오로지 내가 현재 관심 있는 분야에 한정된 자료에 불과하다. Node - Data Structure 자료 구조를 배울 때, 특히 링크드 리스트나 트리, 더 일반적으로는 그래프에 대해 배울 때 노드라는 단어를 처음 만난다. 자료구조에서의 노드란 추상적으로 말하면 구조의 기본 단위, 트리나 그래프로 치면 정점이라고 할 수 있으며 덜 추상적으로 말하면 메모리 곳곳에 흩어져 있는 데이터의 조각, 혹은 그 기본적인 단위를 가리킨다. 추가로 링크드..

목차 스택, 큐, 트리, 그래프에 대해선 지난번에 짧게 요약했다. 이번 글에선 자료구조 중 배열 + 컬렉션 프레임워크에 대해 가능한 짧게 요약한다. Array 배열은 한 마디로 말하면 같은 자료형과 길이가 정해진 행렬이라고 할 수 있다. 행렬이기 때문에 인덱스가 정의되어 있고, 메모리를 연속으로 사용할 것을 요구하기 때문에 각각의 값은 변경할 수 있으나 한 번 정해진 크기는 바꿀 수 없다. 또한 엄밀하게 말하면 자바의 배열은 기본적으로 제공하는 자료형이기 때문에 다양한 관련 함수가 정의되어 있으며, 별도의 호출 없이 손쉽게 정의할 수 있다. 배열은 자료형인가? 결론부터 말하자면 자바에서 배열은 자료형이며 동시에 자료구조로도 분류할 수 있다. 자료형은 변수의 타입을 가리키는 단어이며, 자료구조는 데이터의 ..

자료구조에서의 그래프는 굉장히 일반적인 개념이고 그 예가 많지만, 특정 기준을 이용해 둘로 나누면 아래와 같이 구분할 수 있다. 바로 무방향 그래프(G1)와 방향 그래프(G2)인데, 이와 같은 자료구조를 자바에 구현하는 방법은 크게 두 가지가 존재한다. 하나씩 알아보자. Adjacency Matrix 인접 행렬은 말 그대로 노드간의 관계를 행렬로 나타낸 것이다. 노드가 n개인 그래프의 인접행렬은 n X n 정사각 행렬이 되며, 인접한 경우엔 1, 그렇지 않은 경우엔 0을 채워 넣는다. 추가로 무방향 그래프의 경우엔 인접 행렬이 대칭을 이루고 있는 것이 특징이다. 방향 그래프의 경우엔 반드시 대칭 행렬을 이루지는 않는다. 인접 행렬의 장점은 노드 사이의 빠른 경로를 찾기 편하다는 점이며 단점은 간선의 유무..