코딩 일지

문제 출처https://www.acmicpc.net/problem/2606실버3 유니온 파인드 또는 dfs 문제이다. dfs로 푸는 풀이는 경우가 많지만,이 문제와 같은 경우는 1번 컴퓨터와 연결되어있는지 안되어있는지만 확인하면 되는 문제이므로유니온 파인드를 이용한 풀이도 가능하다.유니온 파인드에 관한 해설은 아래 링크를 참고하면 된다.https://codingul1234.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C-Union-Find [알고리즘] 유니온 파인드 (Union-Find)유니온 파인드유니온 파인드 (Union-Find)란, 합 집합을 만드는..

문제 출처https://www.acmicpc.net/problem/16236 골드3 BFS, 우선순위 큐 문제이다. 상당히 재밌게 푼 bfs 문제이다.shark 구조체에 아기 상어 위치의 행과 열, 그리고 먹은 물고기의 개수, 크기, 움직인 횟수, 그리고 우선순위 큐에서 움직인 횟수, 행의 크기, 열의 크기 순으로 오름차순으로 정렬할 연산자 오버로딩까지 정의해준다.struct shark{ int row; int col; int eatFishCnt; int size; int cnt; bool operator s.col; } return row > s.row; } return cnt > s.cnt; }};..

문제 출처 https://www.acmicpc.net/problem/2012 실버3 그리디, 정렬 문제이다. 불만도는 |A[i]-실제 등수| 라고 한다. 그럼 당연히 불만도가 최소가 되기 위해선 자신이 예상한 등수와 현재 등수가 근접해야한다. 만약 1등을 예상한 사람이 2명이라면, 이 1등 한 명은 어디로 가야할까? 이 1등 또한 최소가 될려면 1등과 가장 근접한 등수를 뺴야한다. 따라서 오름차순으로 정렬한 후 1등부터 찾아나가면 된다. #풀이 #include #include #include #define MAX 500000 using namespace std; typedef long long ll; int main() { int arr[MAX+1]={0,}; vector v; int N; ll ans ..

문제 출처 https://www.acmicpc.net/problem/2164 실버4 큐 문제이다. 1. 큐에 1~N까지의 수를 순서대로 넣는다. 2. pop 3. front를 push한다. 4. pop 5. 큐가 전부 빌 때까지 2번부터 다시 반복한다. 단순히 위 로직을 반복하기만 하면 되는 문제이지만, 처음 pop을 할 때 큐가 빌 수 있기 때문에, 체크를 한 번 해줘야한다. #풀이 #include #include using namespace std; int main() { queue q; int N,ans=0; cin>>N; for(int i=1;i

문제 출처https://www.acmicpc.net/problem/2877 골드5 수학 문제이다. 문제에서 사용하는 숫자는 4와 7 두 개 존재한다.이는 2진수와 유사한 성질을 가지기 때문에, 2진수를 구할 때 사용한 방식을 응용할 것이다.다만, 2진수는112103114100510161107111인 반면, 4와 7은14273444475746777444이다.위 표를 통해 알 수 있듯, 1만 존재할 때는 4와 완벽히 대응을 하지만, 0이 존재하면 대응되지 않게된다. 그럼 조금 더 규칙을 찾아보자. 2를 4와 7로 변환해보면2 % 2 = 02 / 2 = 110으로 47이 나와야한다.이걸 7로 나오게할려면 2%2 = 0 이후에2로 나누었을 때 반복문 또는 재귀가 무조건 끝나야 한다. 대부분 2진수를 구하는 재귀..

문제 출처https://www.acmicpc.net/problem/1167 1167번: 트리의 지름트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지www.acmicpc.net골드 2 트리 문제이다. 임의의 두 점 사이의 거리 중 가장 긴 것을 찾으면 되기에 dfs를 사용했다. 정점 1에서 탐색을 했을 때 가장 길이가 긴 정점은 11을 갖는 5이다.정점 2에서 탐색을 했을 때 가장 길이가 긴 정점은 10을 갖는 5이다. 내가 정점 1을 기준으로 가장 긴 길이를 찾아내도록 풀었다면 위 예제는 문제없이 11이라는 답이 제대로 나오지만정점 2를 기준으로 ..

문제 출처https://www.acmicpc.net/problem/1149 1149번: RGB거리첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나www.acmicpc.net실버 1 다이나믹 프로그래밍 문제이다. 규칙은 1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.다음과 같다.그럼 결국 n번 집의 색과 n-1번 집의 색이 다르기만 하면 된다는 소리다. 따라서 점화식은dp[n][0] = rgb[n]...

문제 출처https://www.acmicpc.net/problem/1043 1043번: 거짓말지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게www.acmicpc.net골드 4 유니온 파인드 문제이다. 예제 6를 봐보자진실을 아는 사람1, 2 ,71파티3, 42파티53파티5, 64파티6, 85파티8 i12345678parent12345678 parent 배열에 유니온 파인드를 사용하면i12345678parent12335575이 된다.이 상태에서 1파티부터 5파티까지 다시 탐색하며 진실을 아는 사람과 연결되어 있는 사람을 골라 제외하면 된다.   #풀이#include #..

문제 출처https://www.acmicpc.net/problem/1005 1005번: ACM Craft첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부www.acmicpc.net골드 3 위상 정렬 문제이다.위 예시에서 4번 건물을 짓기 위해선 2번 건물과 3번 건물이 지어져있어야한다.그렇다면 2번 건물과 3번 건물이 지어졌다는 것을 어떻게 확인할 수 있을까? 바로 해당 정점으로 향하는 간선의 개수를 각각 세주면 된다.정점으로 향하는 간선의 개수를 담아주기 위한 degree 배열을 만들었다.for(int i=0,a,b;i>a>>b; graph[a].push_..

종강하기도 했고 여태 풀었던 문제들을 다시 복습하는 겸 부계정으로 문제를 다시 풀기로 마음을 먹었다. 이왕 정리하는 김에 요번에는 문제 포스팅까지 해볼려고 한다.문제 출처https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.www.acmicpc.net실버 3 다이나믹 프로그래밍 문제이다.N0 출력 횟수1 출력 횟수010101211312423535658781381321 다음과 같이 나오게 된다. 단순히 N-1번째 피보나치 수와 N번째 피보나치 수를 구하는 문제이다.그러나int fibonacci(int n) { if (n == 0) { printf("0"); ..