민규의 흔적

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]) ..

2024년 6월 13일문제 링크 : 백준 2667번 - 단지번호붙이기 문제  과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.입력첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 ..

2024년 6월 11일문제 링크 : 백준 11723번 - 집합 문제   비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)all: S를 {1, 2, ..., 20} 으로 바꾼다.empty: S를 공집합으로 바꾼다.입력첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이..

2024년 6월 11일문제 링크 : 프로그래머스 - 구명보트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 접근 문제에서 주어진 조건들 중, 가장 중요한 정보는 다음과 같다. 1. 구명보트는 한 번에 최대 2명만 탈 수 있다.2. 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없다.  limit가 100인데, 사람의 몸무게가 120인 경우는 없다는 뜻이다. 이러면 고려해야 할 사항이 줄어들어 생각하기 편하다. 그리디하게 접근해, 최대한 많은 사람을 태우려면 가장 무거운 사람 + 가장 가벼운 ..

2024년 6월 10일문제 링크 : 프로그래머스 - 큰 수 만들기 문제 접근 주어진 숫자 number에서 k개의 수를 제거하여 도출될 수 있는 가장 큰 수를 구하면 된다. 이는 아주 그리디하게 접근 가능하다.최대한 큰 수가 앞자리 수에 오도록 유도하는 것이다.이에 나는 스택 구조를 활용하여, 최대한 앞자리에 오는 작은 수를 먼저 없애는 것에 초점을 두었다. 1924를 예로 보자.  k는 2이고, 가장 첫 번째 자리수는 1이다.stack이 비어있기에 비교할 대상이 없어 now를 append 해준다.  now는 9이고, stack의 마지막 요소는 1이기에 맨 앞 자리수에 1보단 9가 오는게 수가 더 클 것이다.이에 stack의 마지막 요소가 now보다 크거나 같은 값일 때까지 pop 하며 k를 1씩 감소시킨..

2024년 6월 10일문제 링크 : 프로그래머스 - 조이스틱 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 시작하기 앞서, 그리디 알고리즘에 대해 간단히 짚고 넘어가겠다. (문제 풀이만 보고 싶다면 아래로 넘어가도 무방하다.) 그리디 알고리즘 탐욕법, 탐욕 알고리즘이라고도 하며, 결과를 도출하기 위해 효율적일 것 같은 방법으로 솔루션을 구하는 알고리즘이다. 최적의 해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 다음 그래프를 ..