본문 바로가기

Programming/BOJ277

[C/C++] 백준 #2167 2차원 배열의 합(포함배제 원리) #2167 문제는 2차원 배열 공간에서 사각형으로 지정한 공간에 있는 숫자합을 계산해야 합니다. 지정된 공간의 합을 한번 계산하는 것이라면, 이중 반복문을 이용해서 풀면 되겠지만, 여기는 K개의 질의(query)가 있기때문에 단순하게 처리하면 \(O(KNM)\)이라는 시간 복잡도를 가지게 됩니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 이 문제는 (0, 0)을 시작점으로 해서.. 2023. 4. 12.
[C/C++] 백준 #2166 다각형의 면적(벡터) 이번 문제는 기하와 벡터에 대해서 알고 있으면 쉽게 풀 수 있는 문제입니다. 컴퓨터 그래픽 관련해서 자주 쓰이는 기법입니다. 중고등학교 때, 외적(cross product, outer product, vector product)을 배우고 있지만, 실제로 이런데에 쓰일 수 있다는 점들은 잘 모릅니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 세점 \(O(0, 0)\), \(A(x_A, y_A)\), \(B(x_B, y_B)\)가 있다.. 2023. 4. 12.
[C/C++] 백준 #2164 카드2(큐 자료구조) 이 문제는 #2161 문제와 같은 구조로 푸셔도 되는 문제입니다. 최종 카드를 알아내기 위한 것입니다. 만약 N이 커진다면, 나머지 연산을 통해서 결과를 얻어야 하겠지만, 여기서는 신경쓰지 않아도 됩니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 이 문제와 푸는 방법이 비슷한 #2161 카드 1 문제의 링크는 다음과 같습니다. https://sdev.tistory.com/1218 [C/C++] 백준 #21.. 2023. 4. 11.
[C/C++] 백준 #2161 카드1(큐 자료구조) 이번 문제는 요세푸스(Josephus) 문제와 아주 유사합니다. 요세푸스 문제는 K번째를 제하는 형태이지만, 이 문제에서는 먼저 제하고 시작하는 것이 좀 다릅니다. 요세푸스 (N, 2) 문제와 비숫합니다. 아래는 문제의 링크입니다. https://www.acmicpc.net/problem/2161 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 이 문제는 큐(queue) 자료구조를 활용해서 할 수 있습니다. 요세푸스 문제는 큐를 단순하게 이용할 경우 (N, K) 요세푸스 문제는 큐의 pop 횟수 기준으로 \(.. 2023. 4. 11.
[C/C++] 백준 #2156 포도주 시식(탐욕 알고리즘) 이번 문제는 탐욕 알고리즘의 범주로 놓아야할 것 같아서, 탐욕 알고리즘이라고 적기는 했지만, 문제에서 추천하는 알고리즘은 동적 계획법입니다. 동적 계획법이 더 맞을 수도 있겠죠. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 제가 생각한 알고리즘은 다음과 같습니다. \(fc_0\)은 현재 와인을 선택하지 않았을 때, 최대값입니다. \(fc_1\)은 이전 와인은 선택하지 않았지만, 현재 와인은 선택한 경우입니다. .. 2023. 4. 10.
[C/C++] 백준 #2146 다리 만들기(DFS, BFS) 이번 문제는 최단거리를 찾는 문제이긴 하지만, 이동하는데 드는 비용이 항상 같기 때문에 너비 우선 탐색을 사용하면 되는 문제입니다. 문제는 아래의 링크입니다. https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 이 문제를 풀 때에는 두 단계를 걸쳐서 풀었습니다. 일단 섬마다 고유한 아이디를 부여하기 위해서 깊이우선탐색(DFS)을 이용해서 고유 아이디를 붙였습니다. 다음으로는 모든 섬에 대해서 다리를 놓기 위한 최단 거리를 구하는 작업을 하였습니다. 이 .. 2023. 4. 10.
728x90

티스토리툴바