Doby's Lab

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 별자리를 트리라고 생각했을 때, 거리 값이 비용 값이고, 총비용이 최소가 되게 구하려면 최소 스패닝 트리를 이용하면 된다. 생각을 해야 했던 부분은 각 별(노드)끼리의 거리였다. 복잡하게 생각할 필요 없이 2중 for문을 이용해 쌍방향으로 최소 스패닝 트리를 할 수 있도록 만들어주었다. for(int i = 0; i < v.size(); i++){ for(int j = 0; j < v.size();..

https://www.acmicpc.net/problem/18113 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. www.acmicpc.net 해석만 잘 되면 쉬운 문제였다. 이분 탐색이 필요했던 이유는 k의 범위가 1~10^9까지 가질 수 있었기 때문에 O(N)으로 하면 시간 초과가 나서 이분 탐색인 O(logN)으로 풀어야 한다. #include #include using namespace std; int n, k, m; vector v; int main(){ cin >> n >> k >> ..

11월 회고록을 안 쓰고, 12월 회고록까지 몰아서 올해를 마무리하려 한다. 성공적으로 올해 최종 목표 '백준 플래티넘' 이루어냈다! 정말 솔직하게 못 할 줄 알았다. 골드 1을 찍었을 때가 12월 초였는데 골드 1을 찍은 다음날, 플로이드 와샬 알고리즘을 공부하고 나서 포인트가 쭉쭉 오르길래 입대 전날까지 달리면 가능하겠다 싶어서 시작하게 되었다. 진짜 입대 전날까지 달렸으면 울 뻔했다. 그래도 목표는 이루었으니 후회는 없다. 그럼 11월부터 회고를 해보자. [11월 회고] 11월은 10월에 이어서 티어 올리기 때문에 힘들었다. 그러다가 어느 날 카페에 가서 코딩하면서 깨달은 내용을 적어둔 게 있었다. https://draw-code-boy.tistory.com/112 [가끔은 말로] 즐기면서 합시다 ..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 이번 문제는 공부할 포인트가 많았다. 글과 코드가 꽤 길기 때문에 앞서 공부할 내용을 정리하면 배열의 역할, 발상의 전환 exit(0); -> 프로그램 자체 종료 DFS에서 다음 좌표값도 넘겨주기 (시간 소요 줄임) 처음엔 백트래킹을 생각하지 않고 풀려했다. 스도쿠 표를 1행 1열부터 탐색하면서 0이면 check함수를 콜 하여 그 자리에 들어올 수를 넣어주었다. 허나, 아래 코드를 보면 이 방법이..

https://www.acmicpc.net/problem/13925 13925번: 수열과 쿼리 13 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) 2 x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y www.acmicpc.net 한 문제만 풀면 플레티넘이라서 멋지게 피날레를 장식하고 싶은 마음에 풀 수 있을 거 같은 다이아 문제를 골랐었다. (그러지 말 걸 그냥 플레 문제 2개 더 풀걸) 다이아다 보니 당연히 어려웠고, 아 이게 다이아인가 싶었다. 우선 쿼리의 종류는 4가지다. x y v: Ai = (Ai + v) % MOD를..

https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 직전의 포스팅과 똑같은 문제다. https://draw-code-boy.tistory.com/203 [알고리즘] 백준 1725번: 히스토그램 (C++), 세그먼트 트리의 응용 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의..

https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 이번 문제는 유난히 어려웠다. 처음에 떠올랐던 방법은 히스토그램의 높이 중 제일 작은 것을 골라서 전체 구간의 길이와 곱해준 값을 출력해줬었다. >> 차라리 이럴 거면 입력받을 때 최솟값을 구해서 구간과 곱해주는 건데 세그먼트 트리 문제라는 이유로 세그먼트 트리를 구한 게 멍청했다. 하지만, 이 방법이 안 되는 이유는 두 가지에서 떠올랐다. 어떤 높이가 0인 경우 >>..

https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 플로우 전체의 최소 비용을 구하는 문제다. 입력만 행렬의 형태로 들어올 뿐, 최소 스패닝 문제였다. 다만, 입력 과정에서 어차피 양방향이라 주석된 부분처럼 i가 j보다 크거나 같은 경우는 틀렸다고 했었다. >> 이유를 파악하지 못하고 있다.. >> 최소 스패닝 트리에서는 방향이 의미 없지 않나..? for (int i = 1; i > value; edge.push_back({ {i, j}, val..