코딩 일지

문제 출처https://www.acmicpc.net/problem/2457골드3 그리디, 정렬 문제이다. 3월 1일부터 11월 30일까지 모든 꽃이 한 개 이상 펴야하면서, 선택한 꽃의 개수가 가장 최소라면 단순히 생각해서펴있는 기간이 가장 길면 된다.그러나, 3월 1일부터 11월 30일까지 라는 조건이 추가적으로 붙어 있으므로, 처음 선택한 꽃은 3월 1일을 포함하면서 가장 긴 기간을 가지는 꽃이 될 것이다.만약 3월 1일을 포함하면서 기간이 가장 긴 꽃이 7월 25일에 진다면, 그 다음 찾아야하는 꽃은 7월 25일을 포함하면서 또 가장 긴 기간을 가지는 꽃을 찾으면 된다.즉, 포함해야하는 날수를 now라고 할 때 now보다 이전에 피는 꽃들 중 지는 날은 가장 나중인 꽃을 찾으면 된다.따라서 피는 날..

문제 출처https://www.acmicpc.net/problem/1991실버1 트리 문제이다. 트리에 관한 설명은 아래 게시물에서 확인할 수 있다.https://codingul1234.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%8A%B8%EB%A6%ACTree [자료구조] 트리(Tree)트리는 앞으로 가장 많이 볼 자료구조이며, 가장 기본적인 그래프다.트리는 유방향 그래프로 위에서 아래로만 진행이 되며, 순환이 없다.트리의 개념은 다음과 같다.트리는 하나의 루트 노드를codingul1234.tistory.com 재귀적으로 봤을 때,전위 탐색은데이터 출력 -> preorder(tree.left) -> preorder(tree.right)중위 ..

문제 출처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 #..