본문 바로가기

알고리즘 공부 및 문제 풀이/백준(BOJ)

 (220)
[boj] 백준 11505 구간 곱 구하기 (c++) - 세그먼트 트리 [문제] https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net [풀이] 세그먼트 트리를 이용한 standard 문제이다. 구간 합을 구간 곱으로만 바꿔주면 되는데 sum의 경우(start > right || end < left) 조건에서 0을 return하지만 곱의 경우 0이 반환되면 값이 전부 0이 되므로 1을 return하도록 한다. [코드] #include #include #incl..
[boj] 백준 1194 달이 차오른다, 가자 (c++) - 비트마스킹, BFS [문제] https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net [풀이] 보통의 BFS, DFS 문제에서 추가로 고려해줘야 할 부분은 크게 다음 2가지이다. 1) 똑같은 위치라도 key가 없는 상태에서 방문한 것과 key가 있는 상태에서 방문했을 때가 다르다. 이를 구분해주기 위해 visited[][][key]와 같이 3차원으로 선언하여 현재 소지한 키의 상태를 저장할 수 있도록 한다. 2. 6개의 열쇠 소지 여부에 대한..
[boj] 백준 1766 문제집 (c++) - 위상정렬 [문제] https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net [풀이] 위상정렬 문제이다. 다만, 가능하면 쉬운 문제부터 풀어야 한다는 3번째 조건을 만족시키기 위해(문제 번호가 작을수록 쉬운 문제) 우선순위 큐를 사용한다. 오름차순으로 출력되어야 하므로 -1을 곱해서 우선순위 큐에 넣어준다. [코드] #include #include #include #include #include using namespace::std;..
[boj] 백준 2357 최솟값과 최댓값 (c++) - 세그먼트 트리 [문제] https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net [풀이] 세그먼트 트리(segment tree)를 사용해서 푸는 standard 문제이다. 세그먼트 트리는 특정 구간에 대한 연산을 효율적으로 하기 위해 사용되는데, 보통은 배열의 부분합(구간합)을 저장해놓고 쓴다. 이 문제에서는 최솟값과 최댓값을 구하기 위해 구간의 최솟값과 최댓값을 저장하도록 하였다. (세그먼트 트리도 차후에 알고리즘에 정리해야겠다..
[boj] 백준 2098 외판원 순회 (c++) - TSP(비트마스킹, dp, dfs) [문제] https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net [풀이] TSP(Traveling Salesperson Problem)이라는 외판원 순회 알고리즘이 따로 존재할 정도로 유명한 문제라는데...처음 봤다. 비트마스킹도 익숙치 않아서 여러 블로그 깨작거리면서 갱신히 풀었다. 알고리즘 카테고리에 한 번 정리해야 할 것 같다. TSP는 어떠한 도시에서 출발하여 다른 모든 도시들을 거쳐 출발 했던 도시로 다시..
[boj] 백준 16236 아기 상어 - BFS [문제] https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net [풀이] 일단 조건이 많아서 복잡해 보이는데,,,흐름을 정리하자면 다음과 같다. 1. 아기 상어가 처음 위치한 곳에서 BFS를 돌린다. 아기 상어가 먹을 수 있는 물고기가 더이상 없을 때까지 반복하며 먹을 수 있는 물고기의 거리, 위치를 eat_fish vector에 저장한다. 2. BFS가 끝나면 아기 상어가 먹으러 갈 물고기를 찾는다. 1) 가장 가까운 곳에 위치한 물고기 2)..
[boj] 백준 2252 줄 세우기 - 위상정렬 [문제] https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net [풀이] 학생들의 키에 대한 관계가 주어지고 선후 관계가 없을 경우 출력 순서는 상관이 없다. 간단한 위상정렬 문제이다. [코드] #include #include #include using namespace::std; int main() { int n, m; //n명의 학생, m은 키를 비교한 회수 int in[100001]; vector nod..
[boj] 백준 2493 탑 - stack [문제] https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net [풀이] 본인의 바로 왼쪽에 있는 탑부터 비교하도록 하기 위해 stack을 이용한다. 현재 탑의 높이보다 크면 출력, 작으면 pop()을 해주고, stack이 비면 왼쪽에 있는 탑들 중 신호를 받을 탑이 없다는 것이므로 0을 출력한다. [코드] #include #include #include #include #include using namespace::std; int main() { ..

티스토리툴바