민규의 흔적

2024년 6월 7일문제 링크 : 백준 1504번 - 특정한 최단 경로  문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.입력첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) ..

2024년 6월 7일문제 링크 : 프로그래머스 - 줄 서는 방법 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 접근 n이 주어졌을 때, 1 ~ n 까지 모든 수의 조합을 오름차순 정렬하여, k번째 조합을 찾는 문제이다. n에 대한 모든 경우의 수를 구해 k번째 조합을 구하면 큰일난다.n의 최대값은 20이며 시간복잡도는 O(n!), 가능한 조합의 수는 20!로 이는 2,432,902,008,176,640,000 ~= 10^19인 아주 큰 수다. 시간복잡도 말도 안된다.. 이 문제를 해결하기 위해서는 해당 큰 문제를 작은 문제로 쪼갤 수 있는지 접근해보아..

2024년 6월 7일문제 링크 : 프로그래머스 - 스킬트리 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 접근 스킬을 배우는 순서가 CBD라면, C를 배워야 B를 배우고 B를 배워야 D를 배울 수 있다. 딕셔너리를 선언하여 스킬을 key, 배우는 순서를 value로 지정하였다.이게 가능한 이유는 스킬이 중복되지 않기 때문.  검증해보는 스킬트리를 앞에서부터 탐색하며 딕셔너리의 배우는 순서와 비교해본다.아직 배울 수 있는 순서가 아닌데 스킬을 배우려고 한다면 가차 없이 탐색을 종료하고, 스킬트리의 맨 마지막 스킬까지 탐색하여 유효함이 검증된다면 가능한 ..

2024년 6월 7일문제 링크 : 프로그래머스 - 2개 이하로 다른 비트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 접근 주어진 10진수 x와 x보다 큰 모든 수들 중, 2진수로 변환했을 때 비트가 1~2개 다른 수 중 가장 작은 수를 구하는 문제이다. 예를 들어, x가 4일 때, 이를 2진수로 바꾸면 100⑵이며, x보다 큰 수는  5, 6, 7 ... 등등 많지만각각 2진수로 변환하면 101⑵, 110⑵, 111⑵ ... 와 같다. 이러한 x보다 큰 수들 중, 2진수로 변환했을 때 x의 2진수 변환 수보다 비트가 2개 이하로 다른 수 중 가장 작..