투투

문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증..

programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 접근 탐욕법 알고리즘에 분류된 문제이다. 그래서 어떠한 기준으로 매번 최적을 선택할지 고민을 했다. 먼저 정렬을 했는데 진입한 시점을 기준으로 오름차순으로 정렬을 하였다. 이후 규칙을 찾아보려고 했고 나가는시점을 기준으로 오름차순 정렬도 해보았다. 나가는시점을 기준으로 정렬했을 때 나가는 시간을 기준으로 카메라를 설치하고자 하였다. 즉, 정렬 후에는 첫 번째 오는 시간은 가장 빨리 나가는 차량이기때문에 해당 차량이 나가는 시점에 카메라를 설치한다. 이후 설치한 카메라의 시점을 통해..

programmers.co.kr/learn/courses/30/lessons/12951 코딩테스트 연습 - JadenCase 문자열 만들기 JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건 programmers.co.kr 접근 공백다음의 글자는 대문자로 만들고 나머지는 소문자로 만들어서 answer에 추가한다. 구현 첫 번째 인덱스가 영문이라면 대문자로 만들어 answer에 추가한다. 첫 번째 인덱스 이외에는 이전의 문자가 공백일 때 현재문자를 대문자로 만들어 추가하고 아닌 것은 모두 소문자로 만들어 추가한다. def solution(..

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 접근 4, 2가 입력될 때 (1, 1), (2, 2) 등도 출력되어야 하기 때문에 DFS로 M개의 수..

문제 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다. 출력 첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다. 접근..

www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 접근 n에 따라 규칙을 찾고 점화식을 세우려했다. 왜냐하면 크기가 n개일 때는 n-1개에서 특정 크기가 추가되고 n-2개에서도 추가되어 만들어진 것이기 때문이다. 그래서 점화식을 세운다면 f(n) = f(n-1) + 2xf(n-2)가 된다. 구현 n이 최대 1000개가 들어오기 때문에 0으로 초기화된 길이 1000인 리스트를 생성하고 n=1일 때는 1개, n=2일 때는 3개로 설정해두며 for문을 통해 입력된 n개일 때를 구한다. impor..

programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 접근 시간초과가 날 것 같았지만 백트래킹으로 시도를 해보았다. 역시 시간초과가 발생했다. 그래서 1칸, 2칸까지 뛸 수 있다는 것에 동적계획법이 생각이 났고 점화식을 세우려고 했다. 경우의 수를 봤을 때 f(n) = f(n-1) + f(n-2)라는 점화식을 세울 수 있었고 그대로 구현을 하였다. 구현 n은 1이상 200..

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 접근 BFS 탐색을 통해 현재위치에서 갈 수 있는 곳을 방문하면서 K..

문제 N!에서 뒤에서부터 봤을 때 0이 아닌 수가 나올 때까지 0의 개수를 구하라. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 접근 팩토리얼을 구하고 리스트로 변경한 후에 뒤에서부터 0의 개수를 카운트한다. 구현 먼저 반복문을 통해 팩토리얼을 구하여 total에 저장한다. 이후 total을 리스트로 변환하여 각 인덱스에 숫자가 차례대로 위치하도록 한다. 이후 reversed()를 통해 리스트를 뒤집은 후 원소를 꺼내어 0이 나올 때까지 카운트한다. N = int(input()) total = 1 for n in range(1, N+1): total *= n total = list(map(int, str(total))) answer = 0 for ..

programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 접근 처음에 완전탐색으로 풀었지만 시간초과가 발생했다. 이후에 다른 사람들의 풀이를 보고 DP로 접근하는 것을 알았다. 하지만 어떻게 DP로 풀어야할지 감이 잡히지 않았다. 내가 이해한 방식은 다음과 같다. (y, x) 좌표를 기준으로 2x2 크기의 윈도우로 정사각형를 찾아서 크기를 저장해두는 것이다. 1, 1부터 시작을 하여 1이상인 좌표에 대해 왼쪽, 위, 좌상단을 검사하여 최솟값을 찾는다. 만약 이 범위 내에 0이 있다면 정사각형이 아니다. 정사각형이라면 1이상..