기기

자료구조 구현 1. 자료구조 특징 정리 2. 자료구조 특징에 사용될 변수를 정의한다. 3. 자료구조 특징에 따라 구현한다. 구현 시, 변수를 어떻게 활용할지 고려 4. 자료구조 '최대 입력', '비었을때 제거'와 같이 경계영역? 예외 처리 해준다. ex) 배열 크기, 포인터 역할의 변수 ( 경계 영역에서 어디를 가리켜야 하는지 ) 스택 1. Last In First Out 2. top 이용 마지막 원소의 인덱스 3. 구현 시 주의할 점 pop() 스택이 빈 경우 push() 스택이 다 찬 경우 배열을 이용한 스택 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 static class mySta..

일렬로 늘어선 자료를 저장하기 위한 자료구조. 종류 정적 배열 동적 배열 연결 리스트 정적 배열 - 데이터가 메모리에 연속적으로 저장된다. - 크기가 고정이다. - 시간 복잡도 인덱스를 알면 O(1)로 접근 가능 ( Random Access ) 동적 배열 - 데이터가 메모리에 연속적으로 저장된다. - 크기(capacity)가 동적으로 증가한다. 자바에서 대표적으로 ArrrayList가 동적배열이다. - 시간 복잡도 인덱스 통한 접근 O(1) ( Random Access ) capacity 증가 시, 배열을 복사 후 더 큰 배열로 옮기기 때문에 O(N) 삽입/삭제 시, 기존 원소들의 shift 연산이 필요해서 최악으로 O(N) ex) 첫 번째에 삽입/삭제는 기존의 모든 원소들을 밀어야 하기 때문에 O(N)..

모든 쌍 최단 거리 알고리즘 단일 시작점 최단 거리 알고리즘인 다익스트라, 벨만 포드와 다르게 모든 쌍 최단 거리 알고리즘이다. 음수 사이클이 없는 음수 가중치에서도 작동한다. vs 다익스트라, 벨만포드 단일 시작점 최단 거리 알고리즘을 모든 정점에서 실행하여도 모든 쌍 최단 거리 알고리즘을 구할 수 있다. 하지만, 구현하기에 플로이드 워샬이 더 간단하다. 또한, 간선이 많은 경우에도 시간 복잡도가 더 낫다. 모든 쌍 최단 거리 시간 복잡도 다익스트라 O(V x ElgE) 벨만포드 O(V x VE) 플로이드 O(V^3) 핵심 1 dist[u][v] 2차월 배열의 dist[u][v]를 사용한다. u에서 v까지의 최단거리 유지 이동 불가능한 경우는 큰 수로 초기화하며 동일한 정점의 경우는 0으로 초기화한다...

벨만-포드 알고리즘이란? (Bellman-Ford's algorihm) 1. 단일 시작점 알고리즘 시작점에서 다른 모든 정점까지의 최단 거리를 찾는다. 2. 방향 그래프 방향 그래프를 가정으로 둔다. 따라서, 무방향 그래프가 주어진다면 간선을 쪼개 방향 그래프로 바꿔야 한다. 3 음수 가중치 음수가 아닌 가중치만 다루는 다익스트라와 다르게 음수 가중치에서도 최단 거리 문제를 정의할 수 있는 알고리즘이다. 또한, 음수 싸이클로 인해 최단 거리를 정의할 수 없는 경우도 알아낼 수 있다. 동작 과정 1 상한을 두고 최단 거리 줄여나가기 upper[i] : 정점 i까지의 최단 거리의 상한을 의미한다. 알고리즘이 진행되며 upper 오차를 줄여나간다. 최종적으로 작동이 완료되면 upper값들이 최단 거리가 된다...

[ 백준 14501 ] 퇴사 ( java ) 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일2일3일4일5일6일7일TiPi 3 5 1 1 2 4 2 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, ..

다익스트라(Dijkstra) 알고리즘이란? 1. 단일 시작점 최단 거리 알고리즘 시작점에서 다른 모든 정점까지의 최단 경로의 길이를 찾는 문제 2. 방향 그래프 방향 그래프를 가정으로 둔다. 만약 무방향 그래프가 주어진다면 간선을 쪼개 방향 그래프로 바꿔서 생각 3. 0 이상 가중치 음수 가중치가 있으면 안 된다. 다익스트라는 정점을 지날수록 가중치가 증가한다라는 사실을 전제하고 쓰인 알고리즘이다. 음수 가중치가 있다면 전제가 이전까지 계산해둔 최소가 최소라고 보장할 수 없기 때문이다. 4. BFS를 기본으로 한다. BFS처럼 시작 정점에서 가까운 순서대로 방문한다. 방문한 정점은 최단 거리가 정해진다. 5. 탐욕(greedy) 알고리즘 다익스트라는 탐욕 알고리즘의 종류라고 볼 수 있다. 탐욕 알고리즘은..

[ 백준 13458 ] 시험 감독 ( java ) 총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다. 감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 방에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 방에서 감시할 수 있는 응시자의 수가 C명이다. 각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다. 각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다...

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