본문 바로가기
728x90

백준21

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 - 3584번, 가장 가까운 공통 조상 [LCA] 이번에 풀이한 문제는 3584번 LCA(Lowest Common Ancestor), 최소 공통 조상 문제입니다. 문제 제목에서 알 수 있듯이, 트리 정보를 입력받은 후에 두 개의 노드의 최소 공통 조상을 찾으면 되는 문제입니다. 최소 공통 조상은 위 그림과 같이 부모 노드로 타고 올라갈 때, 가장 높이가 낮으면서, 두 개의 노드의 공통 조상인 노드입니다. 이러한 유형을 풀어봤던 것 같은데, 각 노드의 부모 노드 정보를 저장한 뒤에 이를 활용해야 한다는 부분까지는 생각이 났는데, 정확한 알고리즘이 생각나지 않아 다른 분들의 풀이를 참고했습니다. 더 효율적인 방법이 있겠지만, 일단 이 문제에 적용할 수 있는 가장 쉬운 풀이는 하나의 노드가 먼저 부모를 거슬러 올라가며, 방문 처리하며 탐색한 뒤에 두 번째 노.. 2023. 1. 17.
BOJ - 1300번, K번째 수 이분 탐색을 이용한 풀이 (C++) 이번에는 오랜만에 이분 탐색 태그가 달린 문제를 풀어봤습니다. 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 난이도가 골드 2였는데, 역시나 여러 가지 아이디어를 생각하다 다른 분의 풀이를 참고해서 해결할 수 있었습니다. 풀이 과정 정리 요새 난이도가 있는 문제 풀이를 잘 안 해서 그런지 풀이를 보고 이해하는 것도 조금 어려웠던 문제입니다. 우선, 처음 문제를 봤을 때는 배열의 특징부터 뽑아 봤습니다. A 배열은 대칭 행렬 구조이다. A 배열의 대각선 상에 위치한 원소들의 값은.. 2022. 12. 30.
백준 - 11048번, 이동하기 문제 BFS및 Dynamic programming 풀이 (C++) 이번에 풀이해본 문제는 11048번 이동하기 문제로, solved.ac 기준 실버 2 난이도의 문제입니다. 요즘 들어 ps를 너무 오랫동안 방치해서 감을 살릴 겸 기본적인 예제가 없을까 하다가 적당한 난이도의 문제가 보여서 풀게 되었습니다. https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 문제 설명부터 정리한 이후 제 풀이 과정에 대해서 정리해 보겠습니다! 문제 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나.. 2022. 10. 31.
백준 - 12100번 2048 - easy 문제 풀이 정리 이번에 풀어본 문제는 solved.ac 기준 class 5에 속하는 2048문제입니다. 다들 알고 계시는 2048게임을 5번까지 시뮬레이션했을 때 결과로 뽑아낼 수 있는 최대의 수를 찾는 문제로 원래 2048 게임은 한 번 이동이 발생할 때마다 새로운 블록이 등장하는 것과 다르게 이 문제에서는 새로운 블록이 등장하지 않는 전제 하에 시뮬레이션을 구현하면 됩니다. 문제 링크 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048 게임은 여기서 플레이 해보실 수 있습니다! 2048 J.. 2022. 10. 13.
백준 - 17070번, 파이프 옮기기 1 문제 BFS 방식 풀이 (with C++) 문제 설명 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1 ×1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈칸만 차지해야 한다. 파이프를 밀 수 있는 방향.. 2022. 10. 4.
728x90

티스토리툴바