본문 바로가기
728x90

cpp12

BOJ - 2638번 치즈, BFS를 이용한 풀이 정리 이번 문제는 BFS 혹은 DFS와 같은 그래프 탐색 알고리즘을 이용하여, 이후 상황에 대한 시뮬레이션 과정을 구현하는 문제였습니다. 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 위와 같이 주어진 모눈종이에서 외부 공기와 2개의 면 이상이 닿아있는 치즈는 녹는 상황에서 치즈가 모두 녹는데 걸리는 시간을 구하는 문제입니다. 간단한 그래프 탐색 문제처럼 단순하게 순회를 해서 해결되는 문제가 아니었고, 시간의 흐름을 측정할 수 있어야 했습니다. 그 이유는 그 시간대에서 녹을 위치에 있는 치즈가 모두 .. 2023. 2. 1.
BOJ - 2792, 보석 상자 매개 변수 탐색 (이분 탐색) 이번 문제는 매개 변수 탐색(parametric search) 문제입니다. 2792번: 보석 상자 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하 www.acmicpc.net 그동안 그냥 이분 탐색이겠거니 하고 풀이했는데, 매개 변수 탐색 문제는 이분 탐색 기법을 적용하지만 다음과 같이 약간의 개념 차이가 있었습니다. 매개 변수 탐색이란? 이진 탐색(이분 탐색)을 사용해서 조건에 만족하는 최댓값을 구하는 방법을 의미한다. 정리하면, 기존의 이분(이진) 탐색은 수열 내에서 lower-bound 또는 upper-bound로 대소 비교를 통해 찾고자 하는 수의 위치를.. 2023. 1. 3.
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.
BOJ - 2294번 동전 2 문제풀이 (DP, SET 사용) 문제 소개 n가지 종류의 동전을 갖고, k원의 금액을 최소 개수의 동전으로 만드는 어떻게 보면, 기본적인 dynamic programming 문제입니다. 하지만, 풀이하면서 몇 가지 실수가 있었어서 풀이 과정을 간단하게 정리해보려고 합니다. 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 문제 n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수.. 2022. 12. 28.
백준 - 5014번, 스타트링크 문제, BFS 방식 풀이 정리 (C++) 이번에 풀이한 문제는? 백준 5014번 스타트링크 문제 풀이 정리입니다. https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net solved.ac 기준 실버 1 난이도의 문제이고 저는 BFS 방식으로 그래프를 탐색하는 알고리즘을 적용해서 풀이해 봤습니다. 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 .. 2022. 11. 9.
백준 - 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.
728x90

티스토리툴바