🔗문제 보러가기 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 👨‍💻풀이 과정 세그먼트 트리(Segment Tree) 첫 입문 문제로 풀었습니다. 첫 시도고, 조금 변형된 문제인지라 결국 다른 분들의 풀이를 참고하여 풀었지만, 세그먼트 트리라는 개념과 어느정도 친숙해진 그런 계기가 아니었나 싶습니다. 백준 문제를 풀면서 느낀 거지만, 다양한 알고리즘 문제들을 접해볼 수 있다는 게 되게 좋은 것 같습니다. 아직 접해보고 풀어봐야 할 문제들이 많지만 하나씩 천천히 해봐야죠...

🔗문제 보러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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 ..

🔗문제 보러가기 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 👨‍💻풀이 과정 위상 정렬과 다이나믹 프로그래밍을 통해 풀었습니다. 처음에는 DFS로 풀 수 있을 것 같단 생각에 도전하려고 했는데, 중복되는 계산이 너무 많아 시간 초과가 날 것 같단 생각이 들어 그 풀이는 포기했습니다. 아무튼, 제가 어떻게 풀었는지 천천히 설명해 드리도록 하겠습니다. 1. 간선 정보 및 진입 차수 설정 하위 부품에서 상위 부품으로 간선이 가리키도록 방향을 설정하였고, 필요한 부품 개수 정보도 같이 ..

🔗문제 보러가기 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 🧑‍💻풀이 과정 기본적인 틀은 다익스트라 알고리즘인데, 최단 경로에 해당하는 각 도시들 번호를 어떻게 저장할 지가 문제였습니다. 분기가 이루어지는 각 경로마다 자기가 거쳐 온 도시 정보를 가지고 있을까 생각했다가, 메모리가 너무 많이 들 것은 물론 복사 비용이 만만치 않을 것 같아 포기했습니다. 그래서 결국 다른 분의 풀이를 참고했는데, 배열을 통해 이전 노드로 가는 길을 추적하는 참신한 방법을 사용하여 푸셔서 놀랐..

🔗문제 보러가기 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 🧑‍💻풀이 과정 위상 정렬을 사용해 풀 수 있는 문제인데, 사이클(Cycle) 감지 조건을 하나 더 넣어야 하는 문제입니다. 순서를 정하는 게 불가능한 경우는 각 가수들의 순서에 사이클이 있는 경우가 됩니다. 이는 모든 노드를 돌기 전에 큐(Queue)가 비었을 경우로 탐지 할 수 있습니다. ✏️소스 코드 및 결과 #include #include #include using namespace std; #define FAST_IO..