14601번: 샤워실 바닥 깔기 (Large) (acmicpc.net) 14601번: 샤워실 바닥 깔기 (Large) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 7) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net 1. 문제 설명 (1) 오늘은 민규가 훈련소에 입소하는 날이다. 모든 행사를 마치고 생활관으로 돌아와서 쉬려는데 갑자기 교관이 들어오더니 민규의 이름을 부르는 것이 아닌가. 당황한 채로 따라갔더니 이번엔 김준서를 아느냐고 물어보았다. 그 녀석이 샤워실 바닥을 깔았는데, 배수구 위치까지 막아버렸다면서 같은 학교 출신인 민규가 다시 깔라는 것이..

1. 문제 설명 (1) 깊이가 N미터인 우물의 맨 밑바닥에 달팽이가 있다. (2) 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우된다. (3) 날이 맑으면 하루에 2미터를 기어올라갈 수 있지만, 비가 내리면 1미터 밖에 올라가지 못한다. * 날이 맑거나 비가 올 확률은 각각 50%이다. (4) 앞으로 M일 안에 달팽이가 우물 끝까지 올라갈 확률을 찾는 프로그램을 작성하시오. 2. 입출력 조건 및 예제 입력 조건 X 출력 조건 X 입력 예제 3 3 5 3 6 5 8 출력 예제 0.5 0.125 0.5 3. 제약 조건 X 4. 가정법 X 5. 기저 사례 (1) 지정한 날짜 M까지 도달한 경우 6. 코드 public class CLIMB { private static..

( 여기서 먼저 이 알고리즘을 보기전에 아래의 사이트를 먼저 학습하고 보는 것을 추천합니다. ) 삼각형 위의 최대 경로 (난이도: 하) (tistory.com) 삼각형 위의 최대 경로 (난이도: 하) 1. 문제 설명 (1) 아래의 그림과 같이 삼각형으로 배치된 자연수들이 있다고 가정한다. (2) 맨 위의 숫자에서 시작해서, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄까지 닿는 경로를 만들려고 한다. kind-coding.tistory.com 1. 문제 설명 (1) "삼각형 위의 최대 경로"에서는 최대 경로의 합을 구했지 경로 자체는 구하지 않았다. (2) 예를 들어, 아래의 그림 삼각형에는 세 개의 최대 경로 {9, 7, 2, 6}, {9, 7, 3, 5}, {9, 7, 3, 5}가 존재하며 합은 모두 ..

1. 문제 설명 (1) 2xN 크기의 사각형을 2x1 크기의 타일로 채우는 방법의 수를 계산하는 문제가 있다고 하자. (2) 타일들은 서로 겹쳐서는 안 되고 90도로 회전해서 쓸 수 있다. (3) 예를 들어, N=5라고 하면, 아래의 그림과 같이 여덟 가지의 방법이 있다. (4) 이때 N의 최댓 값이 100이라고 할 때 타일을 채우는 방법의 수를 찾는 프로그램을 작성하시오. 2. 입출력 조건 및 예제 입력 조건 (1) 입력의 첫 줄에는 테스트 케이스의 수 C가 주어진다. (2) 그 후 각 줄에 사각형의 너비(1

1. 문제 설명 (1) 양자화(Quantization) 과정은 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. (2) 예를 들면, 16비트 JPG 파일을 4컬러 GIF 파일로 변환하는 것은 RGB 색 공간의 색들을 4컬러 중의 하나로 양자화하는 것이며, 키가 161, 164, 178, 184인 학생 넷을 (160대 두명, 170대 하나, 180대 하나) 라고 축약해 표현하는 것 또한 양자화라고 할 수 있다. (3) 여기서는 1,000 이하의 자연수들로 구성된 수열을 S가지의 자연수만을 사용하도록 양자화하려고 한다. (4) 예를 들어, 수열 1 2 3 4 5 6 7 8 9 10을 두 가지의 숫자만을 써서 표현하려면, 3 3 3 3 3 7 7 7..

1. 문제 설명 (1) 원주율을 몇만 자리까지 외우는 사람들이 존재합니다. (2) 이들은 이 수를 외우기 위해 사용하는 방법 중 하나는 숫자를 몇 자리씩 끊어서 외우는 것입니다. (3) 이때 세 자리에서 다섯자리까지 끊어서 외운다고 하였을 때, 다음과 같은 난이도가 존재합니다. ( ex) 12341234 -> {123}, {41234} 또는 {1234}, {1234} 또는 {12341}, {234} ) 경우 예 난이도 모든 숫자가 같을때 333, 5555 1 숫자가 1씩 단조 증가하거나 단조 감소할 때 23456, 3210 2 두 개의 숫자가 번갈아가며 나타날 때 323, 54545 4 숫자가 등차 수열을 이룰 때 147, 8642 5 이 외의 모든 경우 17912, 331 10 (4) 원주율의 일부가 ..

( 여기서 설명하는 알고리즘은 아래의 사이트에서 LIS를 먼저 선행 후 풀는 것을 추천합니다. ) 최대 증가 부분 수열(난이도: 하) (tistory.com) 최대 증가 부분 수열(난이도: 하) 1. 문제 설명 (1) 부분 순열에 포함된 숫자들이 순 증가(strictly increasing)하면 이 부분 수열을 증가 부분 수열이라고 부른다. * 순 증가란, 두 인접한 숫자 중 앞의 것이 항상 더 작을 때 수열이 순증 kind-coding.tistory.com 1. 문제 설명 (1) 두 개의 정수 수열 A와 B에서 각각 길이 0 이상의 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부른다. * JLIS(Joined Longest Increasing Subsequenc..

1. 문제 설명 (1) 부분 순열에 포함된 숫자들이 순 증가(strictly increasing)하면 이 부분 수열을 증가 부분 수열이라고 부른다. * 순 증가란, 두 인접한 숫자 중 앞의 것이 항상 더 작을 때 수열이 순증가한다고 한다. * 단조 증가(monotonically increasing)란, 두 인접한 숫자가 같은 경우를 말한다. (2) 예를 들어, 수열 S가 '1 3 4 2 4' 라고 하면 '1 2 4'는 S의 증가 부분 수열이지만 '1 4 4'는 아니다. (3) 이때 주어진 수열에서 얻을 수 있는 증가 부분 수열 중 가장 긴 것을 찾는 프로그램을 작성하여라. * 이 문제를 최대 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 부른다. 2. 입출력 조건 ..

1. 문제 설명 (1) 아래의 그림과 같이 삼각형으로 배치된 자연수들이 있다고 가정한다. (2) 맨 위의 숫자에서 시작해서, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄까지 닿는 경로를 만들려고 한다. * 경로는 아래줄로 내려갈 수 있으며 오른쪽과 아래의 숫자로 갈 수 있습니다. (3) 이때 모든 경로 중 숫자의 합을 최대화하는 경로들에 포함된 숫자들의 합은 얼마인지 찾아내는 프로그램을 작성하시오. 2. 입출력 조건 및 예제 입력 조건 (1) 입력의 첫 줄에는 테스트 케이스의 수 C(1

1. 문제 설명 (1) 와일드 카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. (2) 이때 사용하는 문자열을 와일드 카드 패턴이라고 하는데, 패턴은 일반적인 파일명과 비슷하지만 특수 문자 * 또는 ?를 포함할 수 있는 문자열이다. (3) 와일드 카드 패턴을 앞에서 한 글자씩 파일명과 비교해서 모든 글자가 일치했을 때 해당 와일드 카드 패턴이 파일명과 대응된다고 말한다. (4) 와일드 카드 패턴을에 포함된 "?"는 어떤 글자와도 대응된다고 가정하며, "*"는 0 글자 이상의 어떤 문자열에도 대응된가고 가정한다. ( 예시1) 와일드 카드 he?p는 파일명 help와 heap에 대응되지만, helpp에 대응되지 않습니다. ) ( 예시2) 와일드 카드 *p*는 파일명 help와..

1. 문제 설명 (1) 아래의 그림처럼 NxN 크기의 격자에 1부터 9까지의 정수를 쓴 게임판이 있다. (2) 이 게임의 목적은 게임판의 왼쪽 위칸에서 시작해서 게임판의 맨 오른쪽 아래칸 "끝" 쪽으로 도착하는 것이다. (3) 이때 각 칸에 적혀 있는 숫자만큼 아래쪽이나 오른쪽으로 이동할 수 있으며, 중간에 게임판 밖으로 벗어나면 안 된다. (4) 문제는 게임판이 주어질 때 시작점에서 끝점까지 도달하는 방법이 존재하는 지를 확인하는 것이다. (5) 예를 들어, 아래의 그림처럼 위의 그림에서 마지막 2를 3으로 바꾸면 방법이 없다. 2. 입출력 조건 및 예제 입력 조건 (1) 입력의 첫 줄에는 테스트 케이스의 수 C(1

1. 개념 - 동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. - 동적 계획법과 분할 정복의 차이는 문제를 나누는 방식에 있다. - 동적 계획법에서의 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있기 때문에, 이 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있다. - 그렇게 하기 위해서는 이미 계산한 값을 저장해 둘 수 있는 캐시를 사용한다. * 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제(overlapping subproblems)라고 부른다. 2. 이해하기 - 동적 계획법 알고리즘을 이해하기 위해서 가장 유명한 이항 계수(binomial coefficient)의 계산을 예로 들어보겠다. - 이항 계수..

1. 문제 설명 (1) 팬미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 포옹합니다. (2) 아래의 그림은 행사 과정 일부를 보여줍니다. a~c는 세 명의 하이퍼시니어 멤버이고, 0~4는 다섯 명의 팬들입니다. (3) 하지만 하이퍼시니의 남성 멤버들이 남성 팬과 포옹하기가 민망하다고 여겨서, 남성 팬과는 포옹 대신 악수를 합니다. (4) 줄을 선 멤버들과 팬들의 성별이 각각 주어질 때 팬미팅이 진행되는 과정에서 하이퍼시니어의 모든 멤버가 동시에 포옹 하는 일이 몇 번이나 있는지 계산하는 프로그램을 만드시오. 2. 입출력 조건 및 예제 입력 조건 (1) 멤버들의 성별과 팬들의 성별을 각각 나타내는 두 줄의 문자열로 구성한다. (2) M은 남자, F는 여자를 ..

1. 문제 설명 (1) 카라츠바 알고리즘은 정수 두 수를 절반으로 쪼개는 것으로부터 시작됩니다. (2) 다음 문제 설명은 아래의 그림을 보고 이해합니다. ( 이때, 카라츠바는 a x b를 네 개의 조각을 이용해 표현하면 위와 같이 표현할 수 있습니다. ( 이 방법에서는 두 큰 정수를 한 번 곱하는 대신 네 번 곱합니다. ) ( 이때, 10의 거듭제곱은 시프트 연산으로 구현하므로 곰셈으로 치지 않습니다. ) ( 이해를 돕기 위해 아래의 사진을 참고하세요. ) ( 그러나, 위 방법대로 네 번 곱하는 시간 복잡도를 구해보면 결국 O(N^2)이 됩니다. ) ( O(N^2) = 덧셈과 시프트 연산(O(N)) x 2/n길이 조각들의 곱셈 네 번 by 마스터 정리 ) ( 여기서 카라츠바가 발견한 것은 아래와 같이 네..

( 여기서 설명하는 알고리즘은 카라츠바를 쓰기 이전의 알고리즘을 설명합니다. ) ( 그러므로, 분할 정복을 사용하는 카라츠바 알고리즘은 아래의 사이트로 이동하길 바랍니다. ) 카라츠바의 빠른 곱셈 알고리즘(2) - O(N^lg3) (tistory.com) 카라츠바의 빠른 곱셈 알고리즘(2) - O(N^lg3) 1. 문제 설명 (1) 카라츠바 알고리즘은 정수 두 수를 절반으로 쪼개는 것으로부터 시작됩니다. (2) 다음 문제 설명은 아래의 그림을 보고 이해합니다. ( 이때, 카라츠바는 a x b를 네 개의 조각을 이 kind-coding.tistory.com 1. 문제 설명 (1) 카라츠바의 알고리즘은 두 개의 정수를 곱하는 일을 합니다. (2) 32비트 정수 둘을 곱할 때 쓰는 것이 아닌 수백 자리 또는 ..

1. 문제 설명 (1) 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. (2) 시간이 지남에 따라 판자들이 망가져 높이가 다 달라져서 기존의 울타리 일부를 직사각형으로 잘라내 재활용하고 싶습니다. (3) 이때, 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. ( (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. ) ( 단, (c) 처럼 비스듬히 잘래날 수 없습니다. ) 2. 입출력 조건 및 예제 입력 조건 (1) 판자의 수 N(1

1. 문제 설명 (1) 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)가 있습니다. (2) 쿼드 트리는 주어진 공간을 4개로 항상 분할해 재귀적으로 표현하며, (2^N) X (2^N) 크기를 가집니다. (3) 쿼드 트리는 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. - 이 그림의 픽셀이 모두 검은색이라면, 압축 결과는 b가 됩니다. - 이 그림의 픽셀이 모두 흰색이라면, 압축 결과는 w가 됩니다. - 모든 픽셀이 같은 색이 아니라면, 압축 결과는 x가 됩니다. - 이때, x는 하위 자식을 가질 수 있으며 아래와 같이 표현될 수 있습니다. (왼쪽 위 부분의 압축 결과)(오른쪽 위 부분의 압축 결과) (왼쪽 아래 부분의 압축 결과)(..

1. 문제 설명 (1) 크기가 N*N인 행렬 A가 주어진다. 이때, A^B를 구하는 프로그램을 작성한다. 2. 입출력 조건 및 예제 입력 조건 (1) 2

1. 문제 설명 (1) 시계 맞추기 문제는 아래의 보기들을 이용하여 모든 시계들의 방향을 12시로 돌리는 것이다. ➡ ⬆ ⬇ ⬆ ⬆ ⬅ ➡ ⬆ ➡ ⬆ ⬇ ➡ ⬆ ➡ ⬆ ⬇ ( 각 시계들은 3시, 6시, 9시, 12시를 가르키고 있다. ) 스위치 번호 연결된 시계들 0 0,1,2 1 3,7,9,11 2 4,10,14,15 3 0,4,5,6,7 4 6,7,8,10,12 스위치 번호 연결된 시계들 5 0,2,14,15 6 3,14,15 7 4,5,7,14,15 8 1,2,3,4,5 9 3,4,5,9,13 ( 해당 스위치 번호를 누르면 연결된 시계들이 3시간씩 움직이게 된다. ) 2. 입출력 조건 및 예제 입력 조건 (1) 첫 번째 줄에는 문제 개수 C를 입력한다. (2) 두 번째 줄에는 16(4x4)크기만큼 ..

1. 문제 설명 (1) 한 도시를 출발하여 모든 도시를 전부 한 번씩 방문한 뒤 시작 도시로 돌아올려고 한다. (2) 이때 가능한 모든 경로 중 가장 짧은 경로의 길이는 얼마일까? 2. 입출력 조건 및 예제 입력 조건 (1) 첫 번째 줄에는 문제의 개수 C를 입력받는다. (2) 두 번째 줄부터는 도시의 개수 N을 입력받는다. ( 2

1. 문제 설명 (1) 게임판 덮기 문제는 아래와 같은 게임판을 이용하여 삼각형( ┌, ┐, └, ┘)을 가지고 흰색 칸에 빈틈없이 채울 수 있는 최대 경우의 수를 구하는 것이다. ( 이때, 검은색 칸에는 채울 수 없으며 연속으로 이어져 있다. ) 2. 입출력 조건 및 예제 입력 조건 (1) 첫 번째 줄에는 문제 입력 수 C를 입력받는다. (2) 두 번째 줄부터는 게임판의 높이 H와 넓이 W를 입력받는다. ( H>=1과 W

1. 문제 설명 (1) 소풍 문제는 학생들을 두 명씩 짝 지어 목록을 만드는 것이다. ( 단, 항상 서로가 친구인 학생들끼리만 짞을 지어야 한다. ) (2) 최대한 구할 수 있는 모든 경우의 수를 만들어보자. ( 예) (a,b) (c,d) (e,f)와 (a,b) (c,e) (d,f)는 서로 다른 방법이다. ) 2. 입출력 조건 및 예제 입력 조건 (1) 첫 번째 줄에는 총 입력 받을 소풍 문제 개수를 입력받는다. (2) 두 번째 줄부터는 학생의 수 N과 친구의 쌍의 수 M을 입력 받는다. ( N >= 2 && N = 0 && M

1. 문제 설명 (1) 5x5 크기의 알파벳 격자 형태에서 주어진 단어를 찾는 게임이다. (2) 상하 좌우, 대각선 등으로 이어질 수 있으며 한 글자가 두 번 이상 사용 가능하다. 2. 과정 1 2 3 4 5 1 a b c d e 2 f g h i j 3 k l m n o 4 p q r s t 5 u v w x y ( 이때, 찾는 단어 'gmq'라고 가정해보자. 그러면 과정은 다음과 같다. ) 1.처음 1행 1열부터 ~ 5행 5열까지 가로 순으로 첫 단어를 기저 사례로 통해 찾아본다. 2.제일 먼저 발견되는 알파벳은 'g'이며, 'm'에 대해서 주변 인접한 단어를 재귀 호출로 찾아본다. 3.재귀 호출 과정에서 오른쪽 아래 대각선 'm'을 찾았고 다시 주변 인접한 단어를 재귀 호출로 찾아본다. 4.재귀 호..

1. 문제 설명 (1) N개의 정수들 중에 M개를 고르는 (중복을 허용하는) 순열을 구하시요. --> permDup() 메서드로 구현하여라. (2) N개의 정수들 중에 M개를 고르는 (중복을 허용하지 않는) 순열을 구하시오. --> permNotDup() 메서드로 구현하여라. (3) N개의 정수들 중에 M개를 고르는 조합을 구하시오. --> combi() 메서드로 구현하여라. 2. 풀이 및 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 6..

1. 문제 설명 (1) 분수 a/b가 주어질 때 실수 연산을 쓰지 않고 이 분수를 소수 형태로 출력한다. (2) 예를 들면, 3/8은 0인데 0.375를 출력하고 4712/400은 11인데 11.78을 출력하는 것이다. 2. 입출력 조건 및 예제 입력 조건 (1) a>=0, b>0으로 가정한다. 출력 조건 X 입력 예제 2 3 8 4712 400 출력 예제 0.375 11.78 3. 제약 조건 X 4. 가정법 X 5. 기저 사례 X 6. 코드 public class Main { private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in)); private static StringTokenizer st; priv..

0. 응용한 기술 - 데이터베이스 또는 다른 데이터 경로로 받은 데이터를 배열로 저장했다고 가정하고 고객 정보 보여주기. - 카드뷰를 설정하여 레이아웃을 설정하기. 1. 구현해야 할 것 ( 아래는 앱이 실행하는 장면이다. ) 2. 제약조건 - 왼쪽에서 오른쪽으로 넘어가는 애니메이션 만들어보기. - 최소 3개 이상 아이템 만들어보기. 3. 소스코드 - 아래의 사이트에 있는 Mission17 파일을 다운하여 열기. AndroidStudio-Study/Basic-Concept/Version8/Lab2/Mission/Mission17 at master · dlgmldnd017/AndroidStudio-Study (github.com) 4. 배운 점 - 애니메이션이 적용된 뷰는 setVisibility()가 먹히..

0. 응용한 기술 1. 구현해야 할 것 2. 제약조건 3. 소스코드 4. 개선해야 할 점

0. 오류 메시지 - You need to use a Theme.AppCompat theme (or descendant) with this activity. 1. 원인 & 분석 원인 - 아래의 AlerDialog.Builder() 생성자 초기화에서 getAplicationContext()를 사용했다. - 오류 메시지로 보았을 때는 생성자 초기화로 어떤 액티비티에서 띄워주어야 할 지 없다고 판단하여 비정상적으로 종료되었다. 분석 - getApplicationContext()는 어플리케이션 자체 객체이므로 생성자로써 적절하지 않다. 2. 해결방법 - 해당 액티비티 객체를 전달해야 하므로, 생성자 초기화에 'this' or '해당액티비티.this' 를 넣어준다.

0. 응용한 기술 - 간격 1행 1열로 화면 넓이 만큼 카드뷰 늘려주거나 줄여주기. - 길게 눌렀을 경우 삭제하는 AlertDialog 구현하기. 1. 구현해야 할 것 ( 아래는 휴대폰 화면 크기만큼 카드뷰 늘려주는 사진이다. ) ( 각각 넓이가 다른 폴드3의 외부 화면과 내부 화면을 보여준다. ) ( 아래는 추가와 어댑터를 길게 눌러 삭제하는 장면 그리고 중복된 경우 Toast로 알려주는 장면이다. ) 2. 제약조건 - 딱히 없음. 3. 소스코드 - 아래의 사이트에 있는 Test002 파일을 참고. AndroidStudio-Study/Basic-Concept/Version8/Lab2/Test/Test002 at master · dlgmldnd017/AndroidStudio-Study · GitHub 4..

0. 응용한 기술 - 이미지 또한 api를 가져와서 영화 이미지를 구현해본다. ( 여기서는 대충 아무 인터넷에 있는 자료를 가져와본다. ) 1. 구현해야 할 것 2. 제약조건 - api 주소는 아래에 있는 사이트 주소로 이용한다. http://kobis.or.kr/kobisopenapi/webservice/rest/boxoffice/searchDailyBoxOfficeList.json?key=f5eef3421c602c6cb7ea224104795888&targetDt=20120101 3. java 소스코드 ( 아래는 MainActivity.java의 코드이다. ) import androidx.appcompat.app.AppCompatActivity; import androidx.recyclerview.wi..