본문 바로가기

알고리즘51

BOJ 14891 - 톱니바퀴 14891번: 톱니바퀴 (acmicpc.net) 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 접근 방법 처음 문제를 잘못 해석했다. 톱니바퀴를 돌리고 나서, 맞닿는 부분끼리 비교하는 것으로 했지만 문제에선 먼저 비교를 다 한 후에, 돌리는 것으로 문제가 작성이 되어 있었다. 문제는 쉽게 해결할 수 있다. 톱니바퀴가 4개, 각 톱니바퀴의 바퀴상태가 8개 이므로 브루트포스를 이용하여 모두 확인하는 방향으로 구현했다. DFS처럼 재귀를 이용하여, 옆 톱니바퀴와 비교하는 식으로 진행하였다. 이 과정에서 비교 .. 2024. 3. 31.
[시뮬레이션] BOJ 15686 - 치킨 배달 with c++ 15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 접근 방법 1. 폐업하지 않을 치킨집 M개를 선택한다. 2. 해당 폐업하지 않은 치킨집들과 집 사이의 거리들의 합 중 최소값을 구한다. 위 두 가지가 이번 문제의 핵심이다. 폐업하지 않을 치킨집을 고르는 방법 브루트포스밖에 없는 거 같다. 시간을 줄이기위해 백트래킹을 이용하기로 했다. 선택된 M개의 치킨집들과 집과의 거리의 최솟값을 구하기 위해 각 집마다 치킨집들과의 거리를 재어보고 이 중 가.. 2024. 3. 24.
BOJ 14502 - 연구소 14502번: 연구소 (acmicpc.net) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 이번 문제는 DFS와 브루트 포스를 이용하여 풀 수 있는 문제이다. 실행시간도 2초라 널널할 것 같아 다음과 같이 풀었다. 알고리즘은 다음과 같다. 1. 빈 칸(0) 중 3곳을 골라 벽(1)을 세운다. 2. 벽을 세운 상태에서, 바이러스(2)들을 그래프탐색 시키며 지나간곳을 체크한다. 3. 바이러스가 지나가지 않았고, 벽이 아닌 곳의 수가 가장 큰 값을 구한다. 간단하게 해결할 수 있는 문제이다. visited[10][10]을 이.. 2024. 3. 12.
BOJ 2206 - 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1차 시도 부수는 경우와 부수지 않는 경우 총 두가지의 경로가 존재한다. 따라서, 이를 해결하기 위해 부수는 경우를 이차원 배열을 이용하여 저장하려고 시도하였다. broken[][] map[][] chk[][] 그러나 이에 대한 문제가 존재한다. 만약 벽을 하나도 부수지 않는 경우에 이를 이용하면, 도달하지 못한다는 결과가 도출된다. 이런 문제가 발생하는 이유는 벽을 부순.. 2024. 3. 5.
BOJ 16987 - 계란으로 계란치기 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 접근 방법 전형적인 백트래킹 문제이다. 순서대로 계란을 집어, 나머지 계란 중 하나를 치면 되는 문제이다. 이 문제의 핵심은 조건문을 어떻게 작성하냐 이다. 내가 틀렸던 예제는 다음과 같다. 3 1 4 8 1 3 1 // 정답: 2 손에 든 계란 외에 모든 계란이 깨진 경우를 체크해주지 않아 답이 1이 나왔다. 이를 bool flag를 통해 쉽게 수정하였다. 코드 #include #.. 2024. 2. 28.
[그리디 #21] BOJ 7570 - 줄 세우기 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 1차 시도 처음에 이걸 그리디로 해결하기 위해서 다음과 같이 생각했다. 1. 앞으로 옮겼을 때, 뒤쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야한다. 2. 뒤로 옮겼을 때, 앞쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야 한다. 그러나 이것은 금방 틀리다는 것을 알 수 있다. 가령 1,2번이 맞다고 하더라도 순서대로 이어져있지 않으면 문제가 된다. 따라서, 순서를 집중해서 공략하는게 좋겠다고 .. 2024. 2. 27.

티스토리툴바