개발 일기

5. 볼링공 고르기 문제 A, B 두 사람이 서로 무게가 다른 볼링공을 고르려고 한다. 총 N개의 볼링공이 있고 각 공에 무게가 적혀있으며 공의 번호는 1번부터 순서대로 부여된다. 같은 무게의 공이 여러 개 있을 수 있지만 서로 다른 공으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다. N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하시오. 예시 N이 5고 M이 3이며 각각의 무게가 1 3 2 3 2일 때 각 공의 번호가 차례대로 1번부터 5번까지 부여된다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같다. (1, 2) / (1, 3) / (1, 4) / (1, 5) / (2, 3) / (2, 5) / (3, 4) / (4, 5..

4. 만들 수 없는 금액 문제 동네 편의점 주인인 동빈이는 N개의 동전을 갖고 있음. N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오. 예시 N=5이고 각 동전이 각각 3/2/1/1/9원짜리 동전이면, 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원임. N=3이고 각 동전이 3/5/7원짜리 동전이면, 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원임. 입출력 조건 입력 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어짐 (1 ≤ N ≤ 1,000) 둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분함. 이때 각 화폐 단위는 1,000,000 이하의 자연수임 출력 첫째 줄에 주어진 동전들로..

3. 문자열 뒤집기 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 할 때, 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집기란 0을 1로 1을 0으로 만드는 것을 말한다. 문자열 S가 주어졌을 때 다솜이가 해야 하는 행동의 최소 횟수를 출력하시오. 예시 예를 들어 S = 0001100일 때 전체를 뒤집으면 1110011이 됨 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어 두번만에 모두 같은 숫자로 만들 수 있음 하지만 처음부터 4번째 문자부터 5번째 문자까지 뒤집으면 한 번에 0000000이 되어 모두 같은 숫자로 만들 수 있음 입출력 조건 입력: 첫째 줄에 0과 1로만 이..

2. 곱하기 혹은 더하기 문제 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 ‘X’ 혹은 ‘+’ 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정함. 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어짐 예시 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 ((((0+2)*9)8)*4)=576임 567이 주어지면 가능한 가장 큰 수는 567=210임 입출력 조건 입력: 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어짐 (1 ..

1. 모험가 길드 문제 한 마을에 N명의 모험가가 있다. 모험가 길드에서는 N명의 모험가를 대상으로 ‘공포도’를 측정했는데, ‘공포도’가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다. 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있을지 궁금하다. 동빈이를 위해 N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하시오. 단, 몇 명의 모험가는 마을에 그대로 남아 있어도 되므로 모든 모험가를 특정 그룹에 넣을 필요는 없음 예시 N=5, 공포도 2 3 1 ..

Search for a Range (Find First and Last Position of Element in Sorted Array) https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/802/ Explore - LeetCode LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore. l..

Find Peak Element https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/801/ 분류: Top Interview Questions - Medium - Sorting and Searching Explore - LeetCode LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore...

Generate Parentheses https://leetcode.com/explore/interview/card/top-interview-questions-medium/109/backtracking/794/ 분류: Top Interview Questions - Medium - Backtracking Explore - LeetCode LeetCode Explore is the best place for everyone to start practicing and learning on LeetCode. No matter if you are a beginner or a master, there are always new topics waiting for you to explore. leetcode.com 문..

Sqrt(x) https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/819/ 분류: Top Interview Questions - Medium - Math 문제 음이 아닌 정수 x가 주어졌을 때 x의 제곱근을 계산해라. 결과는 가장 가까운 정수로 내림하여 반환 값도 음이 아닌 정수여야 한다. built-in 연산자나 함수를 사용하지 않고 해결해야 한다. type x: int / rtype: int 예시 Example 1: Input: x = 4 Output: 2 Explanation: The square root of 4 is 2, so we return 2. Example 2: Input: x = 8 Out..

Pow(x, n) https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/818/ 분류: Top Interview Questions - Medium - Math 문제 x의 n승을 계산하는 pow(x, n)을 구현하라. type x: float, type n: int, rtype: float 예시 Example 1: Input: x = 2.00000, n = 10 Output: 1024.00000 Example 2: Input: x = 2.10000, n = 3 Output: 9.26100 Example 3: Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-..