민규의 흔적

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

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

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