한창 백준 문제 풀 때 DP의 개념에 대해 정리한 글이다. 이번 글에서는 추가적으로 알게 된 것들만 정리해보자. https://aodtns.tistory.com/16?category=993972 백준 1003번 - 피보나치 함수 피보나치 함수를 구현하는 문제이다. 하지만 일반적인 재귀함수를 이용하는 방법으로 풀면 시간 초과가 뜰 것이다. 이를 해결하기 위해서 동적 계획법에 대해 알아보자. 동적 계획법 (Dynamic Prog aodtns.tistory.com DP를 사용하기 위한 조건 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 분할 정복(Divide and Conquer)과의 차이점 분할 정복과 비슷한 느낌이지만 DP는 문제들이 ..
이코테
그래프 (Graph) 그래프는 노드(Node 혹은 정점(Vertex))와 간선(Edge)으로 표현된다. 그래프 탐색이란 하나의 정점으로부터 다른 노드들을 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 "두 노드는 인접하다(Adjacent)" 라고 말한다. 인접 행렬 (Adjacency Matrix) 인접 행렬은 2차원 배열로 그래프의 연결 관계를 표현하는 방식이다. 이 때 연결이 되어있지 않은 노드끼리는 무한대의 비용이라고 생각한다. 실제 코드에서는 논리적으로 정답이 될 수 없는 큰 값들을 999999999 등의 값으로 초기화하는 경우가 많다. INF = 999999999 #무한의 비용 선언 # 인접 행렬 구현 grpah = [ [0, 7, 5], [7, 0, INF], [5, INF,..
피지컬로 승부하기 구현(Implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 개발할 때 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도(타자)가 빠른 사람을 보고 '피지컬이 좋다'라고 이야기하는데, 구현 유형의 문제는 그런 의미에서 '피지컬을 요구하는' 문제라고도 할 수 있다. 이 책에서는 모든 경우의 수를 모두 계산하는 해결 방법인 완전 탐색, 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 시뮬레이션 유형을 모두 구현으로 취급하여 다룬다. 구현 시 고려해야 할 메모리 제약 사항 C/C++에서 변수의 표현 범위 기본 int 자료형..
그리디 알고리즘 (탐욕법) 그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는' 알고리즘이다. 이 알고리즘의 유형은 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있지만, 뒤에 나오는 정렬, 최단 경로 등의 알고리즘 유형은 미리 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다. 그러므로 그리디 알고리즘 문제를 풀 때는 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 한다. 보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 즉 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다. 그리디 ..
배열 내부의 데이터가 정렬되어 있을 때 O(logN)의 시간 복잡도로 원하는 값을 찾을 수 있는 이진 탐색에 대해 알아보자. 이진 탐색(Binary Search) 이진 탐색은 배열 내부의 데이터가 정렬되어 있는 경우에만 사용할 수 있는 알고리즘이다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다. 이진 탐색에서는 시작점, 중간점, 끝점으로 3개의 변수를 사용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복해서 비교해서 원하는 데이터를 찾는다는 컨셉이다. 대충 이런 느낌이다. 코드를 살펴보면 이해가 될 것이다. def binary_search(arr, target, start, end): if start > end: return None mid = (start+end)//2 if ar..
문제 동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K 번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 한다. N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하라. 예를 들어 N = 5, K = 3이고, 배열 A와 B가 다음과 같다고 해보자. 배열 A = [1, 2, 5, 4, 3..
문제 N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 학생의 성적으로 구분된다. 각 학생의 이름과 성적 정보가 주어졌을 때 성적이 낮은 순서대로 학생의 이름을 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에 학생의 수 N이 입력된다. (1≤N≤100,000) 두 번째 줄부터 N+1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다. 출력 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다. 입력 예시 2 홍길동 95 이순신 77 출력 예시 이순신 홍길동 문제 해설 N의 크기가 100,000이기 때문에 시간 복잡도가 O(Nlo..
문제 하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰 수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오. 입력 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다. (1≤N≤500) 둘째 줄부터 N + 1번째 줄 까지 N개의 수가 입력된다. 수의 범위는 1 이상 100,000 이하의 자연수이다. 출력 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력한다. 동일한 수의 순서는 자유롭게 출력해도 괜찮다. 입력 예시 3 5 27 12 출력 예시 27 15 12 문제 해설 N의 범위가 500으로 매우 작고, 수의 범위 또한 100,000이하의 자연수이기 때문에 어떤 방식의 정렬 방법을 사용해도 상관없..
