레벨업 일지

문제 1074번: Z (acmicpc.net) 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 풀이 반복문으로 구현하였다. 풀이는 다음과 같다. 현재 size를 기준으로 (x,y) 가 몇 사분면에 위치하는지 체크한다. 정답 변수에 (사분면 * ( size/2 ) * (size/2) ) 을 누적합한다. 더 작은 단위로 쪼개기 위해 현재 (행, 열)에 모듈러 연산을 적용한다. 정답 변수를 출력한다. 코드 import java.io.*; import java.lang.reflect.Array; import..

문제 17829번: 222-풀링 (acmicpc.net) 17829번: 222-풀링 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 22 www.acmicpc.net 재귀를 사용해서 문제 풀이를 구현할 줄 아는지 묻는 문제. 풀이 이미지 압축일종인 CNN 풀링중 222-풀링은 4 개의 원소 중 2번째로 큰 원소를 찾는다. stride 기법으로 , 배열 원소 4개씩 살펴 본 뒤, 2번째로 큰 원소를 k번째 칸에 삽입한다. 풀이는 다음과 같다. 현재 size 를 파라미터로 담아 재귀 호출을 한다. 1이 되면 종료한다. 각 단계마다 4개의..

문제 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 풀이 조금 시간이 걸렸던 구현 문제 문제 요구사항은 다음과 같다. 주어진 배열의 순서를 바꾸는데 구현만 하면 되고, 최적화는 필요없다. 따라서 N번 연산의 요구사항에 맞추어 구현했다. 1번 연산의 구현 코드이다. public void upAndDownFlip(int[][] m){ int r, c,t; r = m.le..

문제 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 풀이 문제가 '(' 와 ')' 기호 의 콤비내이션으로 이루어져있어 스택 알고리즘 으로 접근하는게 편하다 생각들었다. 문제를 해석하면 () 는 레이저 광선을 의미하고 (( .. )) 처럼 열림-닫힘 쌍이 아닌 것들은 쇠 막대기이다. 따라서 레이저가 한번 지잉 하면, 쇠막대기 개수만큼 정답 변수에 누적합을 하면 된다. 풀이 알고리즘은 다음과 같다. 현재 기호가 ( 이면 stack +1 . 현재 기호가 ) ..

문제 1992번: 쿼드트리 (acmicpc.net) 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 풀이 알고리즘은 다음과 같다. 주어진 크기 N에서 2중for 탐색으로 배열을 모두 1 인지 0 인지 검사를 한다. 모두 1이거나 0 이면 1 또는 0 을 출력한다. 그렇지 않으면, 재귀 탐색으로 subarray를 탐색을 구현한다. 코드 import java.io.*; import java.util.*; public class Main { int m[][]; int ans; int theta; ..

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 알아야 할 개념 2차원 배열 BFS 탐색 풀이 주어진 조건에 따라 bfs 시뮬레이션을 구현하는 문제. 풀이 알고리즘은 다음과 같다. 현재 위치에서 bfs 탐색을 하며 currentSIze 보다 작은 상어들을 priorityQueue에 추가한다. priorityQueue 가 비어 있지 않은 경우 하나 꺼내서 잡아먹는다. 시간, 상어 사이즈 갱신한다. 지금까지의 PriorytyQueue와..

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 특별한 조건 없는 일반적인 2차원 배열 탐색 문제 풀이 풀이 알고리즘은 다음과 같다. 적록색약이 있으면 if문으로 1 또는 2 에 해당하는지 검사하면서 dfs한다. 색약이 없는 경우 dfs 하면서 메소드 부른 횟수를 카운팅 한다. 정답을 리턴한다. 코드 package solve; import java.io.*; import java.util.*; public class Main { i..

문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 알아야 할 개념 모듈러 연산 특징 prefix sum 풀이 처음에 O( n logn ) 인 세그먼트 트리를 만들어서 접근하려고 했는데 역시나 O(N^2) 로 걸렸다. 이 문제의 키 포인트는 모듈러 연산의 분배법칙이다.. 분배법칙 (a + b ) % m == a % m + b % m 풀이과정은 다음과 같다. prefix sum 배열을 만든다.(누..