url : https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름 leaf노드 ~ leaf노드까지의 거리 구하기 1. leaf 노드 구하기 (dfs) 2. leaf 노드에서 출발하여 dfs 최대 거리 구하기(leaf 노드 ~ leaf 노드) 코드 #include using namespace std; int v, n, a, b, farthestNode, maxDistance; vector tree[100004]; int vi..
url : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 완전탐색 문제인 줄 알았는데, dp문제이다. 완전 탐색으로 풀 경우 O(3^N) 시간복잡도이고, 좀 더 단순한 방법을 생각해야 통과할 수 있다. 구하는 것은 최소 비용이므로 부분 문제의 해가 전체 문제의 해가 될 수 있다. 즉, dp로 풀 수 있다. dp의 경우 시간복잡도는 O(N)이다. DP 생각 타이밍 완전탐색의 시간복잡도가 클 경우 / 1번부터 N번까지 차례대..
오늘은 매주 알고리즘 스터디에서 진행하는 이벤트 날인데, 모여서 3문제를 3시간 안에 푸는 날이다. 문제 난이도는 스터디원을 고려하여 실버 3~골드 2, 프로그래머스 level 1,2로 출제했다. 쉬운 문제, 중간문제, 좀 더 어려운 문제 순으로 문제를 냈다.(내가 스터디 장이라 문제를 출제했다.) 결과적으로 어려운 문제(3번 문제)는 풀지 못했는데, 카카오 문제였다!! ㅠㅠ 내일 문제를 다시 한번 풀 예정이다. 1번 문제 url : https://school.programmers.co.kr/learn/courses/30/lessons/147355 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받..
url : https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 오랜만에 쉬운 DFS 유형 문제를 풀었다. dfs가 오랜만이다보니 헤맸는데, 역시 계속해서 다양한 문제 유형을 접하는 것이 중요한 것 같다. 코드 #include using namespace std; int n, m, tmp; int visited[10], num[10]; vector arr; void dfs(int here, int cnt){ if (cnt==m){ for(i..
Happy New Year! url : https://school.programmers.co.kr/learn/courses/30/lessons/181187 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 수학 문제는 로직 구현시 기존 존재하는 공식이나 정리가 있는지 확인하고, 이를 사용하는 것이 중요하다. 원 공식 : x2+y2=r2 을 이용하여 x 지점에 대해 두 원 사이에 속하는 y 점 개수를 구하면 된다. 원이므로 대칭을 이용하여, 4사분면의 한 부분만 구하고, 구한 개수 *4 를 하여 답을 구한다. 로직 1) x 위치를 기준으로 1~r2 까지 반복문..
url : https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 내일 좀 더 자세하게 정리할 예정... 수학적 지식 +1 코드 #include using namespace std; const int MOD = 1000000007; // 빠른 거듭제곱 함수 long long pow(long long base, int exponent) { long long result = 1; while (exponent > 0) { if (exponent % 2 == 1) result = ..
url : https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 2 문제이다. N이 1000 이하인 이항 계수에 10007로 나눈 나머지를 구하는 문제이다. 수학적 지식을 이용해야 빡센 시간 복잡도를 통과할 수 있다. 이항 계수 계산 이항 계수는 팩토리얼 계산을 베이스로 한다. N이 커질수록 직접 N!, K!, (N-K)!를 구하여 나누는 것은 매우 큰 수가 되기 때문에, 어떤 타입이던 오버플로우가 발생한다. 참고로 13!부터 int 타입 범위를 초과하고, 21!부터 long long 타입 범위를 초과한다. ..
url : https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 2 문제를 풀지 못해 이항 계수 1 문제를 풀었다. 이항 계수 2는 더 큰 팩토리얼(1000!)를 다룬다. 내일 다시 이항 계수 2 문제를 도전해볼 생각이다. 코드 #include using namespace std; int n, k, p1, p2; long long answer = 1; int main(){ cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0); // 1. 입력받기 cin >> n >..
