민규의 흔적

2024년 8월 6일문제 링크 : 백준 1325번 - 효율적인 해킹 문제 해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.입력첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 ..

2024년 8월 6일문제 링크 : 프로그래머스 - 귤 고르기문제 접근 그리디하게 접근해 간단하게 풀 수 있는 문제라고 판단했다.  각 귤마다 이산 값을 가지며, 상자 하나에 k개의 귤을 담고자 할 때 귤의 크기 종류가 최소가 되도록 하고 싶으므로각 크기 별 귤의 개수를 딕셔너리에 저장해 각 value 값을 리스트 형태로 뽑아와 내림차순 정렬하여 종류가 많은 귤부터 상자에 넣으면 된다고 결론냈다.  k = 6, tangerine = [1, 3, 2, 5, 4, 5, 2, 3] 인 입력 예시를 들어보자. 각 크기별 개수를 딕셔너리 형태로 담아내면 다음과 같다. dict = {1 : 1, 2 : 2, 3 : 2, 4 : 1, 5 : 2} 각 value 값을 리스트 형태로 뽑아내면 다음과 같다. [1, 2, 2..

2024년 8월 6일문제 링크 : 프로그래머스 - 네트워크문제 접근 문제 자체는 엄청 간단하다. 서로 이어져있는 여러 대의 컴퓨터가 존재할 때, 각 컴퓨터끼리 이루는 네트워크의 총 개수를 구하면 되는 문제이다. 모든 컴퓨터를 하나씩 시작점으로 지정해보며 만약 아직까지 어느 네트워크에도 소속되지 않은 컴퓨터라면, 해당 컴퓨터를 시작점으로 BFS 로직을 수행해 같은 네트워크에 존재하는 모든 컴퓨터를 알아내기를 반복하면 된다. BFS 로직을 수행한 횟수가 곧 총 네트워크의 개수가 된다. 전체 코드 from collections import dequedef solution(n, computers): answer = 0 visited = [False] * n for start_v in range(..

2024년 7월 31일문제 링크 : 백준 2841번 - 외계인의 기타 연주문제상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다.예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 ..

2024년 7월 19일문제 링크 : 백준 2512번 - 예산문제  국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을..

2024년 7월 17일문제 링크 : 프로그래머스 - 베스트앨범 ※ 만약 2번, 15번 테스트케이스가 틀리셔서 찾아오셨다면, 다음 테스트케이스를 돌려보시기 바랍니다. genres = ["classic", "pop", "classic", "classic", "pop"]plays = [100, 500, 100, 100, 500]  문제 접근 문제에서 명시되어있듯, 핵심은 다음과 같다. 1. 각 장르마다 최대 2개의 노래를 앨범에 수록할 것이다.2. 속한 노래가 많이 재생된 장르를 먼저 수록할 것이며, 각 장르에서 가장 많이 재생된 노래를 먼저 수록할 것이다. 만약 같은 장르 내에서 재생 수가 같은 노래가 존재한다면 고유 번호가 낮은 노래를 먼저 수록한다.3. 모든 장르는 재생된 횟수가 다르다. 특히, 3번 덕..

2024년 7월 17일문제 링크 : 프로그래머스 - 다리를 지나는 트럭 문제 접근 문제의 핵심은 다음과 같다. 1. 다리 위에 있는 트럭이 다리를 건널 수 있으면 건너게 하고, 이후에 다리에 트럭이 올라올 수 있으면 다리 위로 트럭을 올림2. 다리를 건널 때, 트럭은 1초에 1만큼 이동한다고 가정하며, 다리의 길이가 n이라면 n초 후에 다리를 건너게 됨3. 다리가 버틸 수 있는 한계무게가 존재하며, 한계무게를 넘어서는 트럭은 기다려야 함  특히, 1번의 경우가 중요하다고 생각한다. 문제 예시를 보면, 다리 위에 트럭이 오르고 1초마다 1씩 움직여 최종적으로 트럭이 다리를 건널 수 있다면 다리를 건너게 한 이후에 다리에 트럭을 올릴 수 있는지 확인해야 한다. 문제에서 제시된 예시는 다음과 같다.  이 과정..

2024년 7월 15일문제 링크 : 백준 10971번 - 외판원 순회 2문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 ..