본문 바로가기
728x90

알고리즘6

BOJ - 2302번 극장 좌석 문제 (C++) dp를 이용한 풀이 회고 들어가면서.. 문제 설명을 처음 읽고, 전체 문제를 작은 단위의 문제로 쪼갠 뒤 그 결과를 조합해서 전체 문제를 해결해야겠다는 느낌은 받을 수 있었으나 아이디어가 명확하게 떠오르지는 않았습니다. https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 그렇게 몇 번 풀이를 미루다가 오늘 이 문제를 다시 풀게 되었습니다. 다른 방식의 풀이를 보아하니 fibonacci 방식으로 수열이 이어지고, 이를 곱하는 결과로 계산을 한 풀이가 대부분이었는데, 저는 다른 방식으로 .. 2023. 8. 30.
BOJ - 10868번, 최솟값 문제 Segment Tree를 이용한 풀이 이번 문제는 주어진 N개의 정수들에 대해 M번의 구간 최솟값을 묻는 질의에 올바른 답을 반환하는 알고리즘을 구현하는 것이 목표입니다. 물론, 구간의 최솟값을 확인하기 위해 linear한 탐색 방식을 취할 수 있겠지만, 이렇게 하는 경우 - worst case 100,000(N의 최댓값) x 100,000(M의 최댓값) = 10^12번의 연산 위와 같이 연산의 횟수가 너무 커서 시간 초과를 결과로 받게 될 것입니다. 따라서 지난번에 정리한 세그먼트 트리의 개념을 구간 합을 구하는 대신 최솟값을 구할 수 있도록 변형해서 이번 문제를 풀이하는 방식을 채택해 봤습니다. https://kkkdh.tistory.com/entry/%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%E.. 2023. 1. 18.
BOJ - 3584번, 가장 가까운 공통 조상 [LCA] 이번에 풀이한 문제는 3584번 LCA(Lowest Common Ancestor), 최소 공통 조상 문제입니다. 문제 제목에서 알 수 있듯이, 트리 정보를 입력받은 후에 두 개의 노드의 최소 공통 조상을 찾으면 되는 문제입니다. 최소 공통 조상은 위 그림과 같이 부모 노드로 타고 올라갈 때, 가장 높이가 낮으면서, 두 개의 노드의 공통 조상인 노드입니다. 이러한 유형을 풀어봤던 것 같은데, 각 노드의 부모 노드 정보를 저장한 뒤에 이를 활용해야 한다는 부분까지는 생각이 났는데, 정확한 알고리즘이 생각나지 않아 다른 분들의 풀이를 참고했습니다. 더 효율적인 방법이 있겠지만, 일단 이 문제에 적용할 수 있는 가장 쉬운 풀이는 하나의 노드가 먼저 부모를 거슬러 올라가며, 방문 처리하며 탐색한 뒤에 두 번째 노.. 2023. 1. 17.
백준 - 14938번, 서강그라운드 문제 풀이 - (C++) 이번에는 solved.ac에서 적당한 난이도의 문제를 고르다 class 4로 분류된 14938번 서강그라운드 문제가 적당히 풀만하지 않을까?라는 생각으로 풀어봤습니다. 난이도는 solved.ac 기준 골드 4로 class 4에 속한 평균적인 문제 같습니다. 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제 설명 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강.. 2022. 9. 30.
백준 - 17144번: 미세먼지 안녕! 문제 풀이 과정 정리 (C++) 💎 "미세먼지 안녕!" 문제 풀이 정리! 이번에 카카오 코테를 보고 빡구현 문제를 조금 풀어봐야겠다 싶어서 이 문제를 풀게 되었습니다. solved.ac에서 class 4에 있는 문제인데, 예전에 한 번 풀려다가 귀찮아서 안 풀었던 것도 생각나서 이번 기회에 정리해보려 합니다. 문제 링크😀 문제 설명 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다.. 2022. 9. 25.
BOJ - 11054번 가장 긴 바이토닉 부분 수열, 동적계획법 문제 이번 문제는 동적 계획법(Dynamic programming)을 활용해 쉽게 풀이할 수 있는 문제입니다. 가장 긴 증가하는 부분 수열 구하기 + 가장 긴 감소하는 부분 수열 구하기 문제를 합친 문제라고 볼 수 있습니다! 0. 문제 링크 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 1. 문제 설명 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 2.. 2022. 8. 16.
728x90

티스토리툴바