본문 바로가기
728x90

알고리즘 문제 풀이22

BOJ - 23291번 어항 정리 문제 문제 https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 이번 문제는 백준 사이트의 삼성 SW 역량 테스트 기출문제집에 있는 문제로, 구현 유형의 문제입니다. https://www.acmicpc.net/workbook/view/1152 문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon) www.acmicpc.net 저는 어항을 접어서 시뮬레이션하는 과정이 막혀, 다른 분의 풀이를 참고해서 풀이하게 되었습니다. 풀이 과정 참고 https:.. 2023. 10. 6.
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.
백준 - 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.
백준 - 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.
728x90

티스토리툴바