네발로 코딩하는 포메라니안

문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 과정 왼쪽, 왼쪽의 대각선, 위쪽에서 제일 작은 정사각형 크기 + 1이 현재 노드에서의 정사각형의 크기로 한다. 자신보다 아래에 위치한 1들은 나중에 고려하므로 생각하지 않는다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args)..

문제 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 과정 dp[i] = (dp[i-1][x] + dp[i-1][1] + dp[i-1][2]) + (dp[i-1][x] + dp[i-1][2]) + (dp[i-1][x] + dp[i-1][1]) = dp[i-1]*2 + dp[i-1][x] = dp[i-1]*2 + dp[i-2] import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception..

문제 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 과정 처음엔, 3방향 다 Math.max로 고려해줬었다. 하지만, 최단 거리가 아니기 때문에, 대각선에서 오는 것보다 위 혹은 왼쪽을 거쳐 오는 것이 총 사탕 개수가 같거나 큰 경로이므로 대각선은 고려하지 않는 것이 효율적이다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util..

문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 과정 BFS를 떠올리기는 쉬웠는데 K까지 도달하는 개수를 어떻게 셀 지에 대해서 생각하기가 어려웠다. 방문체크를 q에서 꺼낼 때함으로써, 현재 step에서는 중복을 허용하되 다음 step에서는 이전에 방문한 것을 제외하고 방문하도록 할 수 있었다. import java.io.BufferedReader; import java.io.InputStream..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 1. BFS 탐색으로 퍼즐(remove를 쓰기 위해 LinkedList를 사용)과 빈 칸을 각각 분석한다. 1-1. 블럭의 가장 위쪽에서 가장 왼쪽에 있는 블럭을 (0, 0)으로 맞추어 블럭들의 좌표를 변경한다. - setCenter메서드 2. 각 빈칸에 퍼즐을 넣을 수 있는 지 검사한다. 2-1. 개수가 다르면 return false; 2-2. 개수가 같으면 회전시켜가면서 넣을 ..

문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 과정 처음에, 어차피 왼쪽에서 오른쪽, 위에서 아래로만 움직일 수 있기 때문에 2중 반복문으로 풀 수 있을 것 같았다. 하지만, 방향까지 고려해야 돼서 생각하다가 DFS로 풀었다. 다 풀고나서, 고민하다가 방향마다 따라 결과를 저장해가면 2중 반복문으로 풀 수 있을 것 같아서 다시 풀었다. 결과적으로 속도가 2배 향상되었다. 이전 코드 : DFS import j..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 우선 순위가 1~9까지 있고, 문서가 1~100까지이다. 따라서 문서를 우선순위에 따라 정렬하지 않고, int 1차원 배열에 각 우선 순위가 몇 개 있는지 표시하였다. 그리고나서 우선순위를 9부터 1까지 차례로 탐색하면서, 해당 우선순위를 가진 문서가 1개 이상이면 queue에서 찾도록 했다. import java.util.*; class Solution { public int s..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 처음엔 AEIOU 순서대로 DFS방식을 통해 사전순대로 읽어가면서 해당 문자열을 만나면 return하는 방식이 떠올랐다. 그런데, 굳이 순서대로 다 탐색하는 것보다 몇 번째인지 바로 계산할 수 있는 방식이 있어서 이 방식으로 구현했다. 원래는 O(N)만큼 걸리는 알고리즘을 O(1)으로 구현할 수 있는 것이다. 수식 : 5^(length("AEIOU")-1-i) + sum(1*5^(..

문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이과정 각 번호별로 먹은 횟수를 1차원 배열에 기록했다. 여기서 인덱스는 음식의 번호를 의미한다. 이 문제에서는 K개라는 window크기가 정해져있으므로 window를 한칸씩 오른쪽으로 움직여가며 값을 계산했다. window가 옮겨질 때는 window맨 첫번째 수를 빼주고 다음 수를 하나 더해주는 방식으로 진행한다. import java.io.Buff..

문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 과정 대각선 위, 중간, 대각선 아래 순서대로 탐색해서 최대로 설치할 수 있는 개수를 구할 수 있다. 이때, 한 노드에서 갈 수 있는 경로를 모두 탐색했을 때 못가는 경로로 판단날 경우 다시 가볼 필요가 없기 때문에 방문한 모든 노드는 'x'처리한다. 또한, 갈 수 있는 경로는 이제 사용한 경로로 취급되어 다음 경로는 여기를 지나칠 수 없으므로 'x'처리하기 때문에 결과적으로 방문한 모든 노드를 'x'..