썸네일 [알고리즘] 다익스트라(Dijkstra) 알고리즘 1. 다익스트라(Dijkstra) 알고리즘이란? - 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 - 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌. > 모든 정점을 방문하되, 최단 경로로! - "최단 거리는 여러 개의 최단 거리로 이루어져있다."는 다이나믹 프로그래밍의 특성 반영 > 하나의 최단 거리를 구할 때, 그 이전까지 구했던 최단 거리를 그대로 사용 - 가중치가 양수일 때만 사용 가능하다 2. 알고리즘의 동작 단계 (1) 출발 노드, 도착 노드 설정 (2) 출발 노드를 기준으로 각 노드의 최소 비용 저장 (3) 방문하지 않은 노드 중에서 가장 비용이 적은 노드 선택 (4) 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신 > 간선 비용..
썸네일 [알고리즘] 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS) 0. 그래프 탐색 문제란? - 어떤 한 그래프와 해당 그래프의 시작 정점이 주어졌을 때, 시작점에서 간선(Edge, E)를 타고 이동할 수 있는 정점(Vertex, V)를 모두 찾는 문제 - 문제 해결법: 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있다. 1. 너비 우선 탐색(BFS)이란? - BFS (Breadth - First Search) - 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 - 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 - 깊게(Deep) 탐색하기 전에 넓게(Wide) 탐색하는 것 - 두 노드 사이의 최단 경로 / 임의의 경로를 찾을 때 사용 2. 너비 우선 탐색의 특징 - 직관적 X..
썸네일 [Algorithm] 하노이의 탑 알고리즘 (재귀) 💜 하노이의 탑이란? 1) 정의 - 하노이의 탑은 퍼즐의 일종으로, 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 2) 조건 한 번에 한개의 원판만 옮길 수 있다. 가장 위에 있는 원판만 이동할 수 있다. 큰 원판이 작은 원판 위에 있어서는 안 된다 3) 목표 - 세 막대를 왼쪽부터 A, B, C라고 가정하자. - 위 조건에 맞게 모든 원판을 A에서 C로 옮겨야 한다. 💜 어떤 기능을 하는 함수를 구현해야하는가? (문제 정의) - 원반의 이동 횟수를 최소화한다. - 각 원반을 옮기는 모든 순서를 출력한다. => 원반 개수 N개를 입력 받아, 모든 원반을 C막대에 옮기는 모든 과정을 출력한다. ..
[백준] n.3052 - 서로 다른 나머지 개수 구하기 1. 문제 https://www.acmicpc.net/problem/3052 3052번: 나머지 각 수를 42로 나눈 나머지는 39, 40, 41, 0, 1, 2, 40, 41, 0, 1이다. 서로 다른 값은 6개가 있다. www.acmicpc.net 2. 사용 개념 - Scanner - 반복문 (for문), 이중 반복문 - boolean 변수, int 변수 - 1차원 배열 3. 나의 풀이 (*은 잘 안풀린 부분) import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner s = new Scanner(System.in); //*boolean 이용해서 동일여부 판단!!* in..
라이브러리 브랜드 그룹 | 심리학도의 좌충우돌 개발 여행기

티스토리툴바