https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당신 www.acmicpc.net 1. Logic 기본적인 이분탐색 문제이다. 0에 가깝다는 것을 판단하는 것은 절댓값을 통해 가장 작은 값을 찾으면 된다. 2. Code #include using namespace std; int n; vector input; int ans = 0x3f3f3f3f; void solve() { int start = 0; int end = n - 1; while(star..
Algorithm
https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄 www.acmicpc.net 1. Logic 처음에 이 문제를 보고 0~L까지 거리를 구한 값을 우선순위 큐에 넣은 다음 큰 숫자부터 2로 나눠서 m만큼 반복하면 쉽게 풀릴 것 같다고 생각했다. 하지만 여기에는 반례가 있었다. 만약 테스트 케이스가 0 2 100 다음과 같이 주어졌을때를 가정해 보면 먼저 답은 33이 나와야한다. 우선순위 큐에는 0~100까지 100이 들어가있을 것이다. 우선순위 큐로 항상 2로 ..
https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 1. Logic 이 문제를 접근할 때 처음에는 이분탐색이 아닌 투포인터로 접근하려고 했었다. 입력이 1000개이기 때문에 시간복잡도를 맞춰야 했고 N^3으로는 풀지 시간내에 계산을 못한다. 적어도 N^2logN정도를 맞춰야 했다. 이분탐색으로 가능했는데 이분탐색에 대한 로직은 1. 입력 받은 수를 토대로 3개의 수 중 2개의 수를 합쳐놓은 sum 배..
https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net 1. Logic 스탠다드한 이분탐색 문제이다. 중앙값을 구한 뒤 입력 받은 사탕들 중에서 나눗셈연산자로 사탕의 갯수를 구해주면 된다. 2. Code #include using namespace std; int nephew, cookie; vector input; bool check(int val) { int re..
https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 1. Logic 이 문제는 투포인터를 사용하여 풀 수 있다. 문제를 푸는 로직은 1. start, end를 0으로 초기화 한다. 2. input 받은 값을 순회하며 중복이 없을 때 까지 map에 입력한다. 3. 중복이 있는 문자가 나오면 멈추고 수열의 갯수인 end-start-1개를 더해준다. 4. 과정을 반복하며 입력받은 수의 끝까지 반복해준다. 2. Code #include using namespac..
https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 1. Logic 조건대로 계산해보면 피보나치 수열과 같다는 것을 알 수 있다. 그대로 Topdown 방식으로 구현해줬다. 2. Code #include using namespace std; long long dp[91]; long long solve(int n) { if(n == 1 or n == 2) return 1; long long &ret = dp[n]; if(ret != 0) ..
https://school.programmers.co.kr/learn/courses/30/lessons/12987 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. Logic 무조건 한번은 경기를 해야하기 때문에 안할 수는 없고 순서를 바꿔줄 수는 있다. 그렇기 때문에 A를 항상 작게 유지시켜 줘야한다. 오름차순 정렬을 한 후 A
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 1. Logic 트리의 지름을 구하는 방법은 먼저 임의의 한 점에서 가장 거리가 먼 노드를 탐색한다. 이후 가장 거리가 먼 노드에서부터 다시 한번 가장 거리가 먼 노드를 탐색했을 때 거기가 트리의 지름이 된다. 2. Code #include using namespace std; int n; vector tree[10001]; bool vis[10001]; int deepestN..
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. Logic 외판원 순회란 도시들(노드)이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌도 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제이다. 아래 그래프를 보자. 이 5개의 노드가 있을 때 순회를 할 수 있는 방법은 총 5가지이다. 1 > 2 > 3 > 4 > 5 2 > 3 > 4 ..
https://www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 1. Logic 1 ~ n번까지의 정점을 순서대로 다 불을 붙혀보면서 그중에서 전부 연소하는데 걸리는 최소 시간을 구하면 됨. 가장 중요한 모든 그래프를 연소시키는 최소 시간을 구하는 법에 대해 설명할 것이다. 먼저 각 정점에서 모든 정점까지의 최단 경로를 알아햐 한다. 문제의 테스트케이스 1번을 보면 두개의 정점을 연결하는 동일한 간선이 ..
