Redddy's Devlog

🔈 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 ..

🔈 문제 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다. 사람의 수 N이 주어진다. 그리고..

다이나믹 프로그래밍 (Dynamic Programming) 다이나믹 프로그램은 동적 계획법이라고도 불리운다. 다이나믹 프로그램의 기본 모토는 중복되는 연산을 줄이는 것이다. 한번 실행한 연산들은 DP 테이블(리스트)에 저장해두고 그 연산이 필요할 때마다, 연산을 하지 않고 그 DP 테이블에서 연산데이터를 호출하는 방식이다. 이런 기법은 메모제이션 기법이다. 다이나믹 프로그래밍의 대표적인 예제로 피보나치 수열이 있다. 피보나치 수열의 점화식은 a(n) = a(n-1) + a(n-2), a(1) = 1, a(2) = 1 이다. 즉 이전 데이터와 전전 데이터를 더하여 현재 데이터가 된다. 피보나치 수열을 재귀적으로 구현한 코드는 다음과 같다. # 피보나치 함수(Fibonacci Function)을 재귀함수로 ..

도커는 컨테이너를 생성하고 관리하는 도구이다. 소프트웨어 유닛을 컨테이너라고 하며 여기에는 소스코드, 런타임 또는 실행시켜주는 기타 도구가 포함되어 있다. 버전 차이로 생기는 오류를 해결할 수 있는 것이 바로 도커이다. 이전 같은 경우에는 새로운 버전을 재설치, 삭제를 반복하여 문제를 해결하였다면, 도커와 컨테이너가 있다면 각 버전을 컨테이너에 보관하고 필요한 버전을 꺼내 사용하면 되었다. 사아실 아직까진 도커가 무엇인지, 또 도커의 필요성은 아직 잘 모르겠다 char char 알아가야지!!!

이진 탐색 (Binary Search) 이진 탐색이란 정렬되어 있는 데이터에서 특정 데이터를 찾을 때 사용된다. 이진 탐색 말고도 탐색법은 여러개가 있는데, 그중 순차 탐색은 리스트에 저장된 데이터를 처음부터 끝까지, 즉 첫번째 인덱스부터 마지막 인덱스까지 순서대로 탐색하는 방법이다. 이진 탐색의 탐색 방법은 우선 데이터의 중간값과 타겟을 확인한다음 만약 중간값이 타겟값보다 작다면 이제 중간값보다 더 큰 데이터들만 확인하고, 만약 중간값이 타겟값보다 크다면 중간값보다 작은 데이터들만 확인하면 된다. 다시말해 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 우리가 어렸을 때 했던 업앤다운 숫자찾기 게임도 이진 탐색을 사용하면 순차탐색보다 빠르게 찾아낼 수 있다. 1부터 10까지의 자연수 중 하나를..

🔈 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR​ 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 ..

🔈 문제 세 정수 a, b, L이 주어졌을 때, LCM(a, b, c) = L을 만족하는 가장 작은 c를 찾는 프로그램을 작성하시오. LCM(a, b, c)는 a, b, c의 최소공배수이다. 📝입력 첫째 줄에 a, b, L이 주어진다. (1 ≤ a, b ≤ 106, 1 ≤ L ≤ 1012) 📑출력 첫째 줄에 c를 출력한다. 만약, 가능한 c가 없으면 -1을 출력한다. 📚 문제 해석 이전에 풀었던 최대 최대 최소공배수 찾기 문제와 비슷한 유형같아서 풀어보았다. 이번 문제는 a와 b 그리고 L 이 주어질 때 lcm(a,b,c) == L 을 만족하는 c의 최소값을 구하면 된다. 처음에 미리 a와 b의 최소공배수를 구한 다음 while 문을 돌려서 c의 값을 하나씩 올려 L을 찾았는데, TLE 판정 받았다. 그..

🔈 문제 1부터 N까지의 수가 있다. 최소공배수가 최대가 되도록 서로 다른 3개의 수를 선택해 보자. 📝입력 첫째 줄에 테스트케이스의 개수 T가 주어진다. (1≤T≤1000) 둘째 줄부터 T개의 줄에 각각 자연수 N이 주어진다. (3≤N≤100000) 📑출력 각 테스트케이스마다, 최소공배수의 최댓값을 한 줄에 하나씩 차례대로 출력한다. 📚 문제 해석 1부터 n 까지의 수 중에서 3개의 숫자를 골라 최소공배수를 구하는데, 이때 이 최소공배수가 최대가 되도록 3개의 숫자를 골라야 한다. 처음에는 n이 짝수라면 n과 n-1 그리고 n-3 의 최소공배수가, n이 홀수라면 n과 n-1 그리고 n-2의 최소공배수가 최대 최소공배수가 될거라고 생각했다. 숫자가 클수록 최소공배수가 커질 것이라고 생각했고, 짝수일때 n..

🔈 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 2..

Kolya got an integer array a1,a2,…,an The array can contain both positive and negative integers, but Kolya doesn't like 0, so the array doesn't contain any zeros. Kolya doesn't like that the sum of some subsegments of his array can be 0. The subsegment is some consecutive segment of elements of the array. You have to help Kolya and change his array in such a way that it doesn't contain any subse..