본문 바로가기
반응형

Algorithm44

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.
728x90
반응형

티스토리툴바