최단 경로말 그대로 가장 짧은 경로를 찾는 알고리즘 종류다익스트라 알고리즘플로이드 워셜 알고리즘벨만 포드 알고리즘다익스트라 최단 경로 알고리즘그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘'음의 간선'이 없을 때 정상적으로 동작일종의 그리디 알고리즘 -> 매번 가장 비용이 적은 노드를 선택하는 과정을 반복각 노드에 대한 현재까지의 최단 거리 정보를 1차원 리스트에 저장하며 계속 갱신간단한 구현 1각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인시간 복잡도 O( V²) - V: 노드 수import java...

다이나믹 프로그래밍DP(Dynamic Programming)중복되는 연산을 줄이는 방식문제를 작은 하위 문제로 나누어 해결한 결과를 저장해 두었다가, 동일한 하위 문제가 다시 나타날 때 이를 재사용하는 방식다이나믹 프로그래밍의 기본 원리중복된 하위 문제:문제를 작은 하위 문제로 나누었을 때, 동일한 하위 문제가 여러 번 반복해서 나타나는 경우.예를 들어, 피보나치 수열 계산에서는 F(n) = F(n-1) + F(n-2)와 같은 형태로, 동일한 계산이 반복된다.최적 부분 구조:문제의 최적해가 하위 문제들의 최적해로 구성될 수 있는 경우.예를 들어, 최단 경로 문제에서는 전체 경로의 최적해가 부분 경로의 최적해들로 구성된다.다이나믹 프로그래밍의 두 가지 접근법1. 탑다운(Top-Down) 접근법 (메모이제이..

이진 탐색순차 탐색리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법순차 탐색 자바 코드 구현// 순차 탐색 소스코드 구현public static int sequantialSearch(int n, String target, String[] arr) { // 각 원소를 하나씩 확인하며 for (int i = 0; i  이진 탐색반으로 쪼개면서 탐색하기배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘배열이 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음시작점, 끝점, 중간점을 사용하여 탐색찾으려는 데이터와 중간점에 위치한 데이터를 반복적으로 비교해서 원하는 데이터를 찾음재귀를 활용한 이진 탐색// 이진 탐색 소스코드 구현(재귀 함수)pu..

정렬1. 선택정렬가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 정렬연산 횟수는 N+(N-1)+(N-2)+ … +2 = (N² + N)/2 번시간 복잡도는 O(N²)이므로 알고리즘 문제 풀이에 사용하기에는 느림2. 삽입정렬첫 번째 데이터가 정렬되어 있다고 가정하고 두 번째 데이터부터 탐색하여 첫번째 데이터보다 작으면 앞, 크면 뒤에 삽입한다.삽입 정렬은 데이터가 거의 정렬 되어 있을 때 훨씬 효율적삽입 정렬의 시간 복잡도는 시간 복잡도는 O(N²)지만 데이터가 거의 정렬되었을 때는 빠르게 동작하여 최선의 경우 O(N)의 시간 복잡도를 가짐3. 퀵정렬피벗을 선정하여 피벗보다 작은 값을 왼쪽으로, 큰 값을 오른쪽으로 분..

[자료구조] Stack, Queue 그리고 DequeStack, Queue, Deque스택(Stack)박스 쌓기에 비유할 수 있다.선입후출(FILO) 구조 또는 후입선출 구조스택의 메서드큐대기 줄에 비유할 수 있다.선입선출(FIFO) 구조큐의 매서드 간단한 스택과 큐 구현publjaemin0604.tistory.com이전 글에서 공부한 스택, 큐, Deque를 활용하여 DFS/BFS를 알아보고자한다. 들어가기전에.... 인접행렬 vs 인접리스트인접행렬2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 장점:두 정점 사이에 간선이 존재하는지 O(1) 시간에 확인할 수 있다.구현이 단순하고 직관적이다.단점:공간 복잡도가 O(V^2)이다. 따라서 정점의 수가 많아지면 비효율적이다.간선의 수가 적은 그래프(희..

구현- 떠올린 아이디어를 코드로 구현하기 1. 완전 탐색- 모든 경우의 수를 주저 없이 계산하는 해결 방법 2. 시뮬레이션- 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 방법 예시 - 상하좌우 문제좌표가 주어지고 이동방향이 주어졌을 때 도착할 지점의 좌표를 출력하는 문제static int n;static char[] plans; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); StringTokenizer st = new St..

그리디 알고리즘(Greedy)- 탐욕법- 현재 상황에서 지금 당장 좋은 것만 고르는 방법- 매 순간 가장 좋아 보이는 것을 선택하며, 나중에 미칠 영향에 대해서는 고려하지 않는다.그리디에서 중요한 것은- 창의력 -> 문제를 풀기위한 아이디어를 떠올릴 것 -> 정당한지 검토할 수 있어야할 - 특정 문제를 만났을 때, 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야함  그리디 알고리즘 주요 속성1. 탐욕적 선택 속성 (Greedy Choice Property):각 단계에서 탐욕적으로 선택한 것이 항상 최적이라는 것을 보장합니다.즉, 각 선택 시점에서 지금 당장 최적인 선택을 하며, 그 선택이 최종적으로 최적해로 이어질 수 있어야 합니다. 2. 최적 부분 구조 ..

1. 델타 delta- 상하좌우를 이동하는 기법static int dy[] = { -1, 1, 0, 0};static int dx[] = { 0, 0, -1, 1};주의할 점상하좌우 이동하면서 배열의 인덱스 값 범위에서 벗어나는지 검사델타 활용 예시static void print(int y, int x) { for (int d = 0; d = 5 || nx >= 5 ) break; //인덱스 범위 검사 System.out.print(map[ny][nx]); } } System.out.println();} - dx, dy를 조절하여 대각선 이동도 가능static int dy[] = { -1,-1, 1, 1};static int dx[] = { -1, 1, -1, 1}; - 8방향 이동stati..

자바 입력1. 개요일반적으로 자바에서는 Scanner를 사용하여 입력을 받습니다.하지만 Scanner는 입력을 처리할 때 상대적으로 느립니다.특히 많은 양의 입력을 처리해야 하는 경우, BufferedReader에 비해 성능이 떨어집니다.따라서 코딩테스트에서 주로 사용되는 방법은 BufferedReader와 InputStreamReader입니다.2. 자바의 입력 클래스BufferedReader & InputStreamReaderBufferedReader br = new BufferedReader(new InputStreamReader(System.in));String str = br.readLine();System.in -> 표준 입력 스트림으로, 사용자가 콘솔에 입력하는 바이트 데이터를 읽습니다.Inp..