0과 1의 쉼터

풀이 각 지점에서 목표지점(2) 까지의 거리를 출력하는 문제로 반대로 생각해서 목표지점에서 출발해 갈 수 있는 모든 거리에 대한 거리를 계산하는 문제로 풀이할 수 있다. 입력을 받으면서 목표지점(=출발지점)을 찾으면 0으로 대신 넣어주고, 1이면 -1로 넣어주자. 그 외의 숫자는 그대로 넣어주면 된다. 1일 때 -1을 넣어주는 이유는 출발지점으로부터 출발했을 때 갈수없는 땅(0)으로 둘러싸인 영역은 도달할 수 없는 위치(-1)임을 미리 표시하기 위함이다. 출발지점에서 도달할 수 있는 영역의 1들이 전부 -1 로 바뀌면 문제가 없을까? 그렇다, 어차피 도달할 수 있는 영역의 거리들은 이전에 도달한 거리의 값(출발지점 = 0 이므로 0 이상의 수)에 1을 더한 값이기에 결국은 덮어쓰일 것이다. 그 이후로는 ..

풀이 정렬된 점수들의 절사평균을 구하는 문제이다. 가장 작은 15%의 인원과, 가장 큰 15%의 인원을 제외한 후 나머지 인원에 대해 평균을 구한 후 반올림을 해서 출력해주면 된다. 문제는 단순하지만 Python을 사용하다보니 예상치 못한 복병들이 많았다. 우선 첫 번째로 주어지는 점수들의 개수가 최대 3 x 10^5 이다. 실버 난이도의 문제답지 않게 많은 입력이 주어진다. 빠른 입출력을 해주자. 그 다음으로는 전체 인원에 대한 절사평균이 성립하지 않는 경우다. 즉, 인원이 너무 적어 절사평균을 구하기 위해 제외해야할 인원이 적은 경우이다. 15%에 해당하는 인원의 반올림한 값이 0보다 큰 경우에만 인원을 제외시켜 주자. 다른 하나는 Python의 round()의 작동 방식에 대한 문제다. 일반적으로 ..

풀이 주어지는 나머지 M이 모든 case가 일치한다는 보장이 없다. 매번 새로운 피보나치 수열의 수들에 대해 M으로 나눈 나머지로 이루어진 수열을 구해야한다. 다행히도 문제에서 요구하는 수열에는 Pisano Period라는 규칙성이 존재한다. 즉, 모든 피보나치 수열의 수들에 대해 계산할 필요가 없다. 결국 주기에 따라 수열들의 수는 반복을 하기 때문이다. 우선, 아래의 예제 Pisano Period table을 살펴보자. 피보나치 수열들을 K번째 피보나치수로 나누었을 때 나머지들의 수열이다. 즉, Pisano period의 주기는 나머지가 {0, 1}이 나올때를 기준으로 이루어진다는 것을 알 수 있다. 0만 나오는 경우에는 성립하지 않는다. 나머지가 {0, 1}이 나올때까지 반복해주자. 어차피 입력되는..

풀이 각 요일마다 주어진 상담을 진행할 경우 겹치는 분기를 표시한 그림이다. 상담 시작요일은 다 다르지만, 상담이 끝나는 날은 다른 상담기간과 겹치는 것을 확인할 수 있다. 때문에, brute force방식(또는 bottom-up)으로 풀이할 경우 모든 상담일정 기간 이후의 모든 기간에 대해 반복문을 돌며 최대 수익을 반영해줘야 한다. 아래 그림처럼 말이다. 좀 더 효율적으로 풀이해보자. 이전 방법은 현재 상담을 통해 미래의 최대 수익이 변화한다는 특징이 있었다. 하지만, 미래에서 현재까지 거꾸로 최대 수익을 계산하는 방법은 어떨까? 미래의 상담일정은 현재의 상담일정에 대해 영향을 끼치지 않는다. 시간은 거꾸로 흐르지 않기 때문이다! 상담 일정이 퇴사 일정을 초과하지 않는다면, 다음 날(day + 1)에..

풀이 스티커를 사용할 때 변을 공유하는 스티커는 사용할 수 없다는 조건이 있다. 따라서, 스티커를 최대한 많이 사용하고자 한다면 대각선으로 진행하며 사용할 때 가장 많은 스티커를 사용할 수 있다. 총 5개의 스티커를 고를 수 있다. 하지만, 이러한 방식이 항상 스티커 점수들의 최댓값임을 보장하지 않는다. 문제에서 주어진 경우를 살펴보자. 50 - 50 - 100 - 60 으로 총 4개의 스티커를 사용했지만, 스티커 점수들의 합은 260으로 이전에 선택한 경우보다 큰 점수를 가진다. 따라서, 각 스티커 영역마다 가질 수 있는 최댓값을 기록할 때 아래 그림과 같은 선택지를 고려해야 한다. 먼저, 단순하게 대각선으로 선택한 경우다. 주황색은 선택하지 못하는 영역, 초록색은 지금 선택한 영역, 파란색은 선택할 ..

풀이 일전에 풀었던 LIS문제에서 사용한 방법을 응용해 풀이할 수 있다. [백준 11053] 가장 긴 증가하는 부분 수열 [Python] 풀이 LIS (Longest Increasing Subsequence)는 최장 증가 부분 수열로, N개의 원소에 대해 요소를 골라 만든 부분 수열을 만들 때 각 원소가 이전 요소보다 큰 원소로 이루어진 부분 수열을 의미한다. 즉, 가 kyr-db.tistory.com LDS (Longest Decreasing Subsequence) 라고 하더라도, 결국은 LIS와 동일하게 요소간의 차이가 항상 커지거나 작아지는 비연속 부분 수열을 찾으면 되기 때문이다. 다만 주의할 점이 있는데, LIS의 길이를 구할 때 처럼 1번 요소부터 N번 요소 방향으로 탐색을 진행하면 기록되는 ..

풀이 LIS (Longest Increasing Subsequence)는 최장 증가 부분 수열로, N개의 원소에 대해 요소를 골라 만든 부분 수열을 만들 때 각 원소가 이전 요소보다 큰 원소로 이루어진 부분 수열을 의미한다. 즉, 가장 긴 비연속 부분 수열의 길이를 알아내면 된다. 그렇다면, LIS는 어떻게 만들어 지는가? 기본적으로 위에서 언급했 듯 이전 요소보다 큰 요소가 나오면 된다. 문제의 입력에서 알 수 있듯 항상 증가만 하는 요소로 주어지지 않는다. 아래 그림을 보자. 입력받은 배열 A와, 배열에 대한 LIS 길이를 기록할 dp배열이 있다. 그 아래에는 단순히 이전 요소보다 큰 요소가 나오는 경우만 기록한 Increasing Subsequence이다. 첫 번째 경우 10 - 20 - 30 - ..

풀이 combination을 구현해 값을 출력하면 되는 문제이다. 다른 언어의 경우 bigInteger가 없으면 구현하기 까다롭지만, Python에서는 표준 라이브러리를 이용해 풀이할 수 있다. 문제에서 주어지는 최댓값인 100 C 50은 작은 편으로 빨리 풀고 넘기자. 날먹 츄르릅.. 소스코드 소스코드 보기 출처 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net

풀이 부터 시작해 주어진 M, N에 관련된 조건에 맞게 두 자연수를 1씩 증가(이 때 k도 1씩 증가) 해야 한다. 증가한 두 자연수가 이 되기 전에 와 일치하면, 그때의 k를 출력하면 된다. 기본적인 로직은 아래와 같다. 단순히 (M, N, x, y)가 (39999, 40000, 39999, 40000) 으로 주어져도 LCM(39999, 40000) = 1,599,960,000 이기에 위의 방식대로 모든 수를 다 구하면 시간초과가 발생할 것이다. 난이도가 실버1로 낮은 편이고, 주어지는 수 또한 작은 수에 해당되기에 중국인의 나머지 정리를 사용하지 않고도 풀이할 수 있다. 아래와 같은 풀이 과정을 통해 접근이 가능하다. 구하고자 하는 k는 이 가 되기 위해 (x = y)가 아닌 이상 M, N의 배수에 ..

풀이 스택이란 항아리 처럼 나중에 집어넣은 것이 먼저 나오는 제한적 접근 나열 구조이다. LIFO(Last In First Out) 형식이며, 기본 개념을 구현만하면 된다. 단, 한 줄에 하나씩 출력해야 한다는 것을 명심하자 pop 명령을 실행하기 전에 스택이 비었는지 확인하기 위해 empty 명령어만 함수로 구현했다. 실제 메모리에 대한 참조를 해제할 필요 없이, 변수 top을 사용해 값을 가르키는데 제한을 두었다. 소스코드 소스코드 보기 출처 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net..