지민 개발 블로그

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.'원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치를 사용한다. 이 풀이의 아이디어는 '현재 상황에서 조건을 만족할 수 있는가?'를 확인한 뒤 조건의 만족 여부('Yes' or 'No)에 따라서 탐색 범위를 좁혀서 해결할 수 있다. 이 범위를 좁힐 때에 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀나간다.

그리디 알고리즘이란,단순하지만 강력한 문제 해결 방법이다.이 유형은 "탐욕법"이라 소개되기도 하는데, 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.여기서 "탐욕적"이라는 말은 '현재 상황에서 지금 당장 가장 좋은 것만 고르는 방법"을 의미한다.그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.출제 동향 이 유형은 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다. 다만, 그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓기 때문에, 다익스트라 알고리즘과 같이 특이 케이스를 제외하고는 단순 암기를 통해 모든 문제를 대처하기는 어렵다. 그리디 알고리즘 유형의 문제는 매..

이진탐색이 시간초과 해결의 Point였다. 처음에 이 문제를 우당탕탕 풀었을 때는 Case의 답 중 가장 큰 값에서 -1씩 해서 모두 돌려보는 과정으로 이 문제를 해결해보았다. 그러나 시간초과가 나왔다. 다른사람들 코드를 구경하다보니, start,end,mid가 있길래 '어 이거 이진탐색문항이구나..' 깨닫게 되었다. 알고보니 이진탐색을 활용하면 빠르게 풀이되는 문항이었다.이진탐색은 https://stopmin.tistory.com/28 에 간단하게 정리해두었다! 내가 처음 짠 코드들은 둘 다 순차탐색을 활용한 코드였기에 시간초과가 나올 수 밖에 없었다.  내가 처음 짠 2개의 시간초과 코드들)import sysK, N = map(int,sys.stdin.readline().split())string =..

이진 탐색이란, 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다.이진탐색 vs 순차탐색1) 순차탐색순차탐색이란, 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.즉, 이진탐색과는 구분되는 방법이다. 순차탐색은 주로 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용된다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다. 구현도 매우 간단하다. /*논외로, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다.*/2) 이진탐색이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이진 탐색은 위치를..

보호되어 있는 글입니다.

Brute Force Algorism은 "완전탐색알고리즘"으로 Brute는 "무식한"을 뜻한다.무식하다? :"가능한 모든 경우의 수를 '모두' 탐색하면서 요구조건에 충족되는 결과만을 가져온다"라는 특징에 존재한다.*해가 존재할 것이라고 예상되는 영역을 모두 탐색!!*Solutionstep 1.주어진 문제를 선형으로 구조화하기step 2.구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.step 3.구성된 해를 정리한다.브루트 포스 문제의 종류자료의 구조가1) 선형구조 ->순차 탐색2) 비선형구조 -> BFS, DFS활용 문항 #2798_블랙잭Solution)1. 모든 Card를 List안에 넣는다.2. Itertools 의 Combination함수를 활용해서 3개씩 묶어서 List를 만들어..

문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,0..

문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다. 2보다 큰 짝수..

문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다. 입력의 마지막에는 0이 주어진다. 출력 각 테스트 케이스에 대해서, n보다 크고..

문제 무한히 큰 배열에 다음과 같이 분수들이 적혀있다. 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. 출력 첫째 줄에 분수를 출력한다. 예제 입력 1 1 예제 출력 1 1/1 예제 입력 2 2 예제 출력 2 1/2 예제 입력 3 3 예제 출력 3 2/1 예제 입력 4 4..