~2023.02/알고리즘

[알고리즘] 재귀 호출

재귀 호출의 일반적인 형태 일반적인 형태 1 def function(입력): if 입력 > 일정값: # 입력이 일정 값 이상이면 return function(입력 - 1) # 입력보다 작은 값 else: return 일정값, 입력값 또는 특정값 # 재귀 호출 종료 일반적인 형태 2 def function(입력): if 입력

dp

브론즈 9625번 k = int(input()) a = [0]*46 b = [0]*46 a[1] = 0 b[1] = 1 if k == 1: print(a[1], b[1]) else: for i in range(2, k+1): a[i] = b[i-1] b[i] = a[i-1] + b[i-1] print(a[k], b[k])

[기본 정렬 알고리즘 #4] 참고, 공간복잡도

📌 기본 정렬 알고리즘 - 버블 정렬 - 삽입 정렬 - 선택 정렬 - 참고, 공간복잡도 ✔ 참고: 공간 복잡도 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음 시간 복잡도 : 얼마나 빠르게 실행되는지 공간 복잡도 : 얼마나 많은 저장 공간이 필요한지 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘 통상 둘 다를 만족시키기는 어려움 시간과 공간은 반비례적 경향이 있음 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선 그래서! 알고리즘은 시간 복잡도가 중심 [공간 복잡도 대략적인 계산은 필요함] 기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많음 그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라, 공간 복잡도 제약 사항이 ..

[기본 정렬 알고리즘 #3] 선택 정렬

📌 기본 정렬 알고리즘 - 버블 정렬 - 삽입 정렬 - 선택 정렬 ✔ - 참고, 공간복잡도 1. 선택 정렬 (selection sort) 란? 다음과 같은 순서를 반복하며 정렬하는 알고리즘 1. 주어진 데이터 중, 최소값을 찾음 2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함 https://visualgo.net/en/sorting Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo VisuAlgo is free of charge for Computer Science community on earth. If you like VisuAlgo, the..

[기본 정렬 알고리즘 #2] 삽입 정렬

📌 기본 정렬 알고리즘 - 버블 정렬 - 삽입 정렬 ✔ - 선택 정렬 - 참고, 공간복잡도 1. 삽입 정렬 (insertion sort) 란? 삽입 정렬은 두 번째 인덱스부터 시작 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사 이를 key 값이 더 큰 데이터를 만날때까지 반목, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동 https://visualgo.net/en/sorting Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo VisuAlgo is free of charge for Computer Science community on..

[기본 정렬 알고리즘 #1] 버블 정렬

📌 기본 정렬 알고리즘 - 버블 정렬 ✔ - 삽입 정렬 - 선택 정렬 - 참고, 공간복잡도 1. 정렬 (sorting) 이란? 정렬 : 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 정렬은 프로그램 작성시 빈번하게 필요로 함 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수 다양한 정렬 알고리즘 이해를 통해 동일한 문제에 대해 다양한 알고리즘이 고안될 수 있음을 이해하고, 각 알고리즘간 성능 비교를 통해 알고리즘 성능 분석에 대해서도 이해할 수 있음 2. 버블 정렬 (bubble sort) 란? 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 https://visualgo.net/en/sorting Sorting (Bubble..

최단 경로 알고리즘

1. 최단 경로 문제란? 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 [최단 경로 문제 종류] 1. 단일 출발 및 단일 도착 최단 경로 문제 그래프 내의 특정 노드 u에서 출발, 또다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제 2. 단일 출발 최단 경로 문제 그래프 내의 특정 노드 u와 그래프 내 다른 노드 각각의 가장 짧은 경로를 찾는 문제 3. 전체 쌍 최단 경로 문제 그래프 내의 모든 노드 쌍 (u, v)에 대한 최단 경로를 찾는 문제 2. 최단 경로 알고리즘 - 다익스트라 알고리즘 최단 경로 문제 종류 중, 2번에 해당 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 ..

[탐색 알고리즘 #3] 코딩 테스트 연습문제 풀이

📌 탐색 알고리즘 - 이진 탐색 - 순차 탐색 - 코딩 테스트 연습문제 풀이 ✔ 실전 코딩 테스트 - 탐색 알고리즘 [백준 1920번] https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 시간복잡도 O(n^2) n = 5 n_list = [4, 1, 5, 2, 3] m = 5 m_list = [1, 3, 7, 9, 5] for item in m_list: if item in n_list: print(..

[탐색 알고리즘 #2] 순차 탐색(Sequential Search)

📌 탐색 알고리즘 - 이진 탐색 - 순차 탐색 ✔ - 코딩 테스트 연습문제 풀이 순차 탐색(Sequential Search) 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 from random import * rand_data_list = list() for num in range(10): rand_data_list.append(randint(1, 100)) def sequencial(data_list, search_data): for index in range(len(data_list)): if data_list[index] == search_data: return index return -1 print(r..