본문 바로가기

Algorithm Problem/백준

[백준] 3980 - 선발 명단 1. 문제 이해 각 테스트케이스마다 11번씩 11개의 숫자가 주어진다. 즉, 11X11개의 숫자가 주어진다. 각 숫자가 의미하는 것은 포지션에 적합한 정도를 의미한다. 각 포지션은 0 ~ 10으로 숫자로 나타낼 수 있다. 이 때 모든 포지션에 선수를 배치했을 때 최대 적합도를 찾는 문제이다. ( 정답은 항상 존재 ) 2. 문제 풀이 숫자가 11개로 적으므로 브루트포스로 충분히 풀 수 있다. 포지션을 기준으로, 선수의 적합도를 더해나가면 된다. 이 때 기준은 포지션이 아니라 선수가 될 수 있다. 11명 전부 선택해야 하기 때문이다. 브루트포스는 재귀로 풀어나간다. 포지션별로 1명만 선택해야 하므로 어떤 포지션이 선택되었는지 알 수 있는 배열이 필요하다, bool position[11]; // true이면 .. Algorithm Problem/백준 2023. 9. 5.
[백준] 2591 - 숫자카드 1. 문제 이해 입력으로는 40글자 이하의 숫자가 한줄로 주어진다. EX) 27123 이 숫자는 1부터 34 까지 적힌 카드를 일렬로 나열해서 만들어낸 숫자이다. 이 때 카드를 나열하는 경우는 여러가지가 될 수 있다. 27123 의 경우 [ 2 ][ 7 ][ 1 ][ 2 ][ 3 ] [ 2 ][ 7 ][ 12 ][ 3 ] 위 2가지 경우 이외에도 4가지 경우가 존재하여 총 6가지 경우의 수가 존재한다. 입력으로 받은 숫자를 만들어 낼 수 있는 카드의 배열의 경우의 수를 구하는 문제이다. 2. 문제 풀이 이 문제는 작은 문제로 쪼갤 수 있는 문제이다. 27123의 경우 2를 빼놓고 7123의 경우의 수를 구하고 27을 빼놓고 123의 경우의 수를 구할 수 있다. 27123의 정답 = 7123의 정답 + 1.. Algorithm Problem/백준 2023. 9. 4.
[백준] 20007 - 떡 돌리기 1. 문제 이해 N개의 집과 각 집들을 이어주는 M개의 양방향 도로가 있다. 시작점과 하루에 이동할 수 있는 거리가 주어졌을 때, 모든 정점을 방문하기 위한 최소 소모 날짜를 구해야 한다. 이 때, 떡은 한번에 하나씩만 들고갈 수 있으므로, 특정 집을 방문하면 반드시 시작점으로 돌아와야 한다. ( 떡 다시 들기 위해서 ) 최소 소모 날짜를 구해야 하므로, 시작점에서 다른 정점까지의 최소 거리를 구하면 된다. 즉, 다익스트라 알고리즘을 사용하면 된다. 2. 문제 풀이 문제 입력에 따라 양방향 도로가 존재하는 그래프를 구현한다. 그리고 다익스트라 알고리즘을 이용하면 시작점에서 다른 모든 정점까지의 최소 거리를 구할 수 있다. 거리가 가까운 집 부터 방문한다고 했으므로 정렬을 한다. 그리고, 하루에 X보다 더.. Algorithm Problem/백준 2022. 11. 29.
[백준] 17779 - 게리맨더링 2 1. 문제 이해 N X N 배열이 하나 주어진다. 이 배열의 각 칸은 구역을 의미하고, 구역들이 모여 하나의 선거구가 된다. 선거구는 5개가 존재하며, 모든 구역은 정확히 하나의 선거구에 속한다. 또한 하나의 선거구의 모든 구역은 모두 연결되어 있어야 한다. 위 조건을 만족하면서, 기준점 (y, x) 와 경계의 길이 d1, d1가 주어지면, 선거구를 나눠서, 인구가 가장 많은 선거구와 가장 적은 선거구의 차이의 최솟값을 구하는 문제이다, * r행 c열은 (r,c) 로 표현하기 때문에 문제 설명과는 다르게 기준점을 (y,x) 로 표기한다. 2. 문제 풀이 선거구를 나누는 방법은 약간 복잡하다. 기준점을 찾아도, 길이가 의미하는 것을 바로 찾기 어렵다. 그러나, 문제에 나온 방법대로만 하면 경계의 길이가 무.. Algorithm Problem/백준 2022. 9. 6.
[백준] 17298 - 오큰수 1. 문제 이해 하나의 수열이 주어지면, 각 수열의 숫자의 '오큰수' 를 구하는 문제이다. 오큰수란? 자신의 오른쪽에 있는 숫자 중 자신보다 크면서, 그 중 가장 왼쪽에 있는 숫자를 의미한다. 오큰수가 존재하지 않으면 -1 이다. 수열의 크기가 4인 경우, 각 숫자의 오큰수를 순서대로 출력하는 문제이다. 2. 문제 풀이 수열의 크기가 최대 1,000,000 이므로, O(N^2) 의 풀이로 풀 수가 없다. 즉, 최대한 선형 시간 만큼의 시간이 걸리도록 알고리즘을 작성해야 한다. 만약 예제가 [9, 5, 4, 7] 이라면 오큰수는 순서대로 (-1, 8, 8, -1) 이다. 이 때, 숫자5는 자신보다 작은 숫자 4를 알 필요가 없다. 마찬가지로 숫자 9는 숫자 4를 알 필요가 없다. 왜냐하면 이미 5라는 숫자.. Algorithm Problem/백준 2022. 6. 27.
[백준] 1189 - 컴백홈 1. 문제 이해 2차원 배열의 좌측 아래에서 우측 상단으로 한수가 이동하는데, 그 이동경로는 여러가지가 있다. 방문한 곳을 다시 방문하지 않았다고 한다면 이동경로들의 거리는 전부 똑같지는 않을 것이다. 즉, 가장 가까운 거리를 구하는 것이 아닌, 모든 이동경로들의 거리를 구해, K와 거리가 일치하는 수를 구하면 되는 문제이다. 이 때, 거리가 K를 넘어선다면 탐색 할 필요가 없어진다. 2. 문제 풀이 2차원 배열에서 모든 이동경로를 구하는 문제이므로, DFS가 적합하다. DFS에서 2차원 배열을 탐색할 때 마다 현재 좌표의 거리만 계속해서 알고 있다면 문제를 풀 수 있다. DFS를 재귀함수로 구현한다면, 3가지만 잘 체크하면 된다. 재귀함수 기저사례 목적지에 도착하면 탐색할 필요가 없으므로 도착지를 기저.. Algorithm Problem/백준 2022. 6. 25.
[백준] 8972 - 미친 아두이노 1. 문제 이해 2차원 배열 위에 종수의 아두이노 1개와 미친 아두이노 여러개가 있다. 2차원 배열 위에서 게임을 한다. 5가지 과정이 반복된다고 하는데, 3가지 과정으로 요약할 수 있다. 종수의 아두이노가 이동한다. 이 때 이동위치에 미친 아두이노가 있는지 체크한다. 미친 아두이노들을 종수의 아두이노에 가깝게 한 칸 이동시킨다. 이 때, 종수한테 이동했는지 체크한다. 미친 아두이노들이 한 위치에 여러개 있는지 체크한다. 1번과 2번 과정의 경우, 게임을 바로 종료시킬 수 있다. 3번 과정의 경우 미친 아두이노들의 수를 줄일 수 있다. 2차원 배열의 범위가 가로, 세로 각각 100 이하이므로 간단한 구현문제로 생각할 수 있다. 문제에 따로 설명은 없지만, 미친 아두이노들이 순서대로 혹은 동시에 이동하는 .. Algorithm Problem/백준 2022. 6. 24.
[백준] 2174 - 로봇 시뮬레이션 1. 문제 이해 2차원 배열 위에 로봇들의 위치가 입력으로 주어지고, 해당 로봇들에게 명령을 내리는 문제이다. 명령의 종류는 3가지 이며, 중간에 잘못된 명령이 들어 갈 수 있다. 잘못된 명령일 경우 Robot X crashes into the wall: X번 로봇이 벽에 충돌하는 경우이다. 즉, 주어진 땅의 밖으로 벗어나는 경우가 된다. Robot X crashes into robot Y: X번 로봇이 움직이다가 Y번 로봇에 충돌하는 경우이다. 을 출력하고, 잘못된 명령이 없으면 "OK" 를 출력한다. 2. 문제 풀이 2차원 배열의 크기가 가로, 세로 각각 100 이하이며, 로봇들의 수는 100개 이하이다. 명령의 수도 100개 이하이고 각 명령의 반복회수는 100이하이므로 시간 초과를 고려하지 않아도.. Algorithm Problem/백준 2022. 6. 24.

티스토리툴바