투투

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이상..

programmers.co.kr/learn/courses/30/lessons/68645 코딩테스트 연습 - 삼각 달팽이 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] programmers.co.kr 접근 이 문제처럼 어떠한 규칙에 의해 수들이 정렬되어 있을 때 방향이 어떠한 규칙으로 반복되는지, 인덱스는 어떻게 변하는지 등을 생각해볼 필요가 있다. 이 문제는 아래, 오른쪽, 위 방향이 반복되어지고 있다. 그리고 방향이 바뀔 때마다 포함된 숫자들이 하나씩 감소하고 있다. 이 부분을 신경써서 구현을 해보자. 구현 NxN 크기의 그래프를 생성하여 0으로 초기화하였다. 이 그래프에 숫..

www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 접근 분할정복이 이해가 되지않아 문제를 풀어보면서 이해하고자 했다. 분할정복은 큰 문제를 풀기보다 작은 문제들로 나누고 작은 문제부터 해결해나가는 것이라고 이해했다. 그래서 이 문제에서 어떻게 분할할지를 신경썼다. 다른 사람들의 풀이를 참고하였는데 입력예시처럼 8x8 크기의 맵이 들어온다고 해보자. 8x8의 크기를 4x4의 크기로 나눠 네 개의 맵을 만든다. 그리고 다시 4x4를 2x..

문제 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다. 입력의 마지막에는 0이 주어진다. 출력 각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다. 접근 에라토스테네스의 체로 123456x2까지의 소수를 구하여 N을 입력할 때마다 범위 내의 소..

문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 접근 앞으로 n이 소수인지 판단을 할 때 2부터 n의 제곱근까지 검사를 하도록 하자. 왜냐하면 n의 약수는 n/2보다 크지 않기 때문이다. 구현 소수를 판별하는 함수인 is_prime()에서 전달받은 숫자의 제곱근까지 검사하여 소수를 판별하였다. def is_prime(number): if number == 1: return False for i in range(2, int(number**0.5)+1): if numb..

문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 접근 소인수분해는 합성수를 소수의 곱으로 나타내는 것이다. 그래서 정수 N이 주어졌을 때 2부터 계속 나눠간다. 이후 2로 나누어 떨어지지 않는다면 수를 증가시켜 3으로 나눈다. 3으로 나누어 떨어지지 않는다면 4로 나누지만 이전에 2로 모두 나눴기 때문에 4로 나누어 떨어지지 않을 것이며 바로 5로 갈것이다. 이러한 원리로 N이 1이 될 때까지 반복한다. 구현 입력받은 N을 n으로 계속 나눠주며 나누어 떨어지지 않을 때 n을 증가시킨다. N = int(..

문제 M과 N사이의 소수를 찾아 소수들의 합과 소수들 중 최솟값을 출력한다. 입력 입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다. 출력 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. 구현 M부터 N까지 탐색하여 1이 아닐 경우 소수인지 판별한다. 2부터 i전까지 나눴을 때 나누어 떨어진다면 소수가 아니다. 이 방식으로 소수를 판별하고 소수가 없을 때에는 -1을 출력하고 그렇지 않다면 합과 최솟값을 찾아 출력한다. M = int(input()) N = int(input()) prime_numbe..

programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 접근 입력되는 W와 H가 1억 이하의 자연수이다. 그래서 뭔가 탐색을 하여 답을 구할 수 없다고 생각을 하고 규칙을 찾아보려고 했다. 하지만 규칙을 찾지 못하였고 다른 사람들의 풀이를 참고하였다. 종이에 여러가지 테스트 케이스로 그림을 그려보았는데 꼭지점의 개수에 주목을 하였다. WxH에서 대각선을 그었을 때 꼭지점의 개수가 W와 H의 최대공약수였다..

programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr 접근 스택을 활용하였다. 스택의 top과 다른 글자면 push하고 같은 글자면 pop하여 스택이 비어있는지 그렇지 않은지에 따라 최종해를 반환한다. 구현 입력된 문자열을 리스트로 변경한다. 각 리스트를 탐색하면서 스택의 top과 같다면 pop, 다르다면 push를 한다. 리스트를 모두 탐색했을 때 스택에 값이 들어있다면 실패, 스택이 비어있다면 성공을 반환한다. ..

programmers.co.kr/learn/courses/30/lessons/12953 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr 접근 입력되는 리스트의 모든 수를 곱한 결과까지 탐색을 하여, 여기서 구한 최댓값에 입력된 리스트의 각 숫자들을 나눴을 때 모두 나누어 떨어진다면 그 수를 반환한다. 구현 먼저 입력된 리스트의 수를 모두 곱하여 max_num에 저장하고 2부터 max_num까지 탐색을 한다. 이후 i (2부터 max_num)를 입력된 리스트의 원소들로..