개발저장소

문제 https://www.acmicpc.net/problem/2567 2567번: 색종이 - 2 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변 www.acmicpc.net 풀이 가로, 세로 길이가 100인 도화지 위에 길이가 10인 정사각형 색종이를 도화지와 평행하게 붙인다. 이러한 방식으로 색종이를 여러장 붙였을 때, 둘레의 길이를 구한다. 중간에 구멍이 뚫린 모양도 둘레에 포함한다. 수학적인 방법으로 접근하려고 했지만 중간에 둘레가 생기는 경우를 계산하기 위해서 그리디한 방법으로 접근하였다. 도화지를 크기가 100 X 100인 2차원 배열로 생각한다. 이때 배..

문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 풀이 N개의 수열과 L이 주어진다. 수열의 연속된 숫자 L개 중에서 최솟값을 D라고 할 때, 최솟값들을 구해야 한다. 예를 들어 5개의 수열 1, 2, 3, 4, 5와 L = 3가 주어질 때, (1, 2, 3), (2, 3, 4), (3, 4, 5) 중에 최솟값을 구해서 출력해야 한다. ( 1 2 3 이런식으로) N과 L의 범위가 1 이상 5,000,000 이..

문제 https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 풀이 문자열에 ‘A’, ‘C’, ‘G’, ‘T' 만 등장하는 문자열을 DNA 문자열이라고 한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 길이 S의 임의의 DNA 문자열을 만들고, 이 DNA 문자열의 길이가 P인 부분문자열을 비밀번호로 사용하려고 한다. "AAAA" 같은 취약한 비밀번호가 만들어 질 수도 있기 때문에 문자의 개..

문제 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 N개의 수가 주어질 때, 어떤 수가 다른 두 수의 합으로 나타낼 수 있다면 "좋다"라고 한다. 주어진 N개의 수 중 좋은 수의 개수를 출력해야 한다. 같은 값의 수가 주어질 수도 있지만 서로 다른 수로 취급한다. N은 1에서 2000 사이이고, 주어지는 수는 |Ai| ≤ 1,000,000,000 의 정수이다. 투포인터를 사용해 N개의 수를 탐색하는 방법으로 풀었다. 이때, 수의 범위가 크므로 Long형 배열로 입력..

문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 N개의 수열이 주어졌을 때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구한다. Ai + ... + Aj 가 M으로 나누어 떨어지는 순서쌍 (i, j)를 구해야 한다. Si % M과 Sj % M의 값이 같다면 (Si - Sj) % M = 0이 되는 성질을 이용해야 한다. 누적 합을 가장한 모듈러 산술에 대한 문제이다. ..

문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 자연수 N을 제곱수의 합으로 표현해야 한다. 예를 들어 5 = 1^2 + 2^2, 즉 2개의 항으로 나타낼 수 있다. 이때 N을 제곱수의 합으로 나타낼 때, 최소 항의 개수를 구한다. 모든 자연수 N의 최대 항의 개수는 N개이다. 1^2의 합으로 표현할 수 있기 때문이다. 제곱수 N의 최소 항의 개수는 무조건 1개이다. 제곱해서 N이 되는 수 하나..

문제 https://www.acmicpc.net/problem/2628 2628번: 종이자르기 첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 www.acmicpc.net 풀이 직사각형 모양의 모눈종이가 있다. 1cm마다 점선으로 표시되어 있고, 각 점선에는 순서대로 번호가 부여되어 있다. 직사각형의 가로와 세로의 길이, 그리고 잘라야하는 점선이 주어질 때, 가장 큰 종이 조각의 넓이를 구해야 한다. 가로로 잘라야 하는 점선과 세로로 잘라야 하는 점선을 각각 ArrayList로 입력 받은 다음 순서대로 정렬해서 문제를 해결하였다. 길이를 구해야하므로 처음과 끝도 A..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12952 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 N x N 체스판 위에 퀸을 N개 놓는 경우의 수를 구한다. 이때, 퀸은 서로를 공격할 수 없는 위치에 두어야 한다. 퀸은 가로, 세로, 대각선으로 거리에 상관없이 움직일 수 있는 말이다. N은 12 이하의 자연수이다. 대표적인 백트래킹 문제라고 한다. 이때, 조건은 해당 위치에 퀸을 놓을 수 있는가가 된다. 체스판이기 때문에 2차원 배열을 사용해야 할 것 같지만 하나의 행 또는 열에는..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전화번호부에 적힌 번호 중, 한 번호가 다른 번호의 접두어인 경우를 확인한다. 접두어란, 어떤 단어의 앞에 붙어 뜻을 첨가하거나 다른 단어를 이루는 말이라고 한다. 즉, 01012345678의 접두어는 01, 010, 0101 등이 될 수 있는 것이다. 전화번호부의 번호는 모두 다르다. 전화번호부에 중복된 번호는 없다는 특징을 보아, HashMap을 사용하기 적..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/92341 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 주차장에 출입하는 차량 기록이 주어졌을 때, 주차 요금을 구하는 문제이다. 입출차 기록은 시각, 차량 번호, 입출 내역으로 이루어져 있으며 모두 문자열로 주어진다. 입차 후 출차 기록이 없다면 23시 59분에 출차한 것으로 계산한다. 요금표는 기본 시간과 요금, 추가 단위 시간과 요금으로 이루어져 있으며 int형 배열로 주어진다. 차량 번호가 작은 자동차부터 순서대로 주차 요금을 출력한..