본문 바로가기

알고리즘 공부 및 문제 풀이

 (317)
[c++] 백준 1931 회의실 배정 백준 단계별로 풀어보기[그리디 알고리즘] 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net [풀이] 회의실 배정은 끝나는 시간이 빠른 순으로 배정해주어야 최대 배정이 가능하다. 끝나는 시간이 빠른 순으로 정렬을 해주되, 같다면 시작 시간이 빠른 회의가 앞에 위치하도록 한다. 그 다음 회의의 시작 시간이 현재 회의의 끝나는 시간과 같거나 더 늦어야 하고, 조건을 만족한다면 회의가 끝나는 시간을 변경해준다. 회의실 배정을 새로 해줄 때마다 cnt 값을 증가시켜준다. [코드] #include #include using namespace std; bool ..
[c++] 백준 2606 바이러스 백준 단계별로 풀어보기[DFS와 BFS] 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net [풀이] DFS를 이용. [코드] #include #include #include #include using namespace std; int n, m, cnt = 0; //정점의 개수, 간선의 개수, 시작 정점 int adj[101][101]; bool isVisited[101] = { false, }; queue q; void dfs(int v) {..
[c++] 백준 1260 DFS와 BFS 백준 단계별로 풀어보기 [DFS와 BFS] DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [풀이] DFS는 재귀를 이용해서, BFS는 큐를 이용해서 구현하였다. 무방향 그래프이기 때문에 인접행렬을 이용해서 인접관계를 표현했고, 같은 isVisited 배열을 이용하기 때문에 BFS 탐색 이전에 다시 초기화를 해주는 작업이 필요하다. [코드] #include #include #include #..
[c++] 백준 14425 문자열 집합 백준 단계별로 풀어보기 [문자열 알고리즘 1] 문자열 집합 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net [풀이] 트라이 알고리즘으로 insert와 find 함수를 구현하여 풀 수 있다. 트라이 알고리즘에 대한 공부는 알고리즘 카테고리에서... [코드] #include #include #include using namespace std; class Node { public: Node* childs[26] = {..
[c++] 백준 14725 개미굴 백준 단계별로 풀어보기 [문자열 알고리즘 1] 개미굴 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net [풀이] 트라이 알고리즘 응용 문제이다. 먼저 문자열을 vector를 이용해 저장하고 map를 이용해 트라이 구조를 나타낸다. 같은 층에 이미 똑같은 문자열이 존재한다면(경로가 존재), 그 다음 노드로 이동해서 단어를 삽입한다. 만약 존재하지 않는다면 새로 노드를 할당받아 단어를 저장한다. map은 key를 기준으로 오름차순 자동..
[c++] 백준 13305 주유소 백준 단계별로 풀어보기 [그리디 알고리즘] 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net [풀이] 가격이 가장 작은 주유소의 기름 최소값과 도로 거리를 곱할 수 있도록 비교해가며 min값을 설정한다. [코드] #include #include long long road[100000]; long long price[100000]; int main() { //주유소의 기름 가격과 각 도시를 연결하는 도로 길이를 입력, 최소의 ..
[c++] 백준 11286 절댓값 힙 백준 단계별로 풀어보기 [우선순위 큐] 절댓값 힙 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net [풀이] pair를 이용해서 입력된 수와 그 수의 절대값을 모두 큐에 저장한다. 우선순위 큐는 pair의 첫번째 인자를 기준으로 값을 저장하고, 그 값이 같다면 두번째 인자를 기준으로 저장한다. min_heap을 이용하여 절대값이 같다면 더 작은 수를 우선으로 저장해 출력하게 한다. [코드] #include #include #..
[c++] 백준 11279, 1927 최대 힙, 최소 힙 백준 단계별로 풀어보기 [우선순위 큐] 최대 힙, 최소 힙 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmic..

티스토리툴바