민규의 흔적

2024년 7월 5일문제 링크 : 프로그래머스 - 게임 맵 최단거리 문제 접근 한 칸을 이동하는 과정을 한 턴 이라고 이야기하겠다. 적진(지도의 맨 오른쪽 맨 아래 위치)으로 가는데 필요한 최소한의 턴을 구하는 문제이다. 이 문제는 1일차에 [0, 0]에서부터 바이러스가 하루에 주변 한 칸씩 퍼질 때 [n - 1, m - 1]은 며칠차에 감염되는가? 와 같은 문제이다. 문제를 풀기 위해선 다음과 같은 접근 방식이 필요하다. 한 턴에 갈 수 있는 칸은 여러 개 일 수 있다. 나는 이 문제를 BFS 방식으로 풀이할 것이다. 또한, 뒤에서 말할 변수들의 이름은 다음과 같은 뜻을 가지고 있다고 생각해두자. queue = 다음 방문 예정인 노드들 next_v = 지금 위치에서 한 턴 뒤에 갈 수 있는 모든 노드들..

2024년 7월 5일문제 링크 : 프로그래머스 - 전력망을 둘로 나누기 문제 접근 위와 같이 모든 정점이 이어져 있는 한 트리가 주어질 때 간선 하나를 잘랐을 때 나눠진 두 트리의 정점의 개수 차이가 가장 적을 때의 해당 차이를 출력하는 문제이다. 처음 문제를 보고 단절선과 관련된 문제인가? 생각했지만, 모든 간선을 하나씩 제거해보았을 때 나눠진 두 트리의 정점 개수만큼 차를 완전탐색으로 구할 수 있는 문제라고 판단했다. ( 시간복잡도 계산은 맨 뒤 풀이 후기에서 후설하겠다 ) (단절선이란 ? : https://ymg5218.tistory.com/12) 주어진 간선 정보 중, 한 간선을 제거하였을 때 1번 정점을 시작으로 BFS 로직을 돌려 해당 정점과 이어진 정점들을 True로 치환하고, BFS 로직이..

2024년 7월 1일문제 링크 : 프로그래머스 - 피로도문제 접근 규칙을 찾아야하나? 그리디하게 접근해야하나? 한 1분 고민했다. 근데 문제 조건을 보자 일말의 고민도 없이 완전탐색을 해야겠다고 결정했다. 던전의 개수는 1 이상 8 이하입니다. 문제의 조건을 잘 읽어야 하는 이유이다. N이 작기 때문에 던전을 도는 순서에 대해 모든 경우의 수를 얻어내 각 경우의 수에서 차례대로 던전을 탐험할 때 최대 몇 개까지 탐험할 수 있는지를 모든 경우의 수에서 알아보면 된다. 각 경우의 수를 확인하며 최대로 탐험할 수 있는 개수를 계속 갱신시켜주면 된다. 나는 모든 경우의 수를 얻어내기 위해 백트래킹 기법을 사용하여 문제를 해결하였다.전체 코드 # 던전이 최대 8개이기 때문에 백트래킹으로 모든 경우의 수를 고려해보..

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월 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 이다.하지만 여기서는 안 입는 조건도 생각..