분류 전체보기84 Singly Linked List(단일 연결 리스트) (Java) 새로운 노드를 insert할 때마다, 이전에 있던 노드들과 새 노드를 대소 비교한다. 그러면서 더 큰 값이 start(head)와 가깝게, 즉 내림차순으로 list를 형성한다. package LinkedList; public class SinglyLinkedList { class Node { int data; Node next; Node(int data) {this.data = data;} Node(int data, Node next) { this.data = data; this.next = next; } } int size = 0;// 연결 리스트에 저장된 원소의 개수 Node start = null; //연결 리스트를 가리키는 레퍼런스 , start == head // x를 list에 내림차순으로 삽.. 2023. 3. 21. [G4] 백준 1753 - 최단경로 (Python3) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 해결방법 다익스트라 알고리즘을 활용하여 풀었다. 풀이👀 나는 그래프를 python의 dictionary로 표현했다. 그래서 입력받은 간선의 정보들을 모두 graph에 담았다. * 하지만 이렇게 되면 쓸모없는 데이터까지 받아오게 된다. "서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다." 라는 문제 조건이 있기 때문이다. 모든 정보를 담.. 2023. 2. 20. [G4] 백준 11404 - 플로이드 (Python3) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 해결방법 플로이드-워셜 알고리즘을 이용해 풀이했다. 풀이👀 이번 입력은 [출발-도착-비용]이 들어오는데, 출발과 도착 정보가 동일한 입력도 포함된다. 그래서 이런 경우를 대비해주어야 한다. 이 문제는 모든 경로로 이동하는 최소비용 정보를 (출력하라고)요구하고 있다. 그러므로 출발과 도착 정보가 동일하게 주어질 땐 기존 입력값과 비교해서 더 작은 값을 반영해서 이 문제를 풀면 된다. 코드🐱👓 IN.. 2023. 1. 31. [22동계모각코] 8회 계획 및 평가 시작 시간 : 23-01-31 오후 6시 오늘의 목표 플로이드-워셜 알고리즘 공부 플로이드 워셜 알고리즘이란? 모든 노드에서 다른 모든 노드까지 이동하는 최소비용을 구하는 알고리즘이다. 기본 동작은 다익스트라 알고리즘과 비슷하다고 느꼈다. A에서 B까지 이동하는 것보다 A와 B 사이에 k를 지나 도달하는 게 더 저렴한 비용으로 도달할 수 있다는 점에서 이 알고리즘이 만들어진 듯했다. 이 알고리즘은 정해진 점화식에 따라 비용이 수정된다는 점에서 다이나믹 프로그래밍에도 속한다고 한다. D_ab = min(D_ab, D_ak + D_kb) D_ab : a에서 b로 가는 거리(distance) 시간복잡도🕐 입력 노드가 N개 일때, 모든 노드에 대해서 다른 모든 노드(N개)로 가는 경로를 탐색한다. 그렇기 때문에.. 2023. 1. 31. [G5] 백준 1916 - 최소비용 구하기 (Python3) https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 해결방법 다익스트라 알고리즘을 이용한다. 풀이👀 입력에서 버스 이동에 대한 정보를 제공해주고 있다. 순서대로 [출발점, 도착점, (출발->도착)비용] 이다. 각 지점에서는 연결 된 다른 점들로 이동할 수 있다. 이 이동에서 비용이 발생한다. 그런데 이동을 하면서 출발점과 도착점이 같지만 중간에 우회하는 경로를 달리하여 그 비용(결과)를 저렴하게 할 수 있다. 하지.. 2023. 1. 30. [22동계모각코] 7회 계획 및 평가 시작 시간 : 23-01-30 오후 6시 오늘의 목표 다익스트라(Dijkstra) 알고리즘 공부 이렇게 공부한 알고리즘을 정리해보는 것은 처음이다. 그래서 글이 너무 복잡하고, 정리가 안 되어 있다. 오늘은 다익스트라 알고리즘을 공부했다. 다익스트라 알고리즘은 정보 탐색 중에서 최단 경로를 구하기 위한 알고리즘이다. 정보 탐색이란, 탐색에 필요한 정보들을 탐색 전에 미리 알고 있는 경우이다. a에서 b까지의 이동경로를 직접 가보지 않고 미리 알수 있는 경우가 정보탐색인 것이다. 또 다른 특징이 있다면, 비용(cost)의 정보가 모두 음이 아닌 정수여야 한다. 비용 정보가 음수도 포함이 된다면 '플로이드-워셜' 알고리즘으로 해결해야 한댔다. *논외이긴 하지만 정보가 사전에 준비되지 않은 경우에는 다른 탐색.. 2023. 1. 30. [22동계모각코] 6회 계획 및 평가 *5회차는 개인사정으로 불참 시작 시간 : 23-01-24 오후 6시 오늘의 목표 LG Aimers: AI전문가과정 - Module 4. 『딥러닝(Deep Learning)』 - 학습 완료하기 gradient diescent의 기본 개념 neural network의 기본적인 학습 과정에서 사용하는 기본 알고리즘. back propagation 기법 Deep learning이 하나의 합성 함수로 봤을 때에 각각의 편미분을 구할 수 있는 방법 gradient vanishing batch normalization CNN 특정 class에 존재할 수 있는 작은 특정 패턴들을 정의하고, 그 패턴들이 주어진 이미지 상에 존재하는지 판단한다. 지난 학기 '인공지능과 미래사회' 수업에서 배웠던 내용이다. 특징 추출 수.. 2023. 1. 24. [S4] 백준 2417 - 정수 제곱근 (python3) https://www.acmicpc.net/problem/2417 2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net 해결방법 0과 n(n>=0) 의 중앙값의 제곱이 n과 같은지, 큰지, 작은지를 따져보며 q를 구해내는 해결 방법이다. n과 m의 중앙값의 제곱은 앞으로 'n과 m의 중앙제곱'이라고 부르겠다. 만약 0과 n의 중앙제곱이 n과 같다면 그 값이 정답이다. ( 0과 4의 중앙제곱 = 2, 2^2 = 4) 만약 0과 n의 중앙제곱이 n보다 크다면 mid와 n의 중앙제곱을 비교한다. 만약 0과 n의 중앙제곱이 n보다 작다면 0과 mid의 중앙제곱을 비교한다. 위 조건문 안에서는 low와 high를 업데이트 해주는 작업도 반드시.. 2023. 1. 19. 이전 1 2 3 4 5 6 7 8 ··· 11 다음
