![]()
📕문제 https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 🔎문제 풀이 해당 문제는 문제를 읽고 어떤 알고리즘을 사용해서 접근해야 할지 바로 알아야 한다. 친구들의 사탕을 모조리 뺏어버린다 해당 문구를 통해서 유니온 파인드를 통해서 모든 노드의 부모 노드를 설정해야 함을 알 수 있다. 주어진 친구들의 관계를 통해서 묶음으로 친구들을 분류해야 한다. 그리고 얻을 수..
![]()
문제 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 문제 풀이 접근방법에 대해서 정말 난감했던 문제였다. 맨 앞과 뒤로만 접근을 할 수 있다..? -> Dequeue를 써야 해서 옮겨줘야 하나?라고 생각했었다. 하지만 손으로 경우의수를 만들어서 계산을 해보니 이전에 풀었던 문제와 비슷한 느낌이 들었다. https://jja2han.tistory.com/368 [백준 2631] - 줄 세우기(Kotlin)[골드4] 문제 https://www.acmic..
![]()
문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 풀이 시간초과에 많이 좌절했던 문제였다. 배낭문제랑 비슷해서 접근방법은 배낭문제랑 비슷하게 했다. 특이한 점은 가방마다 보석을 하나 담아야 하기 때문에 그 부분을 신경 써줬다. 우선 입력받은 보석을 정렬했다. 우선 무게 순으로 내림차순 정렬했다. 무게가 같다면 보석의 가치로 내림차순 정렬했다. 이유는 단위무게가 높더라도, 가벼..
![]()
문제 https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 문제 풀이 DP 문제로 판단하는 과정은 어렵진 않지만, 어떤 방법으로 풀어야 할지는 아직도 어려운 것 같다. Top-down으로 풀지, Bottom-up으로 풀지, 재귀를 호출할지 등등.. 나는 개인적으로 Bottom-up을선호한다. 해당 문제가 DP인 이유는 이전 선택지에 현재 선택지가 영향을 받기 때문이다. 대부분 나는 이런 문제라고 판단이 되면 DP라고..
![]()
문제 https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 문제 풀이 접근방법에 대해서 많은 고민을 했었다. 시간제한이 1초이고, 이닝의 최대수가 50이며, 순서를 결정해야 하는 타자의 명수는 8명이었다. 그렇다면 시간복잡도는 50*8!*@인데, 시간복잡도가 1초는 안넘길거 같아서 타자의 대한 모든 경우의 수를 계산해도 문제가 되지 않을것이라고 판단했다. 8P3인 이유는 4번 타자는 첫번째 선수로 결정되었기 때문이다. 순열에 대한 코드는 정말 간단하다. ..
![]()
문제 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 문제 풀이 모든 좌표에 대해서 종이를 계속 바꿔가면서 붙이고, 최소한의 종이 개수를 구하면 될 것이라고 판단했다. 이유는 배열의 크기가 그렇게 크지 않다. 10*10이므로 n^2이더라도 넉넉하다고 생각했다. 종이의 종류가 많지 않다. 즉 하나의 좌표에서 종이의 종류대로 붙여가면서 확인을 하더라도 크게 시간이 오래 걸리지 않을 것 같았다. 따라서 나는 종이가 들어갈 수 있는 좌표에 대..
![]()
문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 풀이 나는 문제를 읽고 DP로 접근을 했는데, 다른 풀이를 보니 DFS로 푼 사람들이 꽤 많았다. 개인적으로 DFS보단 BFS를 선호하고, DFS로 풀 생각을 하지 못했어서 DP로 풀었고, 그에 따른 방법을 설명하겠다. 우선 DP로 선택한 이유는 파이프를 놓는 위치가 이전의 선택들에게 영향을 받는다는 점이었다. 즉 (i, j)로 파이프를 놓을 때, 방향에 따라 ..
![]()
문제 https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 문제 풀이 앞선 배열 돌리기 2와 비슷한 문제이다. 거기에선 배열의 원소들을 반시계 방향으로 움직였다면, 이번 문제는 시계방향으로 움직이는 것이다. 그 외에 추가된 것은 연산의 순서를 생각하는 것이다. 회전의 순서에 따라서 배열의 모양이 다르기 때문에 조합이 아닌 순열을 통해서 경우의 수를 산출하고, 회전을 했다. 껍데기의 수는 입력에서 받은 s로 결정하고, r..
![]()
문제 https://www.acmicpc.net/problem/16935 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 문제 풀이 배열 돌리기 2의 상위 문제다. 총 6가지의 연산이 있는데, 1번과 2번은 각각 상하반전과 좌우 반전이다. 1번과 2번은 각각 가운데 행을 기준으로 끝과 끝을 바꿔주면 된다. 3번과 4번은 반시계와 시계방향으로 90도 회전하는 것이다. 여기서 중요한 점은 시계방향으로 한번 돌릴 때마다 N과 M이 바뀐다는 ..
