본문 바로가기

Algorithm5

[로직] 리스트 내 가장 큰 차이 구하기 배열 내에서 두 값의 차가 가장 큰 값을 찾는 로직 - tmp : 가장 최소인 값을 찾음 - answer : 차이가 최대인 것을 찾음 파이썬 내장함수인 min, max를 활용하여 배열을 하나씩 탐색하여 리스트 내 가장 차이가 큰 두 값의 차를 구한다. def solution(prices): INF = 1000000001; tmp = INF answer = -INF for price in prices: if tmp != INF: answer = max(answer, price - tmp) tmp = min(tmp, price) return answer prices1 = [1, 2, 3]; ret1 = solution(prices1); print("solution 함수의 반환 값은", ret1, "입니다.".. 2022. 11. 13.
[ 다익스트라 알고리즘] Dijkstra 기본 최단경로 문제 1) 단일 시작점 최단 경로 문제 : 출발점에서 다른 모든 정점들에 이르는 최단 경로를 구하는 문제 - 다익스트라 알고리즘 음의 가중치 허용하지 X, - 델만포드 알고리즘 음의 가중치 허용, 가중치 합이 음인 사이클은 허용하지 않음 2) 모든 쌍 최단 경로 문제 : 모든 정점 쌍 간의 최단 경로를 구하는 것, 플로이드-워샬 알고리즘(동적 계획법) 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.. 2022. 3. 21.
[파이썬 힙] Heapq 사용법 heapq heap은 최대값이나 최소값을 뽑아내기에 최적화된 자료구조이다. 파이썬에서는 heap 구현할때, heapq라는 내장라이브러리를 사용한다. import heapq heapq.heappush(heap, 4) heapq.heappush(heap, 1) heapq.heappush(heap, 7) heapq.heappush(heap, 3) print(heap) #[1, 3, 7, 4] 출력했을때는 순서가 뒤죽박죽 섞인것처럼 보이지만. print(heapq.heappop(heap)) # 1 print(heap) # [3, 4, 7] heapq.heappop이라는 함수로 최소값을빼낼수있다. heapq.heapify라는 함수로 기존 리스트를 힙으로 변환하는것도 가능하다. heap = [4, 1, 7, 3, .. 2022. 3. 21.
[파이썬] 재귀함수, StackOverFlow 발생 이유 코딩테스트를 준비하던 중 재귀를 사용하다 한번 쯤을 볼 수 있었던 StackOverFlow... 사실 재귀함수는 알고리즘 테스트를 위해 사용하는 것이지 실전에선 사용하기 힘들다. (사용자들이 어떤 이벤트를 발생할지... 예상하기 힘들기 때문, 또는 종료조건의 기준이 이상해짐) StackOverFlow의 이유를 파악하기 위해선 메모리 구조를 꼭 살펴봐야한다. 메모리 구조 코드(Code) 영역 실행할 프로그램의 코드가 저장되는 영역이다. 프로그램이 시작하고 끝날 때까지 메모리에 계속 남아 있는다. 컴파일된 기계어가 들어가게 된다. CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리한다. 데이터(Data) 영역 프로그램의 전역 변수와 정적 변수, 문자열 상수가 저장되는 영역이다. 프로그램이 시작하고 끝.. 2022. 2. 13.
[코테 기본 암기] Python 소수 구하기 from math import sqrt def is_prime_num(n): for i in range(2, int(sqrt(n))+1): if n % i == 0: return False return True print(is_prime_num(13)) print(is_prime_num(7)) print(is_prime_num(112)) 2021. 10. 25.

티스토리툴바