레벨업 일지

문제 18222번: 투에-모스 문자열 (acmicpc.net) 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 풀이 반복되는 조건을 어떻게 처리할지가 관건인 문제 문제 조건을 다시 확인해 보자 X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 X'를 붙인 문자열을 X로 다시 정의한다. 2~3의 과정을 무한히 반복한다. 문자열 최대 길이 10^18를 일일히 확인하려면 TLE 가 뜬다. 따라서 반복되는 조건을 이용하여 찾아야 한..

문제 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 . 현재 기호가 ) ..

문제 https://www.acmicpc.net/problem/5464 5464번: 주차장 시내 주차장은 1부터 N까지 번호가 매겨진 N개의 주차 공간을 가지고 있다. 이 주차장은 매일 아침 모든 주차 공간이 비어 있는 상태에서 영업을 시작하며, 하룻동안 다음과 같은 방식으로 운영 www.acmicpc.net 풀이 내가 생각한 문제에서 요구사항은 다음과 같다. 주어진 조건대로 waiting Q를 구현하고싶은데 우선순위를 수정할줄 아느냐? 구현 문제를 풀때, 의미가 있는 변수 이름으로 설정해주면 내 코드를 보더라도 헷갈리지 않고 풀이할수 있다. 주석을 사용하는 대신 변수 네이밍으로 뜻만 보더라도 알아볼 수 있게 하였다. 풀이 알고리즘은 다음과 같다. 현재 차가 들어올 타임일때 현재 대기 번호 뽑은 차량이 ..

문제 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/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 알아야 할 개념 독해력 DFS 구현 풀이 나의 부족한 문제 이해력으로 문제의 예외 캐이스를 미쳐 생각 못해 머리를 싸메다 백준 질문 게시판에서 힌트를 얻었다. dfs구현은 어렵지 않았지만 예외 케이스가 존재하였다. 바로 빙산이 한번에 녹아 버리는 경우이다. 문제를 다시 보자 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성..