알고리즘
-
[백준 7785] 회사에 있는 사람알고리즘/백준 2019. 5. 17. 00:19
입력 N 제한이 100,000이기 때문에, set을 사용하여 입력과 동시에 정렬을 가능하게 하였다. enter 명령에는 insert시키고 leave 명령에는 erase를 시키면 되는 문제이다. 사전 역 순으로 출력하기 때문에, rbegin()과 rend()를 사용하였다. 출처 : https://www.acmicpc.net/problem/7785 문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가..
-
[백준 1927] 최소 힙알고리즘/백준 2019. 5. 13. 14:57
백준 11279번과 매우 유사한 문제이다. (관련글) 다른 점이라면, 단지 출력을 할 때 가장 작은 수를 출력한다는 점이다. 1. 배열에 자연수 x를 넣는다. 2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 이때 X가 0이면 배열에서 가장 큰 값을 출력하고 X가 자연수라면 (X>0)이면 배열에 X를 삽입한다. 배열에 자연수 X를 넣을 때 마다, top의 위치가 바뀌는 우선 순위 큐를 사용하면 쉽게 풀 수 있다. 출처 : https://www.acmicpc.net/problem/1927 문제 널리 잘 알려진 자료구조 중 최소 힙이라는 것이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다.배열에서 가장 작은 값을 출력하고, 그 값..
-
[백준 11279] 최대 힙알고리즘/백준 2019. 5. 13. 14:53
1. 배열에 자연수 x를 넣는다.2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 이때 X가 0이면 배열에서 가장 큰 값을 출력하고X가 자연수라면 (X>0)이면 배열에 X를 삽입한다. 배열에 자연수 X를 넣을 때 마다, top의 위치가 바뀌는우선 순위 큐를 사용하면 손 쉽게 풀 수 있다. 출처 : https://www.acmicpc.net/problem/11279 문제 널리 잘 알려진 자료구조 중 최대 힙이라는 것이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다.배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)..
-
[백준 1717] 집합의 표현알고리즘/백준 2019. 5. 12. 22:46
Union_Find (유니온 파인드)의 개념을 알고 있으면 금방 풀 수 있는 문제이다.연산 명령이 0이면 Union 함수를 사용하여 같은 집합으로 묶어주면 되고연산 명령이 1이면 Find 함수를 사용하여 최상위 부모가 같은지 확인하여구현하여 풀 수 있는 문제이다. ※ 입력과 출력이 매번 있기 때문에 cin cout 보다는 ※ ※ scanf 과 printf를 쓰는 것이 바람직하다. ※ 참고하면 좋은 글 : 유니온 파인드란?? 출처 : https://www.acmicpc.net/problem/1717 문제 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프..
-
[백준 3015] 오아시스 재결합알고리즘/백준 2019. 5. 12. 16:00
스택을 활용한 문제 중에서는 쉬운 축에 속하지는 않지만 로직을 알고보면 금방 구현할 수 있는 문제이다. 우선 (1 ≤ N ≤ 500,000) N 제한이 50만이기 때문에for문으로 검사를 하면 25억번의 연산 => 25초가 걸리게 된다.(시간초과) 그래서 간단하게 스택을 사용하도록 하면대부분의 스택 연산에는 O(n)만에 연산이 가능하기 때문에거의 1초 내로 풀 수 있게 된다. 자세한 설명은 소스코드를 보면 이해가 쉽다. 출처 : https://www.acmicpc.net/problem/3015 문제 오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다. 이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다. 두 사람 A와 B가 서로 ..
-
[백준 9935] 문자열 폭발알고리즘/백준 2019. 5. 12. 02:31
스택 입문으로 풀기에는 쉬운 문제는 아니다. 보자마자, 떠오르는 방법으로 구현을 해봤지만 보기 좋게 틀린 문제이다.또한 질문게시판에서 반례를 찾아봤지만, 문제의 조건에 맞지 않는 반례 때문에 헤매기도 하였다.( 조건 : 폭발 문자열에서 같은 문자는 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 )을 시켜준다. ** 폭발 문자열의 첫번째 문자는 매번 검사해줘야 한다 ..
-
[백준 11725] 트리의 부모 찾기알고리즘/백준 2019. 5. 11. 23:01
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 문제 루트 없는 트리가 주어진다. 이때, 트..