민규의 흔적

2024년 6월 30일문제 링크 : 백준 15649번 - N과 M (1) 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 알고리즘 분류백트래킹문제 접근 자연수 N이 주어졌을 때, 1 ~ N 까지의 자연수 중, 중복 없이 길이 M만큼의 수열로 올 수 있는 모든 경우의 수를 사전 순으로 출력해야 하는 문제이다. 모든 경우의 수..

2024년 6월 30일문제 링크 : 프로그래머스 - 카펫문제 접근 문제에 어떤 규칙이 있는지 먼저 알아야 한다고 판단했다. 1. 카펫 테두리 1줄은 갈색(brown)으로 칠해져 있다.2. 테두리 1줄을 제외한 내부는 모두 노란색(yellow)이다.3. 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 길다.  brown = 24, yellow = 24인 경우를 보자. yellow가 24만큼 칸을 차지하려면 다음과 같은 가로, 세로 조합을 가질 수 있다. 가로세로2411228364 각각의 모든 경우에, 테두리 1줄을 차지하는 brown 몇 칸을 차지하게 되는지를 계산해보고, brown이 24칸을 차지하는 경우의 가로,세로 조합을 출력하면 된다. 가로세로 brown 241541223283266424 b..

2024년 6월 26일문제 링크 :  백준 2231번 - 분해합문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.입력첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.출력첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. 알고리즘 분류브루트포스 알고리즘 문제 ..

2024년 6월 26일문제 링크 : 백준 2798번 - 블랙잭 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어..

2024년 6월 26일문제 링크 : 백준 1436번 - 영화감독 숌 문제 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작..

2024년 6월 22일문제 링크 : 프로그래머스 - 의상문제 접근 각 카테고리의 옷은 0 ~ 1 가지 입을 수 있으며, 최소한 하나라도 입는 옷 코디 조합을 구하는 것이다.단, 모든 옷을 0개 입는(아무것도 입지 않는) 경우는 코디 조합에 포함시키지 않아야 한다. 문제를 보자마자 딕셔너리로 카테고리별 옷들의 종류를 구분해주어야 겠다고 생각했다. 그러면 각 카테고리별로 옷이 몇 가지 씩 있는지 알 수 있는데, 단 해당 카테고리의 옷을 안입는다는 전제도 포함해야 하므로 공백문자("")또한 각 카테고리별로 추가해주었다. 우리는 여기서 가짓 수를 조합하는 공식을 떠올릴 수 있다. A개의 상의와 B개의 하의와 C개의 신발을 입는 서로 다른 코디의 종류는 A * B * C 이다.하지만 여기서는 안 입는 조건도 생각..

2024년 6월 22일문제 링크 : 프로그래머스 - 소수 찾기(Lv 2) 문제 접근 해야하는 작업은 크게 2가지 이다.1. 주어진 숫자 카드를 조합하여 나올 수 있는 모든 수를 구하기 2. 모든 수 중에서 소수 판별하기 1번 작업은 파이썬에서 itertools 라이브러리의 순열 함수 permutations()나 조합 함수 combinations()를 활용하면 쉽게 모든 수를 얻어낼 수 있지만, 나는 라이브러리의 힘을 최대한 빌리지 않기 위해 백트래킹 방식으로 구하였다. 0과 1, 그리고 2를 제외한 짝수는 모두 확실하게 소수가 아니기에 쓸데없는 연산을 줄이기 위하여, 조합을 진행하다 해당 수가 나왔다면 집합에 추가해주지 않았다. 이후, 2번 과정을 수행하기 위해 내가 구한 모든 수에 대해 " 2 ~ 현재..

2024년 6월 18일문제 링크 : 프로그래머스 - 섬 연결하기 문제 접근 모든 섬을 최소 비용으로 연결했을 때, 해당 비용을 출력하는 문제이다. 이어져있지 않은 섬은 존재하지 않기에, 최소 신장 트리(MST)를 찾는 문제라고 판단해 크루스칼 알고리즘을 활용하고자 하였다. 다음과 같은 그래프가 있다고 가정해보겠다.  모든 간선의 정보를 비용을 기준으로 오름차순 정렬하고, 각 노드의 루트 노드 정보를 담을 배열을 선언 및 초기화, MST의 총 길이를 나타내는 length를 선언한다. 두 노드 중 어느 노드를 부모 노드로 할 지 통일시켜주기 위해, 번호가 더 작은 노드를 부모노드로 지정하는 것으로 통일시켜주겠다. 이제부터, 각 간선의 정보를 앞에서부터 확인하며 탐색을 진행해보자.  0번 노드와 1번 노드의 ..