리콜의 개발로그

문제 링크https://www.acmicpc.net/problem/1780 1. 문제N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다...

문제 링크https://www.acmicpc.net/problem/2448 1. 문제2. 문제 관찰 과정 및 풀이2-1. 문제 관찰 과정아주 불친절한 문제였다. 먼저 주어지는 N은 높이가 된다는 것을 알 수 있었다.또한 넓이는 N의 두배에서 -1을 한 값이 었다. (공백 포함) char 2차원 배열을 만들어서 풀게 되었는데 따라서 배열은 [n][n * 2 -1 ]의 배열이었다. 문제의 예시그림과 같이 3가지 파트로 나누어 그림을 생각하였다.좌표를 생각하는 과정에서 가로가 홀수이다 보니 중간점을 기준으로 생각하는 것이 많이 헷갈렸다. 또한 이전의 별찍기 10과다르게 먼저 채우지 않고 처리하여 조금더 빠르게 해보려 하였다.2-2. 문제 풀이만약 높이가 3이된다면 제일 작은 중간이 비어있는 삼각형을 해당좌표에..

문제 링크https://www.acmicpc.net/problem/2447 1. 문제문제재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.**** ****N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.입력첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k 출력첫째 줄부터 N번째 줄까지 별을 출력한다.2. 문제 관찰 과정 및 풀..

문제 링크https://www.acmicpc.net/problem/13549 1. 문제n과 k가 주어지고 n을 k값으로 만들려고 할때 +1, -1 , *2를 할 수 있을때+1, -1은 cost가 1 들게 되지만*2는 비용이 들지 않는다. 이때 최소 비용으로 k를 만드는 문제였다. N(0 ≤ N ≤ 100,000) K(0 ≤ K ≤ 100,000)2. 문제 관찰 과정 및 풀이 2-1. 문제 관찰 과정최단 거리를 구하는 문제 이기 때문에 bfs를 떠올리게 되었고수만 주어지기 때문에 hashset으로 방문을 했었는지 확인하였다.2-2. 문제 풀이start와 end를 매개 변수로 받는 bfs메서드count를 각 경로마다 카운트하기 위해 node클래스를 만들어서 관리시작하는 노드를 큐에 넣고 방문으로 표시whil..

문제 링크https://www.acmicpc.net/problem/1806 1. 문제문제10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.입력첫째 줄에 N (10 ≤ N 출력첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.예제 입력 1 복사10 155 1 3 5 10 7 4 9 2 8예제 출력 1 복사22. 문제 관찰 과정 및 풀이2-1. 문제 관찰 과정누적합을 이용해서 문제를 풀었다. 다만 left와 right를 관리할때 주어지는 배열이 정렬된 배열도 아닌데 어떻게 나아가야하나 많은 고민을 하였다...

문제 링크https://www.acmicpc.net/problem/1522  1. 문제문제a와 b로만 이루어진 문자열이 주어질 때,  a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오.이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다.예를 들어,  aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다.입력첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 1,000이다.출력첫째 줄에 필요한 교환의 회수의 최솟값을 출력한다.예제 입력 1 복사abababababababa예제 출력 1 복사3예제 입력 2 복사ba예제 출력 2 복사0예제 입력 3 복사aaaabbbbba예제 출력 3 복사0예제 입력 4 복사abab예제 출..

문제 링크https://www.acmicpc.net/problem/4949   1. 문제 문제이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다...

https://www.acmicpc.net/problem/9012 문제괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 ..

https://www.acmicpc.net/problem/2504문제4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.‘()’ 인 괄호열의 값은 2이다.‘[]’ 인 ..

https://www.acmicpc.net/problem/10799 문제여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.이러..