본문 바로가기

알고리즘

 (128)
[알고리즘] 점화식의 이해(recurrence relation) 점화식 수열의 귀납적 정의와 유사 차이 : 인접한 항간의 관계만을 다루는 것은 아니다. 어떤 함수를 자신보다 더 작은 변수에 대한 함수 자신과의 관계로 표현한 것. (수열 = 정의역이 정수인 함수) 되부름, 혹은 유사한 방식으로 문제를 풀 때 걸리는 시간을 구하는데에 사용함 ex) T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) + 1 An = T(n), An = 2A(n-1) + 1 점화식을 푸는 법 1. 반복 대치 : 주어진 조건을 이용하여 점점 작은 함수로 반복해서 대치하는 방법. 침착하게 꼼꼼히! 2. 추정 후 증명 : 점화식의 결론을 추정하고, 귀납법으로 증명함. 반복 대치가 복잡할 때 유용함. but 추정이 쉽지 않을 수 있음 3. 마스터 정리 : 점화식 공식. 여기에서는 다..
[알고리즘] 알고리즘 개요 및 정의 알고리즘의 정의 : 어떤 입력에도 정확한 출력을 유한한 시간 안에 내는 프로그램 어떤 입력 : 문제의 난이도나, 입력의 크기에 상관없이 문제를 풀 수 있다. 정확한 출력 : 문제가 요구하는 조건을 만족한다. 정답이 요구하는 조건이 무엇인지 명시할 수 있다. 유한한 시간 : 무한루프에 빠지지 않고 납득할 수 있는 시간에 종료한다. ex) 100명의 학생들의 시험 점수 중 최댓값을 구하시오. 수학적 귀납법→ 정확성 : 자명하다. → 시간 : n명의 점수를 읽으면, n-1번 비교. → max(지금까지의 최댓값, i+1번째 학생의 점수) ex) 100명의 학생들의 시험 점수 중 최빈값을 구하시오. ex) 입력 : U={1,2, … , n} 중에서 특정한 수 하나만 빼고 무작위의 순서로 n-1개의 숫자가 한번에 ..
[PGS] Lv.1 : 소수 만들기 https://school.programmers.co.kr/learn/courses/30/lessons/12977 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다. nums의 각 원소는 1 이상..
[PGS] Lv.1 : 음양 더하기 https://school.programmers.co.kr/learn/courses/30/lessons/76501 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 return 하도록 solution 함수를 완성해주세요. 제한사항 absolutes의 길이는 1 이상 1,000 이하입니다. absolutes의 모든 수는 각각 1 이상 1,000 이하입니..
[C++/백준] 10989 : 수 정렬하기 3 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 브론즈 1티어. 처음에는 아무 생각 없이 배열에다가 입력을 모두 저장하고, 버블 정렬 식으로 풀면 된다고 생각했는데 특이하게도 이 문제는 메모리 제한이 8MB이었다.(아주 작은 편) 그래서 배열 크기 + 정렬 시간 -> 실패 예감 // 아래는 메모리 초과 코드 int main() { int n; int a = 0; int nums[10000000] = { 0, }; cin >> n; for (int i = 0; i > num..
[C++/백준] 2920 : 음계 문제 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8부터 1까지 차례대로 연주한다면 descending, 둘 다 아니라면 mixed 이다. 연주한 순서가 주어졌을 때, 이것이 ascending인지, descending인지, 아니면 mixed인지 판별하는 프로그램을 작성하시오. 브론즈 2. PS에 여러 방법이 있을 것 같아 고민하다가 입력과 동시에 비교하는 방법이 가장 효율적일 것 같아서, 반복문 안에 if문을 넣어버렸다. 근데 다른 풀이를 보니 숫자 누적 말고 그냥 tf로 했어도 되는거였네...ㅎㅎ #include..
[C++/백준] 2775 : 부녀회장이 될테야 문제 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다. 아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다. 브론즈 1. 생각보다 문제 풀기가 복잡하고 까다로웠다. 이차원배열을 사용하여 풀었더니 비주얼 스튜디오에서 C..
[C++/백준] 1712 : 손익분기점 문제 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다. 예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다. 노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다. A, B, C가 주어졌..
728x90

티스토리툴바