10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net 10162(Baekjoon). 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 각각 5분, 1분, 10초이다. 냉동음식마다 전자레인지로 요리해야할 시간 T가 초단위로 표시되어 있다. 우리는 A, B, C 3개의 버튼을 적절히 눌러서 그 시간의 합이 정확히 T초가 되도록 해야 한다. 단 버튼 A,..

1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 1065(Baekjoon). 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다. 출력 첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. b의 최대공약수를 출력한다. ❧ 테스트..

최대공약수 구하기 두 정수 $a$, $b$를 입력받아서, $a$, $b$의 최대공약수를 출력하시오. codeup.kr 2623(Codeup). 최대 공약수 구하기 카드 두 정수 a, b를 입력받아서, a, b의 최대공약수를 출력하시오. 입력 정수 a, b가 공백으로 구분되어 입력된다.(1 0: gcd = C A, B = B, C C = A % B print(gcd) 1️⃣ 유클리드 호제법 사용 2️⃣ 소수를 구하는 방법 사용 시, 시간 복잡도 : O(n) 3️⃣ 유클리드 호제법 사용 시, 시간 복잡도 : O(logn) 유클리드 호제법 [ 1. 교과서 속 주개념] [ 1) 유클리드 호제법] 두 정수 a, b의 최대공약수를 G(a, b)라고 하자. 정수 a, b, q r (b ≠ 0)에 대하여 a = bq ..

삼각화단 만들기 (Small) 주어진 화단 둘레의 길이를 이용하여 삼각형 모양의 화단을 만들려고 한다. 이 때 만들어진 삼각형 화단 둘레의 길이는 반드시 주어진 화단 둘레의 길이와 같아야 한다. 또한, 화단 둘레의 길이 codeup.kr 2625(Codeup). 삼각화단 만들기 (Small) 주어진 화단 둘레의 길이를 이용하여 삼각형 모양의 화단을 만들려고 한다. 이 때 만들어진 삼각형 화단 둘레의 길이는 반드시 주어진 화단 둘레의 길이와 같아야 한다. 또한, 화단 둘레의 길이와 각 변의 길이는 자연수이다. 예를 들어, 만들고자 하는 화단 둘레의 길이가 9m라고 하면 한 변의 길이가 1m, 두 변의 길이가 4m인 화단, 한 변의 길이가 2m, 다른 변의 길이가 3m, 나머지 변의 길이가 4m인 화단, 세..

7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 7795(Baekjoon). 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1. 두 생명체 A와 B의 크기가..

2650(Codeup) : 디지털 도어락 XX사에서 만든 디지털 도어락은 내부적으로 보안키 값을 가지고 있고, 이 값은 1,000이하의 자연수로 이루어져 있다. 각 카드키들은 ID값을 가지고 있는데, 이 값이 도어락의 내부 보안키 값의 약수이면 이 도어락을 열 수 있다. 길동이는 △△사에서 근무하고, △△사는 XX사에서 만든 디지털 도어락을 쓴다. 길동이가 자신의 사무실로 가기 위해서는 3개의 문을 통과해야 한다. 길동이는 자신이 통과해야하는 3개의 문의 내부 보안키 값을 알고 있을 때, 이 3개의 문을 모두 열 수 있는 만능 보안키를 여러분에게 의뢰했다. 길동이를 도와주자. 단, 보안키의 ID값이 클수록 제작비용이 적다. 최소한의 비용을 마스터 보안키를 만드는 프로그램을 작성하시오. 입력 세 자연수가 ..

최소 대금 입력은 5 행으로 이루어지며, 한 줄에 하나씩 양의 정수가 적혀있다. 1행의 정수는 첫 번째 파스타 가격이다. 2행의 정수는 두 번째 파스타 가격이다. 3행의 정수는 세 번째 파스타 가격이다. 4행 codeup.kr 2001(CodeUp) : 최소대금 열정이 불타오르는 신입생 지웅이는 최대한 많은 수업을 들을 수 있는 수업 조합으로 수강 신청을 하려고 합니다. 파파 파스타 가게는 점심 추천 파스타와 생과일 쥬스 세트 메뉴가 인기가 좋다. 이 세트 메뉴를 주문하면 그 날의 3 종류의 파스타와 2 종류의 생과일 쥬스에서 하나씩 선택한다. 파스타와 생과일 쥬스의 가격 합계에서 10%를 더한 금액이 대금된다. 어느 날의 파스타와 생과일 쥬스의 가격이 주어 졌을 때, 그 날 세트 메뉴의 대금의 최소값을..

시간 복잡도(Time Complexity) : 인풋 크기에 비례하는 알고리즘의 실행 시간을 나타낸다. 공간 복잡도(Space Complexity) : 인풋 크기에 비례하여 알고리즘이 사용하는 메모리 공간을 나타낸다. 빅오 표기법(Big-O Notation) nnn을 매우 크다고 가정한다. 절대적인 시간이 아닌 성장성을 보고 판단한다. O(1) : input의 크기가 소요 시간에 영향❌ (반복문이 없는 경우 대체로O(1)) O(n) : 반복되는 횟수∝ input의 크기 O(n^2) : 보통 중첩 반복문(반복문 내에 반복문이 있는 경우) O(n^3) : 중첩 반복문 O(lgn) : 보통 두배씩 증가

탐색 선형 탐색 알고리즘(Linear Search Algorithm) 최선의 경우 : 1 최악의 경우 :O(n) 이진 탐색 알고리즘(Binary Search Algorithm) 📢 정렬된 자료일 경우에만 사용 가능하다. 최선의 경우 : 1 최악의 경우 :log2n 재귀 함수 base case : 문제가 이미 충분히 작아서 바로 풀 수 있는 경우 recursive case : 문제를 더 작은 문제로 쪼개서 풀 수 있는 경우(재귀) 반복문으로 풀 수 있는 문제는 재귀 함수로 풀 수 있다. 재귀 함수의 문제점 call stack이 너무 많이 쌓이게 되면 프로그램 과부하 발생 재귀 함수의 호출이 너무 많이 발생하면 반복문으로 푸는 게 좋음 알고리즘 패러다임 Brute-Force Attack(무차별 대입 공격) ..