분류 전체보기
-
[이코테 # Greedy3] 숫자 카드 게임Programming 기초/Coding Test 2023. 6. 5. 16:24
* 숫자 카드 게임 '각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수'를 찾는 것이 핵심. # 행(n)과 열(m) 개수 입력받기 n, m = map(int, input().split()) # 카드 더미 만들기 d = [] min = [] for i in range(n): d.append([]) min.append(99) d[i] = list(map(int, input().split())) # 게임 룰 적용 # 1 각 행 별로 min 값을 비교해야함 # 0번 인덱스는 1번째 행의 최솟값 for i in range(n): for j in range(m): if min[i] >= d[i][j]: min[i] = d[i][j] MAX = 0 for i in range(n): if min[i] >..
-
[CodeUp#review] 기초 100제Programming 기초/Coding Test 2023. 6. 4. 15:55
100제 중 기록해둘 몇 개 문항만 다룬다. * 짝수 합 구하기(6077번) 정수(1 ~ 100) 1개를 입력받아 1부터 그 수까지 짝수의 합을 구해보자. [ 입력 ] 정수 1개가 입력된다. (0 ~ 100) [출력] 1부터 그 수까지 짝수만 합해 출력한다. # 더 빠른 풀이, but 가독성이 떨어짐 k = int(input()) print((k >> 1) * ((k >> 1) + 1)) # 가독성을 조금 더 높인 풀이 # 등차수열의 합공식n*(n+1)/2을 이용함. # 모두 짝수이므로 2를 인수로 가지고 있다. k = int(input()) n = k//2 sum = n*(n+1) print(sum) 시간복잡도 : O(1) # 제공 풀이 n = int(input()) sum=0 for i in rang..
-
[이코테 # Greedy2] 큰 수의 법칙, sort함수, 함수 매개변수의 콜론(:)과 화살표(->)의 의미Programming 기초/Coding Test 2023. 6. 4. 00:14
# 배열의 크기 n, 숫자가 더해지는 횟수 m, 연속 인덱스 k번 제한 # original 답변 n, m, k = map(int, input().split()) data = list(map(int, input().split())) data.sort() max1 = data[4] max2 = data[3] mul1 = m // (k + 1) mul2 = m % (k + 1) sum = k * max1 * mul1 + max2 * mul1 + max1 * mul2 print(sum) * sort 함수 def sort(self: list[SupportsRichComparisonT], *, key: None = None, reverse: bool = False) -> None: ... 위 코드는 sort 함수 ..
-
[이코테 # Greedy1] 거스름돈 문제 풀이Programming 기초/Coding Test 2023. 6. 2. 17:13
* Greedy Algorism " 현재 상황에서 지금 당장 좋은 것만 고르는 방법" * 거스름돈 문제 카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리의 동전이 무한히 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수.(단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.) # 해설 보기 전 original 본인 답변 # 500원= Five_H, 100원= One_H, 50원 = Fifty , 10원 = Ten # 손님에게 거슬러줘야 할 돈 N = change # 상품 가격 : ProductPrice = 1350원 ProductPrice = 740 print("상품 가격 : %d" % ProductPrice) payment = int(input("..
-
[Python 자료구조 #고급정렬3] 기수 정렬(radix sort), 카운팅 정렬(counting sort), 팀 정렬(Timsort)Programming 기초/Python 2023. 6. 2. 02:35
* 기수 정렬(radix sort) 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 색다른 정렬 기법이다. 다른 방법들이 O(nlog_2 n)이라는 비교기반 정렬의 이론적인 하한선을 깰 수 없는데 비해 기수 정렬은 이 하한선을 깰 수 있다. 기수 정렬은 O(kn)의 시간 복잡도를 갖고 k에 비례한다. 대부분 k는 크지 않은 값(예: k
-
[Python 자료구조 #고급정렬2] 병합정렬(merge sort), 퀵 정렬(quick sort), 이중피벗 퀵 정렬(dual pivot quick sort)Programming 기초/Python 2023. 6. 1. 23:31
* 병합 정렬(merge sort) 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법이다. 하나의 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략인 분할 정복(divide and conquer) 기법에 바탕을 두고 있다. 추가적인 메모리가 필요하다는 단점이 있다. 병합단계에서 n번의 비교 연산이 필요하고, 병합 단계가 log_2 n번 필요하므로 비교 연산은 최대 O(n log_2 n)번 필요하다. 최악, 평균, 최선의 경우에도 모두 동일한 O(nlog_2 n)시간 복잡도를 갖는다. ▶ 병합 정렬의 주요 처리 과정 분할(Divide) : 입력 배열을 같은 크기의 2개의..
-
[Python 자료구조 #고급정렬1] 셸 정렬(shell sort), 힙 정렬(heap sort)Programming 기초/Python 2023. 6. 1. 00:09
* 다양한 정렬 알고리즘 선택 정렬 : 입력의 크기에 따라 자료 이동 횟수가 결정된다. 삽입 정렬 : 레코드의 많은 이동이 필요하지만 대부분의 레코드가 이미 정렬되어 있는 경우에는 비효율적이다. 버블 정렬 : 인접 요소를 교환하는 방식의 가장 간단한 알고리즘을 사용한다. 셸 정렬 : 삽입 정렬 개념을 개선한 방법 힙 정렬 : 추가적인 메모리 공간이 필요 없는 제자리 정렬로 구현하는 방법 병합 정렬 : 연속적인 분할과 병합을 이용하는 방법 퀵 정렬, 이중피벗 퀵 정렬 : 피벗을 이용한 정렬 방법으로 대표적인 효율적인 정렬 알고리즘 기수 정렬, 카운팅 정렬 : 항목의 비교를 사용하지 않고 분배를 이용해 정렬하는 방법이지만 적용할 수 있는 킷값에 제한이 있는 알고리즘 * 셸 정렬(shell sort) Dona..
-
[Python 자료구조 #가중치 그래프3] 최단 경로 알고리즘 - Dijkstra, FloydProgramming 기초/Python 2023. 5. 30. 23:09
* 최단 경로(shortest path) 최단 경로 문제는 가중치 그래프에서 두 정점을 연결하는 여러 경로들 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다. 간선의 가중치를 시간으로 하면 "최단시간 경로", 거리로 하면 "최단거리 경로"가 된다. 인접 행렬에서 두 정점 사이의 간선이 없으면 None이 아니라 무한대 값(INF)을 저장한다. 간선의 가중치는 반드시 양수이다. * Dijkstra의 최단 경로 알고리즘 하나의 시작 정점 v에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 만약 그래프의 모든 정점들 사이의 최단 경로를 구하려고 한다면 Dijkstra 알고리즘을 정점의 수만큼 반복하여 실행하면 된다. 하나의 정점에서 출발하여 모든 정점까지의 최단 경로를 찾는데 O(n^2)..