![]()
문제 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 문제를 풀다가 어려워서 알고리즘 분류를 봤고, 비트마스킹이 적혀있었다. 저번에 풀었던 외판원 순회라는 문제도 비트마스킹을 사용했고, 비트마스킹을 통해서 도시의 방문처리를 했던 것을 토대로, 숫자들을 사용했는지, 안했는지를 비트마스킹을 통해서 해결했다. 우리는 0~9까지의 숫자를 반드시 하나 이상 사용해야 한다. 이러한 정보를 비트마스킹으로 저장을 한다는 얘기이다. 예를 들어 숫자가 1일경우 visit -> visit | 1 visit | 2방문현황, k->마지막 숫자 즉 DP [1][visit][1] =..
![]()
문제 https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 문제 풀이 본론부터 말하면 해당 문제는 LIS 알고리즘을 활용하는 문제이다. 왜 그렇게 생각했느냐에 대해서 얘기해볼까 한다. 우리의 목표는 A와 B를 연결하는 전깃줄이 교차하지 않게 하면서, 최소한의 전깃줄을 제거해야 한다. 그러면 전깃줄이 교차하는 경우는 무엇일까? A의 1번은 B의 8번과 연결되어 있고, A의 2번은 B의 2번과 연결되어 있다. A의 1번 전깃줄을 연결한 상태에서 A의..
![]()
문제 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 풀이 가장 긴 증가하는 부분 수열 문제는 알고리즘의 명칭이 있을 정도로 유명한 문제이다. DP를 이용해서 그 수열의 길이를 구한 문제는 풀어본 적이 있지만, 수열의 길이와 그 수열을 구해야 하는 문제는 따져줘야할것이 많기 때문에 DP로 풀면 안 될 거 같은 느낌이 왔다. 기존의 LIS 문제는 N의 크기가 크지 않아서 N^2 알고리즘으로 DP 배열을 계속 업..
![]()
문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제 풀이 문제를 꼼꼼히 잘 읽고 흐름을 파악해서 코드를 작성하면 어려운 문제는 아니라고 생각한다. 문제를 풀기 위해 생각해야 할 점은 다음과 같다. 낚시가 진행되는 순서(낚시왕 이동, 상어 잡기, 상어 이동) 상어를 움직이는 로직 같은 칸에 있는 상어 처리하기 이렇게 크게 3개라고 생각한다. 상어를 움직이는 로직은 다양하게 구현할 수 있다. 낚시가 진행되는 순서 낚시가 ..
![]()
문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 풀이 알고리즘 자체는 정말 간단하지만 그 내부 구현이 조금은 복잡했던 문제였다. N의 크기가 크지 않고, 이동할 수 있는 방향의 개수가 적어서 충분히 완전탐색으로 풀 수 있을 것이라고 판단을 했다. 하지만 고민은 하나의 배열로 풀 수 있을까였다. 퍼즐을 밀고, 해당 탐색을 마친다면 이전의 퍼즐 배열로 돌아와야하는데 하나의 배열을 이용하면 풀 수 없을 것이라고..
![]()
문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 문제 풀이 시간초과 때문에 정말 고생했던 문제였다. 문제에서 요구한 대로 벽을 부수고, 벽을 부순 시점에서 이동할 수 있는 경로의 수를 구하는 문제이다. 정말 당연하게도 벽인 곳을 큐에 넣어서 BFS를 진행했다. while(!q.isEmpty()) { Queue child = new LinkedList(); Point cur = q.poll(); child.add(cur..
![]()
문제 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제 풀이 팰린드롬 시리즈는 유명한 문제이다. 팰린드롬에 대해서 간단하게 설명하자면 가운데를 기준으로 일치하는 문자열을 의미한다. 예를 들어서 ABA라는 문자열이 팰린드롬에 해당한다. 그 외에도 문자열의 길이가 1인 문자열도 팰린드롬에 해당한다. 해당 문제를 풀기 전에 팰린드롬에 개념을 알고 문제를 진행하면 풀기 수월하다. ..
![]()
📕문제 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..
