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

문제 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 풀이 과정 가장 왼쪽, 위쪽에서 출발해서 일반 블럭일 때만 DFS 탐색을 하면, 일반블럭이 무조건 1개 이상인 조건을 만족한다. 탐색 후, (블럭 사이즈가 최대) || (이전 블럭 사이즈와 같고 rainbow블럭의 개수가 같거나 큼)일 때, 가장 큰 블럭 값을 갱신해준다. 가장 큰 블럭은 삭제하면서 -2로 표시한다. import java.io.BufferedReader; import ja..

문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 과정 입력된 수를 최대힙과 최소힙에 나눠 저장해서 중간 값이 최대힙의 top에 있도록 했다. 최대힙은 값을 넣을 때, 음수로 넣어서 최소힙을 활용한 최대힙을 만들었다. 최대힙의 크기 >= 최소힙의 크기로 밸런스를 맞춰서 최대힙.peek()를 출력해주면 된다. 1. mid값보다 크면, 최소힙에 삽입 1-1. 최소힙의 크기 > 최대힙의 크기면, 최대힙.offer(최소힙.po..

문제 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^(..