ps17 [백준] 12014 주식 https://www.acmicpc.net/problem/12014 전형적인 LIS + binary search 문제이다. 최장 증가 부분 수열이라고 하는 LIS는 DP를 통해 O(N^2)로 풀거나, 이진탐색으로 O(nlogn)으로 풀 수 있다. 가장 긴 증가하는 부분 수열을 알아내는 방법에 이진 탐색을 쓰는 이유는 찾고자 하는 LIS 배열이 정렬되어 있기 때문에 logN의 시간복잡도로 있어야 할 인덱스를 알아낼 수 있기 때문이다. 무슨 말이냐면 예시로 arr = [100, 50, 70, 60, 87, 105, 78, 110, 60] 일 때 찾고자 하는 lis 배열은 lis = [100] 이다. 그 다음 arr의 1번 인덱스 부터 lis 배열에 들어갈 수 있는지 없는지 판정하는 것이다. 100 li.. 2025. 5. 6. [백준] 1034 램프 https://www.acmicpc.net/problem/1034 아이디어011010 에서 2번째 행의 0을 키게 되면 해당 열의 모든 비트가 반전되므로 001111 이 되어서 답이 2가 된다. 열 전체가 바뀌므로, 동일한 비트의 개수가 중요하다고 생각했다. 어떤 자리의 비트를 키는 횟수는 k번 정의 되므로반드시 k번의 열 반전이 일어난다.그럼 결국 동일한 비트의 개수 중에 최대인 것을 뽑고그게 k번 안에 모두 1로 바꿀 수 있는지 판별하면 된다.1.dict를 통해서 각 행의 비트의 중복되는 수를 세어 준다.2. 0의 개수를 세어준다. (p라고 하자)3. p가 짝수면 k도 짝수여야 하고, p가 홀수면 k도 홀수여야 한다.4. p는 k보다 작거나 같아야 한다. n,m = map(int, input().sp.. 2025. 4. 27. [백준] - 14719 빗물 https://www.acmicpc.net/problem/14719 생각을 코드로 구현하면 되는 문제이다. 일단 1이 벽이고 0이 빈칸이라고 했을 때, 첫번째 1이 생겨서 벽이 생기면 그 이후로는 전부 물이 고일 가능성이 존재한다.그리고 다음 1이 나오면 연속된 0을 ans에 더해주면 된다.H,W = map(int, input().split())board = [[0]*W for _ in range(H)]l = list(map(int, input().split()))for i in range(len(l)): for j in range(l[i]): board[j][i] = 1ans = 0for i in range(H): wall_cnt = 0 water_tmp = 0 fo.. 2025. 4. 22. [백준] 1334 다음 팰린드롬 수 https://www.acmicpc.net/problem/1334 문제 유형 : 구현 조건 분기가 많아서 귀찮긴한데 하나씩 처리하면 된다. 12345 1234612 4646이 12보다 크기 때문에 46앞의 자리를 +1 해준다.그럼 12400이 되고, 여기서 부터 1씩 증가시켜주면 12421이 된다. 그럼 N보다 큰 팰린드롬수가 된다.9999를 예로 들면10000이 되고 left = 10, right = 00이 된다. 10이 00보다 크기 때문에 right에 1을 더해준다.그럼 10001이 된다.12345 -> 12346 -> 124211999 -> 2000 -> 2002123 -> 124 -> 131191 -> 192 -> 2021234 -> 1235 -> 1241 여기서 짝수 홀수에 따라 mid 의 존.. 2025. 4. 20. [백준] 10427 빚 https://www.acmicpc.net/problem/10427 그리디 + 누적합 문제인데 쉽게 말해서 M = 3 이면 3 * [고른 3개 숫자 중에서 제일 큰 값 ] - [고른 3개의 숫자 총합] 인 값들의 집합 중에서 제일 작은 값들의 합이 얼마인지 찾는 문제이다. 지문을 보고 내가 알고 있는 형태로 바꾸는 연습을 계속 해야 한다. 일단 딱봐도 10^4개 중에서 1개 고르고, 2개 고르고 ... N 개 고르는 건 완전 탐색으론 절대 무리기 때문에 정렬을 통한 그리디를 생각 해볼 수 있다. 정렬을 해보면 예를 들어서 [3, 5, 10, 14, 17] 이 있다고 가정해 보자. 처음 1개를 고르는 S(1) 은 어차피 0 이므로 제외하고 S(2)일 때를 가정하면 2 * 5 - (3 +5)2 * 10 -.. 2025. 3. 16. 알고리즘문제해결전략 - 완전 탐색 완전 탐색모든 경우의 수를 순회하는 방법재귀 호출더이상 쪼개지지 않는 기저 사례(base case)를 선정하고 반복적으로 같은 작업(코드)를 처리하는 것완전 탐색 레시피완전탐색의 대략적인 지침은 다음과 같다.완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠한다. 만약 시간 안에 계산 할 수 없으면 다른 알고리즘을 써야 한다.가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다. 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.조각이 하나밖에 .. 2025. 2. 6. 알고리즘문제해결전략 - 알고리즘 정당성의 증명 5장 알고리즘의 정당성 증명증명을 소홀히 하지 마라알고리즘 외우지 말고 증명을 이해해라수학적 귀납법과 반복문 불변식100개의 도미노가 존재할 때 다음 두 가지 사실을 알고 있다.첫 번째 도미노는 직접 손으로 쓰러트려야 한다.한 도미노가 쓰러지면 다음 도미노는 반드시 쓰러진다.귀납법의 증명은 크게 3가지로 나뉜다.단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눈다.여기선 100개의 도미노를 하나의 도미노에 대한 규칙으로 나눴다. 당연한 소리지만 단계로 나누는 것이 가장 중요하다.첫 단계 증명 : 그중 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다.귀납 증명 : 한 단계에서 증명하고 싶은 내용이 성립하면, 다음 단계에서도 성립함을 보인다. 앞의 예에서 한 도미노가 쓰러지만 다음 도미노는 반드시 쓰러.. 2025. 2. 4. [백준] 2421 저금통 https://www.acmicpc.net/problem/2421문제 설명 홍태석은 저금통 2개를 가지고 있다. 홍태석은 매일매일 하나의 저금통에 1원을 넣는다. 두 저금통에 모두 N원이 모이면 태석이는 새로운 장난감을 살 수 있기 때문에, 저금을 멈춘다.홍태석은 소수를 좋아하는 것으로 서강대에서 유명하기 때문에, 첫째 저금통에 들어있는 돈의 양과 둘째 저금통의 돈의 양을 이어붙였을 때, 그것이 소수가 되는 것을 너무나도 좋아한다.예를 들어, 첫째 저금통에 12원이 있고, 둘째 저금통에 7원이 있다고 하자. 그럼 그 두 수를 이은 127은 소수가 된다.이제, 최대한 소수가 많이 나오도록, 홍태석이 돈을 넣는 최적의 순서를 찾아내면 된다. 가장 처음에 두 저금통에는 1원씩 들어있다.예를 들어, N=4일 .. 2025. 1. 30. [백준] 14500 테르로미노 https://www.acmicpc.net/problem/14500문제폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.정사각형은 서로 겹치면 안 된다.도형은 모두 연결되어 있어야 한다.정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.테트로미노는 반드시 한 정사각.. 2024. 6. 9. [백준] 1774 - 수 묶기 def f0(n): if n > 0 and n != 1: return True return False def f1(n): if n 2024. 2. 20. 이전 1 2 다음
