🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑🏻‍💻 풀이 과정 [1차 시도] 다익스트라 알고리즘 (실패) 출발지(s)로부터 각 노드에 대한 최단 경로 배열을 구해놓고, 각 노드(i)마다 다익스트라 알고리즘을 돌려서 s👉🏻i + i👉🏻a + i👉🏻b 값들 중 최솟값을 구하는 방식으로 풀었습니다. 노드의 개수(N)가 최대 200개라 될 줄 알았는데 효율성 테스트에서 시간 초과가 나더군요. [2차 시도] 플로이드 워셜 알고리즘 (성공) 매 노드마다 다익스트라 알고리즘을 돌린 것이 원인이라 생각되어, 모든 노드 간의 최단 경로를 구할 수 있는..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑‍💻풀이 과정 다익스트라 알고리즘을 활용하여 풀었습니다. 목적지(Destination)를 시작점으로 하여 각 지역에 대한 최단 거리 배열을 구하고, 출발지(source)들에 해당하는 값들을 answer 배열에 담아주었습니다. 만약 어떤 출발지의 최단 거리 값이 초깃값과 같다면, 그 지역은 못 간다는 의미이므로 -1을 담아주면 되구요. 또한, 모든 지역 간의 이동 비용이 1이므로, 우선순위 큐 대신 일반 큐를 활용하여 시간을 줄였습니다. ✏️소스 코드 및 결과 #include #include ..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻풀이 과정 제 문장 독해력에 하자가 있는건진 몰라도, 처음에 문제 읽고 무슨 소리지 했었습니다. 핵심은 셔틀 버스 운행 횟수인 \(n\) 번 내에 사무실에 갈 수 있는 가장 늦은 시간을 고르는 것이었네요. 단순 구현 문제이긴 한데, 시간과 관련된 문제는 항상 계산 부분에서 주의를 기울여야 하는 것 같습니다. 일단은 계산하기 쉽게, string을 int로 변환하는 작업을 먼저 해보죠. 1. String 👉🏻 Int로 변환하는 함수 작성 주어지는 시간은 "HH:MM" 형태를 띄고 있다고 문제..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑‍💻풀이 과정 🔗최소 신장 트리(MST, Minimum Spanning Tree)를 활용하는 문제입니다. 최소 신장 트리를 구축하는 과정에서 크루스칼(Kruskal) 또는 프림(Prim)의 알고리즘이 사용되며, 저는 크루스칼(Kruskal)의 알고리즘을 사용하여 풀었습니다. 신장 트리의 조건 중 하나로 사이클이 있으면 안된다가 있는데, 분리 집합(Disjoint set)의 개념인 🔗유니온 파인드(Union Find)라 불리는 자료구조로 쉽게 점검할 수 있습니다. 이번 기회에 공부하여 개념을 ..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑‍💻 풀이 과정 처음엔 다익스트라(Dijkstra) 알고리즘을 먼저 떠올렸는데, BFS로도 간단하게 풀 수 있겠단 생각이 들어 BFS로 풀었습니다. 알고리즘은 다음과 같습니다. 행 번호는 노드의 번호, 열 번호는 행 번호 노드와 연결된 다른 노드들의 번호로 이루어진 2차원 배열을 선언한다. 1번 노드를 방문 처리 후 Queue에 넣고, BFS 탐색을 시작한다. Queue에서 노드(source)를 꺼낸 후, 해당 노드와 연결된 다른 노드들을 방문 처리 후 Queue에 넣는다. 이 때, sour..

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🧑‍💻풀이 과정 문제를 보자마자 양 쪽에 인덱스를 가리키는 변수 2개를 두고 구간을 줄여가며 구해야겠다고 생각했는데, 이게 투 포인터(Two pointer) 알고리즘이더군요. 몰랐지만 자연스럽게 사용하게 되었습니다..? 풀이 방식은 다음과 같습니다. gems 배열을 순회하며 보석의 종류 개수를 알아낸다. 시작 인덱스(start)와 끝 인덱스(end) 변수를 각각 0으로 두고, 보석의 종류 개수를 다 포함하는 구간이 될 때까지 end를 증가시킨다. 보석의 종류를 모두 포함하는 가장 작은 구간까지..