고인물을 지양하는 블로그

https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서 www.acmicpc.net 전후관계를 나타내기 위해 방향그래프를 이용했다. A 사건이 B사건에 우선하면 A->B라 표기 다시 문제로 돌아가면, 사건들의 전 후 관계가 ..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r, www.acmicpc.net 첫 번째 접근 방법은 분할과 정복/완탐 이었다. 재귀 함수에서 1 2 3 4분면으로 나누고, Z방향대로 (1->2->3->4) 탐색해 순서를 ..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 기존 조합 문제에서 한 레벨 위의 문제라 할 수 있는데.. 크게 두 가지 부분에서 그렇다. 1) 일단 nCm 에서 n과m의 범위가 100으로 매우 크다. 2) long long을 쓰더라도 100C50의 결과값을 저장할 수 없다. 따라서 DP를 이용해 큰 수의 조합을 구하고, String을 이용해 결과값을 저장해 해결했다. string Add(string a, string b) { string ans; long long sum = 0; while(!a.empty() || !b.empty() || sum) { if(..

없는 시간 쪼개서 팀원들과 주 1~3회 만남을 가지고 기출 풀어보는 시간을 가졌지만, 프로그래밍 스타일을 비슷하게 맞치기에는 부족한 시간이었고, 각자 컴퓨터로 연습하던 때와 컴퓨터 한 대로 문제를 풀어내야하는 대회는 정말 많이 달랐다. 특별히 긴장하지는 않았지만, 예상했던것만큼 문제가 잘 풀리지 않아 시간이 지나면 지날수록 더 초조해지고, 마음만 급해졌다. 올해 예선에서는 온라인 저지 오류로 스코어보드 보고 전략을 짤 수 있는 기회가 거의 없었는데, 사실 스코어보드 오류가 아니었어도 쉬운 문제들만 제출하고 막혀서 전혀 진도가 안나가는 상황이었지만 그래도 아쉬웠다. 비교적 쉬웠던 2017, 2018 문제 난이도 기준, 6~7 문제를 목표로 잡았었는데 한참 모자라는 5문제 제출, 3솔로 마무리했다. 제출 문..

이 또한 방학 때 교수님께서 알려주신 알고리즘으로, 모든 가능한 순열을 생성해본다. https://yunjae-gong.tistory.com/29 Brute Force: 조합 N개의 수가 주어졌을 때. 그중에서 K개를 뽑는 경우 혹은 그 수를 구할 때, 다음과 같은 방법을 이용해 구할 수 있다. 순서는 조합에서 의미가 없으므로, 크게 i를 사용하는 경우, 사용하지 않는 경우 혹은 다른.. yunjae-gong.tistory.com 조합 알고리즘은 i번째 원소로 n을 채택할지 하지 않을지 재귀적으로 함수를 호출해 해결했다. 순열 알고리즘의 경우, N개중 K개를 뽑아 나열해야 하므로, 추가로 각 원소의 위치를 바꿔주는 동작이 추가된다. inline void swap(int &a, int &b) { int t..

N개의 수가 주어졌을 때. 그중에서 K개를 뽑는 경우 혹은 그 수를 구할 때, 다음과 같은 방법을 이용해 구할 수 있다. 순서는 조합에서 의미가 없으므로, 크게 i를 사용하는 경우, 사용하지 않는 경우 혹은 다른 말로 i번째 수로 m을 사용하는 경우, 사용하지 않는 경우로 나누어 생각할 수 있다. 1. 1~N까지 N개의 수 중에서, K개를 뽑는 경우 2. 입력된 N개의 수 중에서. K개를 뽑는 경우 두 가지 경우에 대해 다뤄보겠다. 코드_1 #include int N,K, cnt=0; void Combination (int c[], int i, int n) { if(i

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 올 2월 겨울방학 스터디 때 교수님이 backtracking 소개를 해주시며 처음 접하게 된 문제로, 가장 기본적인 backtracking 문제이다. brute force를 이용한 문제 해결의 시간 복잡도를 알아보면, 해당 위치에 퀸을 놓을 수 있는지 확인하는 possible 함수가 $O(N^N)$ 번 호출되는데, 그 때마다 $O(N)$ (혹은 $O(N)$) 시간을 들여 그 자리에 놓을 수 ..

https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다. www.acmicpc.net 일전에 작성했던 간단한 크루스칼 알고리즘으로 접근했다가 오답이 나왔다. 문제 이해를 조금 잘못했는데, 임의의 정점간 통신에 걸리는 시간이 원래 네..