풀이의 핵심은 Union & Find 알고리즘이다. 위 그림을 보면, 노드 1, 2, 3이 한 집합, 노드 4, 5가 한 집합으로 엮여있음을 직관적으로 알 수 있다. (추후, 작성하겠습니다.) 정답 소스코드 #include using namespace std; int n, m; int unf[1000004]; int Find(int v) { if(unf[v]==v) return v; return unf[v]=Find(unf[v]); } void Union(int a, int b) { a=Find(a); b=Find(b); if(a!=b) unf[a]=b; } int main() { ios_base::sync_with_stdio(0); for(int i=1; i>n>>m; int a, b, c; while..

풀이의 핵심은 이렇다. i는 2부터 123456*2일 때까지 반복: j는 2부터 i*j값이 123456*2일 때까지 반복: i*j의 값은 소수가 아님을 배열에 저장한다; (n이 입력으로 주어진다.) i는 n+1부터 2*n까지 반복: 저장한 배열의 값으로 소수인지 아닌지 판별한다: 소수라면 count; count한 소수의 갯수 출력(이후 다시 n을 입력으로 받고 반복실행); 소수가 아닌 수를 생각해보자면, 어떤 수의 2배, 3배, 4배, ..., n배는 모두 소수가 아니다. 따라서 어떤 수를 i로 생각하고, 2부터 반복으로 곱해나가서 그 값은 소수가 아니라고 저장하는 것이다. (이 방식은 매우 자주 사용되므로 외우는 편이 낫다.) 정답 소스코드 #include using namespace std; int ..

풀이 전에, 선을 기준으로 한 좌표체계를 공간으로 바꾸는 방법은 의외로 간단하다. 오른쪽 위 꼭지점 좌표를 end포인터처럼 생각하면 된다. (소스코드의 input함수 참고) 그러면 아래 그림의 좌표체계를 선이 아닌, 공간처럼 인식할 수 있다. 1. DFS 풀이 DFS 풀이의 핵심은 이렇다. int 영역넓이(전역변수); 풀이함수(solution)에서 좌표마다 반복: 만약 빈 좌표라면: DFS를 돌린다(빈 좌표갯수 count, 인접한 빈 좌표들을 채운다); 반환값1(영역갯수)++; 영역넓이를 반환값2에 저장한다; 영역넓이를 0으로 초기화한다; void DFS(좌표): 현재 좌표를 채운다; 영역넓이++; 4방향반복: 만약 togo좌표가 비어있다면: DFS(togo좌표) 재귀진입; 각 영역마다의 넓이를 전역변수..

풀이의 핵심은 이렇다. 입력으로 주어진 문자열을 하나씩 순서대로 처리한다: 만약 ( 이라면: 막대기의 시작을 알리는 것이다. stack에 넣는다; 만약 ) 이라면: stack pop; stack의 top(가장 최근에 넣은 값)이 ( 이라면: 레이저로 인해 조각들이 생겼다. 생겨난 조각 수(stack의 size)만큼 결과값에 더한다; stack의 top(가장 최근에 넣은 값)이 ) 이라면: 조각의 끝을 알리는 것이다. 결과값에 하나를 더한다; 위의 그림과 함께 보면 의사코드의 이해에 도움이 될 것이다. 주의할 점은, ) 을 처리하려는데 이전에 ( 이 들어왔다면, 막대기가 아닌 레이저이므로 미리 stack에서 pop시켜야 한다. 그래야 조각 수를 올바르게 더할 수 있다. ) 을 처리하려는데 이전에도 ) 이 ..

내가 생각한 풀이의 핵심은 이렇다. 입력으로 주어진 숫자를 하나씩 순서대로 처리한다: 만약 i번째 수 > stack의 top이라면: stack pop; k 하나 감소; i번째 수를 stack에 넣는다; 이후 k가 남아있을 수 있으니, k가 0이 될 때까지 stack을 pop시켜야 한다. (나중에 다른 사람의 풀이를 통해 알게 되었다.) 그리고 stack에 담긴 수를 역순으로 꺼내서 답을 조합하였다. 그런데 stack으로 풀면 시간 초과가 났다. 그래서 vector로 대신하여 풀었더니 맞았습니다!!가 나왔다. (왜 이런지는 잘 모르겠다.) 정답 소스코드 - vector를 이용한 풀이 #include #include using namespace std; int main() { ios::sync_with_st..

문제인식) 다음과 같은 이진트리가 있다. 위 트리를 전위순회, 중위순회, 후위순회하려면 어떻게 해야할까? 참고로 전위순회, 중위순회, 후위순회에 대한 이름이 붙은 기준은 루트노드에 대한 작업순서를 기준으로 이름이 붙었다고 생각하면 쉬울 것이다. 즉, 루트노드를 먼저 작업한다면 전위순회 (루트노드 → 왼쪽서브트리 → 오른쪽서브트리), 루트노드를 중간에 작업한다면 중위순회 (왼쪽서브트리 → 루트노드 → 오른쪽서브트리), 루트노드를 마지막에 작업한다면 후위순회 (왼쪽서브트리 → 오른쪽서브트리 → 루트노드) 가 되는 것이다. 이렇게 각 순회에 따른 출력 결과는 다음과 같아야 할 것이다. 전위순회 1 2 4 5 3 6 7 중위순회 4 2 5 1 6 3 7 후위순회 4 5 2 6 7 3 1 왜 이렇게 나오는지 전위..