문제풀이

[문제] https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net [풀이] 약간.. 구현문제에 DFS 살짝 추가한 정도의 문제 같다. 그냥 7가지 경우의 수에 따라 파이프의 한쪽 끝이 원하는 위치에 도달할 때까지 깊이 우선 탐색을 진행한다. 아래 5가지에 유의하면서 풀었다. 1. 파이프 끝점을 기준으로 한다. 2. 파이프 주위 꼭 빈칸이어야 하는 곳에 벽이 있을 경우 파이프를 이동할 수 없다. 3. 파이프가 가로일 경우, 가로로..

[문제] https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net [풀이] 민식이의 최소 이동 횟수를 구해야 하기 때문에 BFS 문제라고 유추할 수 있다. 하지만 일반 BFS 문제와는 다른 점이 크게 두 가지 있는데 1. 열쇠 정보값에 따라 방문할 수 있는 미로가 다르기 때문에 획득하는 열쇠 값을 저장해야 한다. 2. 다른 BFS 문제와는 달리 이미 방문했던 곳을 다시 방문해야 되는 경우가 발생한다. 📌 열쇠 정보 저장하기..

[문제] https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net [풀이] 문제에서 중요한 조건은 1. 초기 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 2. if (아기 상어 크기 ≥ 물고기 크기) 아기 상어가 지나갈 수 있다. 3. if (아기 상어 크기 > 물고기 크기) 아기 상어가 물고기를 먹을 수 있다. 4. 먹을 수 있는 물고기가 1마리라면 그 물고기를 먹으러 가고, 5. 먹을 수 있는 물고기가..

[문제] 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 [풀이] [Java] BOJ/백준 12738번 가장 긴 증가하는 부분 수열 3 [문제] https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,00..

[문제] https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net [풀이] [Java] BOJ/백준 11053번 가장 긴 증가하는 부분 수열 [문제] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {..

[문제] https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net [풀이] [Java] BOJ/백준 12015번 가장 긴 증가하는 부분 수열 2 [문제] https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,0 ..

[문제] https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net [풀이] [Java] BOJ/백준 11053번 가장 긴 증가하는 부분 수열 [문제] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, chaewsscode.tistory.com 해당..

[문제] https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net [풀이] 📌 최장 증가 부분 수열(LIS: Longest Increasing Subsequence) 알고리즘 원소가 n개인 배열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 일반적으로 LIS의 길이를 ..

[문제] https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net [풀이] 이 문제는 1) 사이클이 발생하는 구간을 구할 수 있는지, 2) 그래프 탐색으로 최단 거리를 구할 수 있는지 를 판단하는 문제이다. 따라서 아래와 같은 순서로 문제를 풀었다. 1. DFS 탐색을 통해 사이클이 발생하는 구간을 체크한다. 2. BFS 탐색을 통해 모든 노드에서 사이클이 발생하는 노드까지의 최단 거리를 계산한다. 1️⃣ 사이클 발생 구간 체..