Algorithm/알고리즘
-
[😸코테] 시간복잡도 VS 공간복잡도Algorithm/알고리즘 2022. 7. 25. 18:48
시간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리나? 빅오 표기법 : 가장 빠르게 증가하는 항만을 고려하는 표기법 예제) 5개의 데이터를 받아 차례로 5회 더해준다 -> 연산횟수가 N에 비례함 -> O(N)이라 표기 array = [3, 5, 1, 2, 4] # 5개의 데이터(N=5) summary = 0 # 합계를 저장할 변수 # 모든 데이터를 하나씩 확인하며 합계를 계산 for x in array: summary += x # 결과를 출력 print(summary) 예제) 2중 반복문 -> N*N만큼의 연산 사용 -> O(N^2) array = [3, 5, 1, 2,4] for i in array: for j in array: temp = i*j print(temp) 코딩테스트에서는..
-
🌼알고리즘🌼 그리디 알고리즘Algorithm/알고리즘 2022. 6. 5. 19:13
그리디 알고리즘 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘 문제 유형 : 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준이 나타난다. 이런 기준은 정렬 알고리즘과 함께 짝을 이뤄 출제된다 그리디 알고리즘 예제 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 풀이 idea : 가장 큰 화폐 단위부터 돈을 거슬러 줘야함 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 그 다음 100원, 50원, 10원... 으로 거슬러 준다. n = 1260 count = 0 # 동전의 유형 coin_typ..