본문 바로가기

Algorithm44

Pancake Sorting n = [56,324,23,24,54,83,34] def filp(array, count=0): #배열의 길이 l = len(array) #배열의 길이와 count의 횟수가 같아진다면, 종료 if count == l: return array #배열의 0~(l-count)까지의 최대값 maxi = max(array[:l-count]) #최대값의 배열에서의 위치. index = array.index(maxi) #찾은 maxi를 배열의 첫번째로 위치하게 하고, array = array[0:index+1][::-1] + array[index+1:] #그리고 찾은 maxi가 l-count의 위치로 전체 배열을 역전한다. array = list(reversed(array[0:l-count])) + array[l-c.. 2024. 3. 30.

배열의 원소의 총합 계산하기 n = [13,6,9,8,12] def total(array, sum=0): #array의 비교할 것이 남아있지 않다면, if not array: #sum을 넘기면서 프로그램을 종료한다. return sum #sum에 첫번째 원소를 더한다. sum += array[0] #이미 더한 원소를 빼기위해서 0번째 원소를 뺀 배열과 더해져있는 sum을 리턴한다. return total(array[1:], sum) print(total(n))해당 함수의 시간복잡도는 배열의 길이의 비례만큼 실행되기 때문에 시간복잡도는 $O(n)$이다. n = [13,6,9,8,12] def min(array, com): #array의 비교할 것이 남아있지 않다면, if not array: #com을 넘기면서 프로그램을 종료한다. r.. 2024. 3. 30.

알고리즘 가이드 도움이 될 링크들 백준 온라인 저지 - https://www.acmicpc.net 백준 온라인 저지 슬랙 - https://www.acmicpc.net/slack 백준 문제 난이도 보여주는 서비스 - https://solved.ac 알고리즘 랭겜 코드포스 - https://codeforces.com (그린 민트 블루 퍼플 오렌지 레드 누텔라 등은 코드포스 레이팅을 의미합니다) 라이님의 알고리즘 강좌 - https://kks227.blog.me/220769859177 BaaaaaaaarkingDog님의 강좌 - https://blog.encrypted.gg/category/강좌 Lawali님의 강좌 - https://blog.naver.com/PostList.nhn?blogId=ingu9981&catego.. 2023. 8. 7.

배열에서 최솟값 찾기 n = [13,6,9,8,12] def min(array, com): # array의 비교할 것이 남아있지 않다면, if not array: # com을 넘기면서 프로그램을 종료한다. return com # 배열의 첫번째를 now로 선언. now = array[0] # now가 com보다 작다면, if now < com: # 배열의 첫번째수가 비교하는 수보다 작으면, now를 com로 대체한다. return min(array[1:], now) # now가 com보다 작지 않다면, else: # 배열의 첫번째가 비교하는 수보다 작지 않다면, com을 유지한다. return min(array[1:], com) print(min(n, n[0])) 해당 함수의 시간복잡도는 배열의 길이의 비례만큼 실행되기 때문에.. 2023. 8. 7.

Chapter 12. 백트래킹 백트래킹 (핵심 유형 문제풀이) 혼자 힘으로 풀어 보기 N-Queen: https://www.acmicpc.net/problem/9663 문제 제목: N-Queen 문제 난이도: 중(Medium) 문제 유형: 백트래킹 추천 풀이 시간: 40분 문제 풀이 핵심 아이디어 N x N 크기의 체스 보드 위에 퀸(Queen) N개를 서로 공격할 수 없게 배치시켜야 합니다. 대표적인 백트래킹(Backtracking) 문제입니다. N = 4일 때는, 다음과 같은 경우가 존재합니다. DFS를 이용하여 간단히 백트래킹 알고리즘을 구현할 수 있습니다. 각 행을 차례대로 확인하면서, 각 열에 퀸(Queen)을 놓는 경우를 고려합니다. 각 행을 차례대로 확인하면서, 각 열에 퀸(Queen)을 놓는 경우를 고려합니다. 이 때 .. 2020. 8. 10.

Chapter 11. 탐욕 알고리즘 탐욕 알고리즘 (기초 문제풀이) 혼자 힘으로 풀어 보기 거스름돈: https://www.acmicpc.net/problem/5585 문제 제목 : 거스름돈 문제 난이도: 하(Easy) 문제 유형: 그리디 추천 풀이 시간: 10분 문제 풀이 핵심 아이디어 거스름돈의 최소 개수를 계산해야 합니다. 가장 기초적인 탐욕 알고리즘 문제 유형입니다. 단순히 '큰 화폐 단위' 순서대로 잔돈을 거슬러 주면 최적의 해를 얻을 수 있습니다. '큰 화폐 단위' 순서대로 잔돈을 거슬러 줍니다. 거슬러 줄 돈: 620 거스름 돈의 개수: 0 거슬러 줄 돈: 120 거스름 돈의 개수: 1 거슬러 줄 돈: 20 거스름 돈의 개수: 2 거슬러 줄 돈: 20 거스름 돈의 개수: 2 거슬러 줄 돈: 0 거스.. 2020. 8. 10.

Chapter 10. 그래프 고급 탐색 알고리즘 그래프 고급 탐색 알고리즘 (핵심 유형 문제풀이) 혼자 힘으로 풀어 보기 해킹: https://www.acmicpc.net/problem/10282 문제 제목: 해킹 문제 난이도: 중(Medium) 문제 유형: 다익스트라 최단 경로 추천 풀이 시간: 50분 문제 풀이 핵심 아이디어 기본적인 다익스트라 최단 경로 알고리즘 문제입니다. 도달할 수 있는 정점들의 개수와 최대 거리를 출력합니다. 정점의 개수 N이 최대 10,000이고, 간선의 개수 D는 최대 100,000입니다. 우선 순위 큐를 이용하여, 시간 복잡도 O(NlogD)로 해결할 수 있습니다. 정점개수 = 3, 간선 개수 = 3, 시작 정점 번호 = 1 소스코드 import heapq import sys input = sys.stdin.readli.. 2020. 8. 10.

Chapter 09. 그래프 기본 탐색 알고리즘 그래프 기본 탐색 알고리즘 (기초 문제풀이) 혼자 힘으로 풀어 보기 DFS와 BFS: https://www.acmicpc.net/problem/1260 문제 제목: DFS와 BFS 문제 난이도: 하(Easy) 문제 유형: DFS, BFS 추천 풀이 시간: 30분 문제 풀이 핵심 아이디어 기본적인 형태의 그래프를 단순히 DFS와 BFS로 탐색합니다. 이 문제에서는 "정점 번호가 작은 것"을 먼저 방문해야 합니다. 모든 노드와 간선을 차례대로 조회하여 O(N+M)의 시간 복잡도로 문제를 해결해야 합니다. 국내 코딩 테스트 합격을 위해서는 이 문제를 매우 빠르게 풀 수 있도록 숙달할 필요가 있습니다. 큐(Queue) 구현을 위해 collections 라이브러리의 deque를 사용합니다. 예시) 정점 개수 = .. 2020. 8. 10.

Chapter 08. 동적 프로그래밍 동적 프로그래밍 (기초 문제 풀이) 혼자 힘으로 풀어 보기 01타일: https://www.acmicpc.net/problem/1904 문제 제목: 01타일 문제 난이도: 하(Easy) 문제 유형: 동적 프로그래밍 추천 풀이 시간: 20분 문제 풀이 핵심 아이디어 사용할 수 있는 타일의 종류는 2개입니다. 두 가지 종류의 타일을 이용하여, N 길이의 수열을 만드는 모든 경우의 수를 구해야 합니다. 가장 전형적인 동적 프로그래밍 문제입니다. N이 최대 1,000,000이므로 시간 복잡도 O(N)으로 해결해야 합니다. 타일을 왼쪽에서부터 오른쪽으로 이어서 붙인다고 가정합니다. 예를 들어 N = 3일때, 경우의 수는 3가지입니다. 예를 들어 N=4일 때, 경우의 수는 5가지 입니다. 동적 프로그래밍 문제를 풀.. 2020. 8. 10.

Chapter 07. 고급 탐색 알고리즘 고급 탐색 알고리즘 (기초 문제 풀이) 혼자 힘으로 풀어 보기 트리 순회: https://www.acmicpc.net/problem/1991 문제 제목: 트리 순회 문제 난이도: 하(Easy) 문제 유형: 트리, 구현 추천 풀이 시간: 20분 문제 풀이 핵심 아이디어 전위 순회: 루트 -> 왼쪽자식 -> 오른쪽 자식 중위 순회: 왼쪽 자식 -> 루트 -> 오른쪽 자식 후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 루트 소스 코드 class Node: def __init__(self, data, left_node, right_node): self.data = data self.left_node = left_node self.right_node = right_node def pre_order(node): p.. 2020. 8. 10.

Chapter 06. 기본 탐색 알고리즘 기본 탐색 알고리즘 (기초 문제 풀이) 혼자 힘으로 풀어보기 문서 검색: https://www.acmicpc.net/problem/1543 문제 제목: 문서 검색 문제 난이도: 하(Easy) 문제 유형: 탐색 추천 풀이 시간: 20분 문제 풀이 핵심 아이디어 문서의 길이는 최대 2,500이고 단어의 길이는 최대 50입니다. 단순히 모든 경우의 수를 계산하여 문제를 해결할 수 있습니다. 시간 복잡도 O(NM)의 알고리즘으로 해결할 수 있습니다. 문서와 단어의 위치를 맞추어서 반복적으로 비교합니다. 소스 코드 document = input() word = input() index = 0 result = 0 while len(document) - index >= len(word): # 문서에서 보고 있는 단어.. 2020. 8. 10.

Chapter 05. 고급 정렬 알고리즘 Chapter 05. 고급 정렬 알고리즘 (핵심 유형 문제풀이) 혼자 힘으로 풀어보기 수 정렬하기2: https://www.acmicpc.net/problem/2751 문제 제목: 수 정렬하기2 문제 난이도: 하(Easy) 문제 유형: 정렬 추천 풀이 시간: 20분 문제 풀이 핵심 아이디어 데이터의 개수가 최대 1,000,000개입니다. 시간복잡도 O(NlogN)의 정렬 알고리즘을 이용해야 합니다. 고급 정렬 알고리즘 (병합 정렬, 퀵 정렬, 힙 정렬등)을 이용하여 문제를 해결할 수 있습니다. 혹은 파이썬의 기본 정렬 라이브러리를 이용하여 문제를 풀 수 있습니다. 메모리가 허용된다면, 되로록 Python 3보다는 PyPy3를 선택하여 코드를 제출합니다. 병합 정렬(Merge Sort) 알고리즘 분할 정복.. 2020. 8. 10.

Chapter 04. 재귀 호출 Chapter 04. 재귀 호출 (핵심 유형 문제풀이) 혼자 힘으로 풀어보기 피보나치 수: https://www.acmicpc.net/problem/2747 문제 제목: 피보나치 수 문제 난이도: 하(Easy) 문제 유형: 재귀 함수 추천 풀이 시간: 15분 문제 풀이 핵심 아이디어 피보나치 수열의 점화식을 세웁니다. 재귀 함수를 이용해 문제를 풀 수 있는지 검토해야 합니다. 문제에서 N은 최대 45입니다. 실패 소스코드 def fibonacci(n): if n == 0: return 0 if n == 1: return 1 return fibonacci(n-1) + fibonacci(n-2) print(fibonacci(int(input()))) 피보나치 수열: 재귀적 구현의 한계 소소코드 n = int.. 2020. 8. 10.

Chapter 03. 기본 정렬 알고리즘 Chapter 03. 기본 정렬 알고리즘 (기초 문제풀이) 혼자 힘으로 풀어보기 수 정렬하기: https://www.acmicpc.net/problem/2750 문제 제목: 수 정렬하기 문제 난이도: 하(Easy) 문제 유형: 정렬 추천 풀이 시간: 15분 문제 풀이 핵심 아이디어 데이터의 개수가 1,000개 이하이므로 기본적인 정렬 알고리즘으로 해결할 수 있습니다. 소스 코드 1) 선택 정렬 알고리즘으로 문제 해결하기 n = int(input()) array = list() for _ in range(n): array.append(int(input())) for i in range(n): min_index = i # 가장 작은 원소의 인덱스 for j in range(i+1, n): if array[m.. 2020. 8. 10.

Chapter 02. 고급 자료구조 고급 자료구조 (핵심 유형 문제풀이) 혼자 힘으로 풀어보기 SHA-256: https://www.acmicpc.net/problem/10930 문제 제목: SHA-256 문제 난이도: 하(Easy) 문제 유형: 해시, 구현 추천 풀이 시간: 15분(검색 시간 포함) 문제 풀이 핵심 아이디어 hashlib의 sha256 함수를 이용하면 SHA 256해시를 구할 수 있습니다. hashlib.sha256(문자열의 바이트 객체).hexdigest(): 해시 결과 문자열 소스 코드 import hashlib input_data = input() encoded_data = input_data.encode() result = hashlib.sha256(encoded_data).hexdigest() print(resu.. 2020. 8. 10.

Chapter 01. 기본 자료구조 Chapter 01. 기본 자료구조(기초 문제풀이) 혼자 힘으로 풀어보기 음계: https://www.acmicpc.net/problem/2920 문제 제목: 음계 문제 난이도: 하(easy) 문제 유형: 배열, 구현 추천 풀이 시간: 15분 문제풀이 핵심 아이디어 리스트에서의 원소를 차례대로 비교합니다. 비교할 때 두 원소를 기준으로 오름차순/내림차순 여부를 체크합니다. [초기상태 오름차순: True, 내림차순: True] [초기상태 오름차순: True, 내림차순: False] [초기상태 오름차순: False, 내림차순: False] 오름차순 및 내림차순이 모두 False이므로 'mixed'를 출력합니다. 소스 코드 a = list(map(int, input().split(' &#.. 2020. 8. 10.

Chapter 21. 백트래킹 백 트래킹 기법의 이해 1. 백 트래킹 (backtracking) 백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현 각 후보군을 DFS 방식으로 확인 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 .. 2020. 7. 22.

Chapter 20-2. 최소 신장트리의 이해 최소 신장 트리의 이해 1. 프림 알고리즘 (Prim's algorithm) 대표적인 최소 신장 트리 알고리즘 Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘) 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 Kruskal's algorithm 과 Prim's algorithm 비교 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) Kruskal's algorithm은 가장 가중치가 작은 간선부터 선.. 2020. 7. 22.

Chapter 20-1. 최소 신장트리의 이해 최소 신장 트리의 이해 1. 신장 트리 란? Spanning Tree, 또는 신장 트리 라고 불리움 (Spanning Tree가 보다 자연스러워 보임) 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴 (사이클이 존재하지 않음) 2. 최소 신장 트리 Minimum Spanning Tree, MST 라고 불리움 가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함 3. 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함 대표적인 최소 신장 트리 알고리즘 Kruskal’s algorithm (크루.. 2020. 7. 22.

Chapter 19. 최단경로 알고리즘 이해 최단 경로 알고리즘의 이해 1. 최단 경로 문제란? 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제임 가중치 그래프 (Weighted Graph) 에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제 단일 출발 (single-source shortest path problem) 최단 경로 문제 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제 따지고 보.. 2020. 7. 22.

이전 1 2 3 다음

728x90

티스토리툴바