로재의 개발 일기 로재의 개발 일기

1. 배열에 자연수 x를 넣는다.2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 이때 X가 0이면 배열에서 가장 큰 값을 출력하고X가 자연수라면 (X>0)이면 배열에 X를 삽입한다. 배열에 자연수 X를 넣을 때 마다, top의 위치가 바뀌는우선 순위 큐를 사용하면 손 쉽게 풀 수 있다. 출처 : https://www.acmicpc.net/problem/11279 문제 널리 잘 알려진 자료구조 중 최대 힙이라는 것이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다.배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)..

각각의 노드가 계층적으로 연결이 되어 있는데, 1번 컴퓨터와 몇 개의 컴퓨터가 연결되어 있는지 구하는 문제이다. ※ 입력이 컴퓨터 순서대로 나오지 않는다. 라는 점 주의할 것 ※ 나는 Union-Find로 문제를 풀었다. (참고하면 좋은 글) >> Union-Find란???

Union_Find (유니온 파인드)의 개념을 알고 있으면 금방 풀 수 있는 문제이다.연산 명령이 0이면 Union 함수를 사용하여 같은 집합으로 묶어주면 되고연산 명령이 1이면 Find 함수를 사용하여 최상위 부모가 같은지 확인하여구현하여 풀 수 있는 문제이다. ※ 입력과 출력이 매번 있기 때문에 cin cout 보다는 ※ ※ scanf 과 printf를 쓰는 것이 바람직하다. ※ 참고하면 좋은 글 : 유니온 파인드란?? 출처 : https://www.acmicpc.net/problem/1717 문제 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프..

스택을 활용한 문제 중에서는 쉬운 축에 속하지는 않지만 로직을 알고보면 금방 구현할 수 있는 문제이다. 우선 (1 ≤ N ≤ 500,000) N 제한이 50만이기 때문에for문으로 검사를 하면 25억번의 연산 => 25초가 걸리게 된다.(시간초과) 그래서 간단하게 스택을 사용하도록 하면대부분의 스택 연산에는 O(n)만에 연산이 가능하기 때문에거의 1초 내로 풀 수 있게 된다. 자세한 설명은 소스코드를 보면 이해가 쉽다. 출처 : https://www.acmicpc.net/problem/3015 문제 오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다. 이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다. 두 사람 A와 B가 서로 ..

스택 입문으로 풀기에는 쉬운 문제는 아니다. 보자마자, 떠오르는 방법으로 구현을 해봤지만 보기 좋게 틀린 문제이다.또한 질문게시판에서 반례를 찾아봤지만, 문제의 조건에 맞지 않는 반례 때문에 헤매기도 하였다.( 조건 : 폭발 문자열에서 같은 문자는 2번 이상 나올 수 없습니다) stack st 을 사용하여first에는 문자열의 해당하는 위치second에는 폭발 문자열에 해당하는 인덱스를 삽입하며 진행한다. 기존 문자열 : mirkovC4nizCC44 폭발 문자열 : C4 1. if(a[i] == b[0]) // m i r k o v ... 이때 C에서 (a[6] == b[0]) 이기 때문에 st.push(make_pair( i, 0 )을 시켜준다. ** 폭발 문자열의 첫번째 문자는 매번 검사해줘야 한다 ..

DFS 혹은 BFS 탐색을 사용하여 풀 수 있는 전형적인 문제이다. 가중치가 없는 양방향으로 백트래킹이 필요한 트리이기 때문에 vector tree를 사용하여출처 : 위키백과tree[2].push_back(7)tree[7].push_back(2)...을 사용했다. stack st; // 지나쳐온 노드를 저장하는 stack vector tree[100001]; // tree[i] = j (i번째 노드와 j번째 노드는 연결되어있다) int depth[100001]; // 깊이를 나타낸다 (방문 여부도 검사 가능) int parent[100001]; // 인덱스별 부모를 저장하기 위한 배열 출처 : https://www.acmicpc.net/problem/11725 문제 루트 없는 트리가 주어진다. 이때, 트..

아직 도전하기에는 쉬운 문제는 결코 아닌 듯 했다. 2개의 Stack을 사용하여, 하나는 왼쪽부터 검사 또 다른 하나는 오른쪽부터 검사를 하여 없애고자 하는 문자열을 모두 없애는 기능을 구현하는 것인데, 필자의 소스코드에는 왼쪽과 오른쪽을 합쳐 없애야 하는 알파벳을 사라지게 하는 부분을 아직 구현을 하지 못해 contest solution을 올렸다. http://hsin.hr/2009/index.html위 사이트에 들어가면 다양한 Testcase를 제공하니반례를 찾을 때 매우 유리하다. 출처 : https://www.acmicpc.net/problem/3111 문제 김상근은 창영마을에서의 권력을 유지하기 위해 신문을 검열하려고 한다.상근이는 텍스트 T에서 A라는 단어를 다음과 같은 알고리즘을 이용해서 모..

흔한 부분수열의 합 문제이다. 문제에서 제시한 값과 일치하는 경우의 수를 출력하는 문제이다. 크게 두가지 방법으로 풀 수 있는데1. DFS 탐색을 사용하여 각각의 경우 탐색 2. 비트마스크를 사용하여 모든 경우 탐색 click! => (비트마스크란?) 출처 : https://www.acmicpc.net/problem/1182 문제 N개의 정수로 이루어진 수열이 있을 때, 길이가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지..