민규의 흔적

2024년 7월 8일문제 링크 : 프로그래머스 - 모의고사 문제 접근 문제가 요구하는 사항들이 명확해, 문제가 요구하는 사항들을 잘 읽기만 한다면 간단히 풀 수 있는 문제라고 생각한다. 수포자는 총 3명이다.1번 수포자는 1, 2, 3, 4, 5를 반복하며 찍는다.2번 수포자는 2, 1, 2, 3, 2, 4, 2, 5를 반복하며 찍는다.3번 수포자는 3, 3, 1, 1, 2, 2, 4, 4, 5, 5를 반복하며 찍는다.가장 많이 맞은 사람을 배열에 출력하면 되며, 가장 많이 맞은 사람이 여럿 존재할 경우 오름차순으로 배열에 담아 출력한다. 전체 코드 def solution(answers): answer = [] first_idx = 0 first_cnt = 0 first = [1, ..

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년 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월 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번 노드의 ..

2024년 6월 18일문제 링크 : 프로그래머스 - 가장 먼 노드 문제 접근 1번 노드에서 가장 먼 노드의 개수를 구하는 문제다. 한 노드에서 다른 노드들까지의 거리(one to all)를 구하는 문제라고 판단되어 다익스트라 알고리즘을 활용해야겠다 생각하였다. 모든 간선의 길이를 1로 간주하고 1번 노드에서 각 노드까지의 거리를 모두 계산한 후, 가장 먼 거리의 노드 개수를 출력하였다. 전체 코드 from collections import dequedef solution(n, edge): answer = 0 INF = 50001 graph = [[] for _ in range(n + 1)] for e in edge: graph[e[0]].append(e[1]) ..