토리의 데굴데굴 공부일기

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 처음 생각한 풀이 queue를 돌려서 넘어가서 popleft하기.. import sys n,k = map(int, sys.stdin.readline().split()) from collections import deque queue = deque() for i in range(1,n+1): queue.append(i) list = [] while len(queue) > 0: for i in range(2): queue.append(queue.popleft()) list.append..

책 내용을 바탕으로 작성된 글입니다. 정렬 알고리즘: 연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘 기준에 따라 데이터를 정렬 정렬 알고리즘 개요 정렬: 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 ex) 오름차순, 내림차순 선택 정렬 : 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두번째와 바꾸는 과정 반복 → ‘매번 가장 작은 것을 선택’ 데이터의 개수가 N개일 경우 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료됨 #6-1.py 선택 정렬 소스코드 array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_inde..

책 내용을 바탕으로 작성된 글입니다. DFS(Deep First Search) 깊이 우선 탐색 알고리즘 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 ** 먼저 그래프(Graph)의 기본 구조를 알아야 함! 그래프(Graph) 간선, 노드로 구성됨 동작 방식 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. ** ‘방문 처리’는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문 처리를 함으로써 각 노드를 한번씩만 처리할 수 있다. BFS(..

https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net 문제 설명: 요리시간 T(초)가 정수로 주어질때 버튼 각각 5분, 1분, 10초로 설정된 A,B,C 버튼을 최소로 누르는 횟수를 출력하는 문제이다. 사실 처음에는 무작정 문제를 푸려고 while문과 if문을 남발(..)하여 풀긴 했다. #10162 전자레인지 T = int(input()) #버튼 A,B,C는 각각 5분, 1분, 10초 = 300초, 60초, 10초 a_count = 0 b..

문제 출처 : www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 설명: ATM에 줄을 서 있는 모든 사람이 업무를 마치는 순간까지 걸리는 시간이 최소가 되게 하는 문제이다. 문제 풀이: 앞의 대기 시간이 줄어들면 뒤의 사람의 대기시간이 줄어드는 것이 보장되기 때문에 항상 적은 숫자가 앞으로 가야 최적해를 찾을 수 있다. 아이디어 1. sort 함수를 사용하여 오름차순 정렬한다 2. 예시를 보고 규칙을 찾아 숫자가 N-(인덱스값)만큼 반복되어 더해진다는 걸 찾았다 코드 #11399 AT..

책 내용을 바탕으로 작성된 글입니다. 그리디 알고리즘이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 100% 최적해를 보장해주지 않는다. 때문에 그리디 알고리즘은 최적해를 구하는 데 근사하는 방법이기도 하다. 탐욕적 알고리즘 문제를 해결하는 방법 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다. 탐욕..