반응형 Algorithm/유형별 문제 풀이12 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. 이전 1 2 다음 728x90 반응형
