민규의 흔적

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월 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 시작하기 앞서, 그리디 알고리즘에 대해 간단히 짚고 넘어가겠다. (문제 풀이만 보고 싶다면 아래로 넘어가도 무방하다.) 그리디 알고리즘 탐욕법, 탐욕 알고리즘이라고도 하며, 결과를 도출하기 위해 효율적일 것 같은 방법으로 솔루션을 구하는 알고리즘이다. 최적의 해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 다음 그래프를 ..

2024년 6월 8일문제 링크 : 프로그래머스 - 타겟 넘버 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 접근 n개의 수가 주어지면, n개의 " + " 혹은 " - " 연산자를 적절히 섞어 사용해 target과 일치하는 경우가 총 몇 가지 인지 구하는 문제이다. 연산자는 2종류 이므로, n이 최대 20일 때 최악의 경우의 수는 2^20 = 1,048,576로 완전탐색해도 되겠다 싶었다. n이 5일 때를 생각해보면 다음과 같이 모든 경우의 수를 생각할 수 있다.  실제 트리처럼 구현하지는 않았지만, 어떻게 풀까 고민하다 그림을 그려보고 백트래킹으로 접..

2024년 6월 8일문제 링크 : 프로그래머스 - 괄호 변환 [2020 KAKAO BLIND RECRUITMENT] 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 접근 카카오 다운 복잡한 구현 문제이다. 이런 문제는 알고리즘적 접근보다는, 문제를 정확히 이해하고 키워드를 뽑아낸 후 문제가 요하는 바를 빠짐 없이 체크해야 한다. 균형잡힌 괄호 문자열, 올바른 괄호 문자열 균형잡힌 괄호 문자열이란, 특정 괄호 문자열의 구성 요소 "(" 와 ")"의 개수가 일치하는 문자열을 뜻한다. " (()) " , " ())( ", " )( " 모두 균형잡힌 괄호 문자열..

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로 지정하였다.이게 가능한 이유는 스킬이 중복되지 않기 때문.  검증해보는 스킬트리를 앞에서부터 탐색하며 딕셔너리의 배우는 순서와 비교해본다.아직 배울 수 있는 순서가 아닌데 스킬을 배우려고 한다면 가차 없이 탐색을 종료하고, 스킬트리의 맨 마지막 스킬까지 탐색하여 유효함이 검증된다면 가능한 ..