본문 바로가기
728x90

알고리즘 문제 풀이22

백준 - 17070번, 파이프 옮기기 1 문제 BFS 방식 풀이 (with C++) 문제 설명 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1 ×1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈칸만 차지해야 한다. 파이프를 밀 수 있는 방향.. 2022. 10. 4.
백준 - 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.
백준 2434번 - 기타 레슨, 이분 탐색 (Binary Search) 풀이 (C++) 이번에 풀이한 문제는 백준 2434번 기타 레슨 문제입니다. 이분 탐색 알고리즘을 활용해서 풀이할 수 있었고, 풀이한 과정을 간단하게 정리해 보겠습니다! 언어는 C++를 이용해 풀이했습니다. 문제 링크!😀 1. 문제 설명 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 .. 2022. 9. 16.
백준 2470번 - 두 용액, 대표적인 투 포인터 문제 문제 소개 2470번 두 용액 문제는 제목에도 쓰여있는 것처럼 대표적인 투 포인터 알고리즘으로 풀이 가능한 문제 중 하나입니다! solved.ac 기준으로 골드 5 난이도의 문제로 기본적인 투 포인터 문제임에도 불구하고 꽤 높게 난이도가 책정되어 있습니다. 문제 링크입니다!! 😀 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 문제 설명 및 아이디어 우선 입력으로 용액의 개수인 N을 입력 받은 후, 산성 용액(특성 값이 양의 정수)와 알칼리성 용액(특성 값이 음의 정수) 들의.. 2022. 9. 8.
백준 7562번 - 나이트의 이동, BFS를 이용한 그래프 순회 문제 (with C++) 문제 소개 이번에 풀이한 문제는 7562번 나이트의 이동 문제입니다. solved.ac 기준으로 실버 1 난이도이긴 하나, BFS 알고리즘을 적용해야 하는 구조를 이해하면, 쉽게 풀 수 있는 문제였습니다!! 문제 링크입니다!! 😀 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제 설명 및 아이디어 임의의 사이즈의 체스판 위에서 나이트가 놓여 있을 때, 입력받은 도착 지점으로 이동하는데 최소 몇 번 움직여야 하는지 구하는 것이 목표인 문제입니다. 따라서 나이트의 현재 위치에 따라서 다음 번에 이동할 수 있는 .. 2022. 9. 4.
728x90

티스토리툴바