Algorithm & 자료구조

힙(heap)이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙 종류 최대 힙(max heap) 부모 노드 값이 자식 노드의 값보다 크거나 같음 루트 값은 저장된 원소 중 가장 큼 최소 힙(min heap) 부모 노드 값이 자식 노드의 값보다 작거나 같음 루트 값은 저장된 원소 중 가장..

1. 연결리스트(Linked List)란? LinkedList는 Node라는 객체로 이루어져 있는데 Node는 데이터를 저장하는 field와 다음 노드를 가리킬 수 있는 next pointer field로 구성이 되어있습니다. 이말인 즉슨, 이 노드들이 연결된 형태의 자료구조를 바로 LinkedList라고 하는 것입니다. 예를 들어, 학교에서 어느 반의 모든 학생들의 데이터를 저장한다고 했을 때, 학생 한명 한명의 신상정보 자료를 노드로 만들고, 1번 학생의 신상정보 자료에 2번 신상정보 자료가 어디 있는 지 표시를 해 놓는 방식인 것입니다. 쉽게 말해서 줄줄이 소세지마냥 자료를 엮어 놓은 것이라고 생각하면 되겠습니다. 반면, 배열은 학생들의 데이터를 한 곳에 쭉 쌓아 올린 모양새라고 생각하면 됩니다. ..

HashMap 이란? Map 인터페이스를 구현하고 있는 대표적인 자바 클래스. key-value쌍으로 되어있다. Map의 대표적인 특징은 key는 정확히 하나의 value만 가질 수 있다. 순서는 유지되지 않는다.(순서가 유지되어야 하는 경우 LinkedHashMap사용) 동일 키값으로 추가 시 덮어쓰기 된다. value값엔 null값도 넣을 수 있다. 해싱 검색을 사용하기 때문에 대용량 데이터 관리 시에 좋은 성능을 보인다. 위 그림과 같이 HashMap은 내부에 키와 값을 저장하는 자료 구조를 가지고 있다. 해시 함수를 통해 키와 값이 저장되는 위치를 결정하므로, 그 위치를 알 수 없고 삽입되는 순서와 들어 있는 위치 또한 관계가 없다.(삽입한 순서에 따라 정렬되지 않는다.) HashMap은 왜 필요..

배열의 기본 구조 배열 생성시, 크기가 고정된다. 배열의 인덱스는 0부터 시작된다. 위 예시는 int(정수) 배열을 나타낸다. 정수 배열은 4바이트 단위로 이루어ㅊ져 있어, 메모리 주소(memory address)의 시작 위치를 1000, 1004, ..., 1020로 나타낸다. 배열의 특징 연속된 메모리의 공간에 순차적으로 데이터를 저장하는 선형 자료구조이다. 많은 수의 데이터를 다룰 때 사용하는 자료구조 각 데이터를 인덱스와 1:1 대응 데이터가 메모리상에 연속적으로 저장 배열 생성시 크기를 미리 설정해야함 메모리는 배열이 선언될 때(컴파일 할 때) Stack영역에 할당한다. 배열의 장점 인덱스를 이용하여 데이터에 빠른 접근 시간 복잡도; O(1) 자료 구조의 크기가 클수록 더 강력한 장점 연속된 메..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 2023.10.17 - [Language/Java] - Queue Queue Queue란? Queue의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미하는데 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조입니다. 큐는 데이터를 burning-go9me.tistory.com Queue 를 이용해서 풀어 볼 수 있는 예제 Queue 메소드들을 이용 ..

Queue란? Queue의 사전적 의미는 무엇을 기다리는 사람, 차량 등의 줄 혹은 줄을 서서 기다리는 것을 의미하는데 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조입니다. 큐는 데이터를 일시적으로 쌓아두기 위한 자료구조로 스택과는 다르게 FIFO(First In First Out)의 형태를 가집니다. FIFO 형태는 뜻 그대로 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말합니다. Enqueue : 큐 맨 뒤에 데이터 추가 Dequeue : 큐 맨 앞쪽의 데이터 삭제 Queue의 특징 1. 먼저 들어간 자료가 먼저 나오는 구조 FIFO(First In FIrst Out) 구조 2. 큐는 한 쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행함 3. 다른 한 쪽 끝은 리어(rear)로 정..

복잡도 ✔ 알고리즘 성능을 나타내는 척도 ✔ 시간 복잡도 (Time Complexity) - 알고리즘의 필요 연산 횟수 ✔ 공간 복잡도 (Space Complexity) - 알고리즘의 필요 메모리 ✔ 시간 복잡도와 공간 복잡도는 Trade-off 관계 시간 복잡도 ✔ 어떤 문제를 해결하기 위한 알고리즘의 필요 연산 횟수 ✔ 빅오(Big-O) 표기법을 통해 나타냄 공간 복잡도 ✔ 어떤 문제를 해결하기 위한 알고리즘의 필요 메모리 사용량 ✔빅오 표기법을 통해 나타냄 - 일반적으로 메모리 사용량 기준은 MB 단위 // 기초 수학 - 알고리즘 복잡도 public class Main { static int fibonacci(int n) { if (n < 3) { return 1; } return fibonacci..

점화식 ✔어떤 수열의 일반항을 그 이전의 항들을 이용하여 정의한 식 예시) 피보나치 수열 재귀함수 ✔ 어떤 함수가 자신을 다시 호출하여 작업을 수행하는 방식 제곱, 제곱근, 지수 제곱 ✔ 같은 수를 두 번 곱함 ✔ 거듭 제곱: 같은 수를 거듭하여 곱함 제곱근 ✔ a를 제곱하여 b가 될 때 a를 b의 제곱근이라고 함 로그 ✔ a가 b가 되기 위해 제곱해야 하는 수

팩토리얼 ✔ 1에서 n까지 모든 자연수의 곱 (n!) 순열 ( Permutation ) ✔ 순서를 정해서 나열 ✔ 서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 O, 중복 X) 중복순열 ✔ 서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 O, 중복 O) 원 순열 ✔ 원 모양의 테이블에 n개의 원소를 나열하는 경우의 수 조합(Combination) ✔ 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 X) 중복 조합 ✔ 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 O)

문제링크 https://www.acmicpc.net/problem/25556 25556번: 포스택 포닉스가 순열을 청소할 수 있으면 YES, 불가능하다면 NO를 출력한다. www.acmicpc.net 위 문제는 stack을 이용해서 푸는 골드4 단계 문제이다 아래 stack 참조 2023.10.16 - [Language/Java] - Stack Stack Stack 이란 ? 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 사전적 정의는 '쌓다' 상자에 물건을 쌓아 올리듯이 데이터를 쌓는 구조로 그 접근 방법은 언제나 목록의 끝에서만 일어난다. burning-go9me.tistory.com 내 풀이 import java.util.ArrayList; import java.util.List; i..