전체 글

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/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 1. Logic - 처음 문제를 딱 봤을 때 map이 먼저 생각났다. map로 선언한 후 접근하면 풀릴 것 같았다. 그리고 이후에 문제의 범위를 봤을때 500000이길래 이분탐색을 사용해서 숫자를 찾아야하는구나 라고 느꼈다. 사실 map과 이분탐색 둘다 해봤는데 둘다 통과 된다. 하지만 이분탐색이 시간복잡도가 더 작을 뿐이다. 2. Code map을 이용한 풀이 #i..

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번을 보면 두개의 정점을 연결하는 동일한 간선이 ..

https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 1. Logic 우리가 이 문제에서 구해야 할 점은 2가지이다. 1. 모든 사람들이 만나는 시간. 2. 1분도 쉬지 않고 달려야 하는 사람들이 지나는 도로의 수 : 도착점에 가장 늦게 도착하는 경로의 갯수 이제 구하는 로직을 설명해 볼건데 순서대로 보면 1. 모든 사람들이 만나는 시간. 모든 사람들이 만나려면 도착점에 먼저 들어온 사람은 가장 늦게 도착한 사람이 올 때 ..