Study Platform📚/(알고리즘)- [이코테] 이것이 코딩테스트다 정리
[이코테]CHAPTER 09 최단 경로 알고리즘 - 플로이드워셜 알고리즘 - Python(파이썬),Java(자바)
[이코테]CHAPTER 09 최단 경로 알고리즘 - 플로이드워셜 알고리즘 - Python(파이썬),Java(자바)
2022.06.11참고자료 : https://www.youtube.com/watch?v=acqm9mM1P6o 📎 다익스트라(Dijkstra) 알고리즘과 플로이드 워셜(Floy-Warshall) 알고리즘의 차이 1) 다익스트라(Dijkstra) 알고리즘 - 자세한 설명은 : https://coooco.tistory.com/36?category=1071114 - 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우에 사용하는 알고리즘 - 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택 -> 해당 노드를 거쳐가는 경로 확인 -> 최단 거리 테이블 갱신 - 그리디 알고리즘 2) 플로이드 워셜(Floy-Warshall) 알고리즘 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용하..
CHAPTER 6 -번외 정렬 - 위상 정렬(Topology Sort) - Python(파이썬)
CHAPTER 6 -번외 정렬 - 위상 정렬(Topology Sort) - Python(파이썬)
2022.06.08참고 자료 : https://m.blog.naver.com/ndb796/221236874984 위상 정렬 : 순서가 정해져 있는 작업을 수행해야 할 때 그 순서를 정해주기 위해서 사용하는 알고리즘 ex ] 0번 -> 1번 ->3번 -> 5번 순으로 이어진 후에 4번이 나오기 전에 2번 만족 이런식으로 그래프의 흐름이 있고 다양한 조건들이 얽혀있을 때 일렬로 그래프의 순서를 나열할 수 있어야함 ex] 0 -> 1 -> 3 -> 5 -> 2 -> 4 -> 6 1. 위상 정렬의 특징 - 여러개의 답이 존재 할 수 있다 - DAG(Directed Acyclic Graph)에만 존재(방향그래프이지만 사이클이 존재하지 않는 그래프) -> 사이클이 발생하는 경우 위상 정렬을 수행할 수 없다. Why? 위상 정렬은 시..
[이코테] CHAPTER 09 최단 경로 알고리즘 - 다익스트라 최단 경로 알고리즘
[이코테] CHAPTER 09 최단 경로 알고리즘 - 다익스트라 최단 경로 알고리즘
2022.05.23최단 경로 알고리즘(Shortest Path) : 가장 짧은 경로를 찾는 알고리즘 1) 최단 경로 문제- 지점( 노드 ), 지점 간 연결된 도로( 간선 ) - 한 지점에서 다른 한 지점까지의 최단 경로를 구해야 하는 경우 - 한 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 2) 최단 경로 알고리즘 종류 - 다익스트라 최단 경로 알고리즘 , 플로이드 워셜 1. 다익스트라(Dijkstra) 최단 경로 알고리즘 : 특정한 한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 - 음의 간선(0보다 작은 값을 가지는 간선)이 없을 때 정상적으로 동작 -> GPS 소프트웨어(길찾기)의 기본 알고리즘 채..
[이코테] CHAPTER 05 DFS/BFS - BFS(deque 메서드) - Python(파이썬),Java(자바)
[이코테] CHAPTER 05 DFS/BFS - BFS(deque 메서드) - Python(파이썬),Java(자바)
2022.05.18DFS 설명 스택, 큐, 재귀함수, DFS 탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘으로 DFS, BFS , 이 두 알고리즘을 이해하기 위해서 스택, 큐, 재귀 함수를 알아야한다. 참고자료. https: coooco.tistory.com https://www.youtube.com/watch?v=7C9RgOcvkvo BFS : 너비 우선 탐색 가까운 노드부터 탐색하는 알고리즘 DFS: 최대한 멀리 있는 노드를 우선으로 탐색하는 방식 - 큐 자료구조 사용 하는 것이 정석 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드 중에서 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. ( B..
[이코테]CHAPTER 05 DFS/BFS - 스택, 큐, 재귀함수, DFS
[이코테]CHAPTER 05 DFS/BFS - 스택, 큐, 재귀함수, DFS
2022.05.17탐색(Search) : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘으로 DFS, BFS , 이 두 알고리즘을 이해하기 위해서 스택, 큐, 재귀 함수를 알아야한다. 참고자료. https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html 스택(Stack)= 박스 쌓기 : 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 또는 LILO(Last In Last Out) 구조 스택 메서드( java 라이브러리) * push(E item) : 해당 item을 Stack의 top에 삽입 * pop( ): Stack의 top에 있는 item을 삭제하고 해당 Item을 반환 * peek( ): Sta..
[이코테] CHAPTER 06 정렬 - 계수 정렬
[이코테] CHAPTER 06 정렬 - 계수 정렬
2022.05.16계수 정렬 (Count Sort) : 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 알고리즘( 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.) 별도의 리스트를 선언하고 그 안에 정보를 담는다. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완성된다. ex) 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 1 0 0 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 0 1 2 3 4 5 6 7 8 9 0 0 0 0 0 1 0 1 0 0 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2 0 1 2 3 4 5 ..
[이코테]CHAPTER 06 정렬 - 퀵정렬- 파이썬(Python)
[이코테]CHAPTER 06 정렬 - 퀵정렬- 파이썬(Python)
2022.05.151) 퀵 정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸기. 피벗(Pivot)(교환하기 위한 기준) 사용 - 호어 분할 방식(Hoare Partition) 1. 리스트에서 첫번째 데이터를 피벗 설정 2. 리스트 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서는 피벗보다 작은 데이터를 찾기 3. 큰 데이터와 작은 데이터 교환 1. '5'보다 큰 데이터를 선택하므로 왼쪽에서부터 '5'보다 큰 '7' 오른쪽에서부터 '5'보다 작은 '4' 둘이 변경 2. '5'보다 큰 데이터를 선택하므로 왼쪽에서부터 '9' 선택 오른쪽에서부터 '2' 둘이 변경 3. '5'보다 큰 데이터를 선택하므로 왼쪽에서부터 '6' 선택, 오른쪽에서부터 '1' 선택하였는데 이렇게 두 값이 엇갈린 경우 ..
[이코테] CHAPTER 07 이진탐색- 순차 탐색, 이분탐색/이진탐색, 이진탐색트리
[이코테] CHAPTER 07 이진탐색- 순차 탐색, 이분탐색/이진탐색, 이진탐색트리
2022.05.131. 순차 탐색( Sequential Search ) : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 주로, 정렬되지 않는 리스트에서 데이터를 하나씩 차례대로 확인하는 방법 - 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점 - 리스트에 특정 원소가 있는 지 체크할 경우, 리스트에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드 이용할 경우 import sys #순차 탐색 def sequentail_search(n,target,array): # n : 들어오는 숫자의 개수 # target: 현재 비교하고 싶은 원소 # array: 비교하고 싶은 list #하나씩 원소를 확인 for ..
[이코테] CHAPTER 03 그리디(Greedy)
[이코테] CHAPTER 03 그리디(Greedy)
2022.05.11그리디(Greedy) 알고리즘 탐욕적으로 문제를 푸는 알고리즘( 현재 상황에서 지금 당장 좋은 것만 고르는 방법) 기준에 따라 좋을 것을 선택하는 알고리즘이므로 문제에서 "가장 큰 순서대로","가장 작은 순서대로"와 같은 기준을 제시 -> 이 기준들은 정렬 알고리즘을 사용하였을 경우 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝 지어 출제 대표적인 예제 : 거스름돈 가정 ) 거스름돈으로 사용할 돈은 500,100,50,10원짜리 동전이 무한히 존재 손님에게 거슬러 줘야할 돈 N원일 때 거슬러 줘야 할 동전의 최소 개수 구하기 ( 단, 거슬러 줘야할 돈 N원은 항상 10의 배수 ) 문제 해설 ) 가장 큰 화폐 단위부터 돈을 거슬러 준다. -> 이때, 정렬 알고리즘을 활용하여 사용한다..
[이코테] CHAPTER 06 정렬- 선택정렬,삽입정렬- 파이썬(Python), 자바(Java)
[이코테] CHAPTER 06 정렬- 선택정렬,삽입정렬- 파이썬(Python), 자바(Java)
2022.04.26정렬 : 데이터를 특정한 기준에 다라서 순서대로 나열 하는 것 1) 선택정렬(selection sort) : 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정 반복 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복 ex ) 파이썬(Python) #파이썬- 선택 정렬 array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index=i #가장 작은 원소의 인덱스 for j in range(i+1,len(array)): if array[min_inde..