[실습] 숫자 카드 게임 문제 설명 N * M 의 카드가 있다. 뽑고자 하는 카드가 포함된 행을 선택한다. 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑는다. 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 게임이론에서 본 최소 극대 전략이다. 각 행마다 가장 작은 수를 찾은 뒤 그 중에서 가장 큰 수를 찾으면 되겠다. N,M = map(int,input().split()) mylist = [[] for _ in range(N)] minmax = 0 for i in range(N): mylist[i] = list(map(int,input().split())) if minmax < min(mylist[i]): minmax = min(mylist[i]) print(min..
이코테
참고한 책 ; 나동빈 (2020). . 서울시: 한빛미디어. [그리디 알고리즘] 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 다시 말해서, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 정렬, 최단 경로, 폴로이드 워셜, 다익스트라 알고리즘 처럼 특정 알고리즘을 미리 외우고 있어야문제를 풀 수 있는 유형과 달리 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형' 이라는 특징이 있다고 한다. (참고로 다익스트라 알고리즘은 엄밀히 말해 그리디로 분류된다고 하니 특이 케이스라 알아두자.) 그리디 알고리즘 유형의 문제는 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다고 한다. " 단순히 현재 상황에서 가장 좋아 보이는 것만 선..
[삽입 정렬] 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다. 버블 정렬은 큰숫자를 뒤로 밀어내며 정렬하는 반면, 삽입 정렬은 정렬이 이미 되어있는 앞부분과 나 자신을 비교해서, 나 자신이 어디에 삽입되면 되는지를 찾는다. 데이터가 거의 정렬되어있다면 매우 효율적인 알고리즘이다. 정렬되어 있는 배열과 비교할 때도, 자기보다 작은 데이터를 만나면 그 위치에서 멈추면 되므로 모든 데이터를 다 볼 필요가 없다. 시간 복잡도는 \( O(N^2) \) 이며, 최선의 경우 \( O(N) \) 을 갖는다. 빨간 박스는 이미 정렬되어 있는 부분을 말한다. 1. 처음에는 자료에서 두 번째 요소를 가지고 이전 데이터와 비교를 시작하며 빨간색 박스를 찾는다. 2. 정렬되어있지 않은 값을 하나하나 정렬된 배열(빨간..
