초콜릿 파워

공부 근황) 요즘 다이나믹 프로그래밍을 공부하고 있는데, 기본적으로 완전탐색에서부터 구현방법을 생각하되, 어떻게 메모이제이션을 활용해 시간 복잡도를 줄일 수 있을지 고민하는 과정이 필수적이다. 다만 완전 탐색(보통은 재귀함수)을 생각해내는 과정이 나에게는 쉽지 않은 과정이었기 때문에, 백트레킹을 다시 연습하기로 했다. 백준 14888 시간 제한 메모리 제한 2 초 512 MB 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면..

LIS를 lower_bound로 해결하는 가장 효율적인 알고리즘이 있음에도 불구하고, 이 알고리즘을 쓰게 된 이유를 알지 못하는 사람들이 많다. 그저 효율적이라는 이유만으로 이 알고리즘을 사용한다면, 그 배경을 알지 못해 응용도 할 수 없을 뿐더러 사용할 때마다 가슴이 답답함을 느끼게 될 것이다.. (나는 이런 걸 왜 생각하지 못할까.. .) 그래서 이 알고리즘이 등장하게 된 배경에 대해서 설명해보려고 한다. (답답해서 공부했다.) 먼저 동적 프로그래밍으로 알고리즘을 설계하는 방법에 대한 것이다. * 동적 프로그래밍 : 앞으로 푸는 문제에 대해 이전의 데이터를 활용할 수 있다면 cache에 저장하여 사용한다. 푸는 방법: https://ebang.tistory.com/89 동적 프로그래밍을 짜기 위해 수..

최적화 문제 동적 계획법 푸는 방법 1. 모든 답을 만들어 보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다. 2. 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 대해 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾼다. 3. 재귀 호출의 입력에 이전에 선택에 관련된 정보가 있다면 꼭 필요한 정보만 남기고 줄인다. 문제에 최적 부분 구조가 성립할 경우에는 이전 선택에 관련된 정보를 완전히 없앨 수도 있다. (* 최적 부분 구조: 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 구할 수 있는 경우, 이 구조에 해당한다고 할 수 있다.) -> 이 부분에서의 목표는 가능한 한 중복되는 부분 문제를 많이 만드는 것이다. 입력의 종류가 줄어들면 줄어들 수록 더 많은 ..

문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. ..

교환 시간 제한 메모리 제한 2 초 128 MB 문제 0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다. 1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다. 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. 출력 첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다. 1. 문제 해석 - ..

c++ 자료형의 프로모션 사칙연산이나 대소 비교 등의 이항 연산자들은 두개의 피연산자를 받는다. 만약 피연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 컴파일러들은 이들을 같은 자료형으로 변환해서 계산하고 이를 프로모션이라고 한다. c++에서 적용되는 규칙은 다음과 같다. 한쪽은 정수형이고 한쪽은 실수형일 경우: 정수형이 실수형으로 변환된다. 양쪽 다 정수형이거나 양쪽다 실수형인 경우: 넓은 범위를 갖는 자료형으로 변환된다. 양쪽 다 int형보다 작은 정수형인 경우: 양쪽 다 int형으로 반환된다. 부호 없는 정수형과 부호 있는 정수형이 섞여 있을 경우 : 부호 없는 정수형으로 변환된다. 연산 될 때 원하지 않는 값이 나오지 않는다면, 조심하도록 하자!

문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경..

최단경로를 다익스트라로 풀고 있을 때, 그 경로도 구해야 하는 경우가 있다. (백준 #5719 거의 최단경로 문제, k번째 최단경로 등) 이럴 때는 어떻게 경로를 저장할 수 있는지 알아보았다. 다익스트라의 진행과정은 다음과 같다. 1. distance[S] 3, 0->4 로 갈 때 모두 갱신이 되고, 모든 경로가 최단경로로써 저장이 될 것이다. - 나중에 최단경로가 아님을 알고 지울 방법이 있는가? -> 알수가 없다. - 나중에 최단경로였음을 알고 되돌아 갈 수 있는 방법은? -> 직전노드를 저장해준다면? -> 갱신될 때마다 방문된 각 노드마다 직전노드를 저장한다면, 마지막에 종료되었을 때의 노드를 기준으로 직전노드로 되돌아가면(일명 벡트래킹) 그것이 최단경로일 것이다! 이러한 사고흐름을 통해, 최단경로..

시간 제한메모리 1 초 128 MB 문제 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다. 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 ..

1. 크루스칼 알고리즘 최소 신장 트리를 구하는 알고리즘 중 하나이다. 1. 유니온 파인드 연산을 필요로 한다. 유니온 파인드 보러가기 >> 2.트리 그래프 : 순환을 갖지 않는 연결 그래프. 임의의 두 정점에 대해서 경로가 정확히 1개 존재함. 하나 이상의 정점을 가지며 임의의 간선 e를 제거한 그래프는 연결 그래프가 아니다. (연결 그래프: 모든 정점들을 간선을 통해방문할 수 있는 그래프 : 임의의 v, u 정점에 대해 path(v,u)가 존재하는 그래프) - 느낌: 그래프를 최소한의 간선으로 모두 연결해서 이동가능 할 수 있게 만든 것이되 사이클이 없는 것. - 특징: 전체 노드의 개수가 N개일때, 트리를 만들고 나면 전체 간선의 수는 N-1개가 된다. (1개의 경로로만 이루어져 있기 때문에) 3...