알고리즘 & 자료구조/문제 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 처음에 2차원 DP + DFS로 접근했지만 2차원으로는 해결할 수 없는 문제가 있었다. 그래서 해당 접근은 보류하고 처음부터 다시 생각했고, 방향에 따라서 간선의 가중치가 달라진다는 점과 최단 거리를 구해야한다는 점을 토대로 다익스트라 알고리즘을 사용해서 문제를 풀었다. 이 문제는 진행 방향에 따라서 도로 건설 비용이 달라질 수 있음을 고려해주어야 한다. 아래는 문제에서 설명을 위해 첨..

풀이 만약 a, b, p, q 가 다음과 같다고 한다면 [3, 9, 2, 3] a(3) : b(9) = p(2) : q(3)를 만족해야 한다. (여기서 a, b의 값은 재료의 질량이다) 즉 pb * x == qa * y를 만족해야 한다. 그럼 (lcm은 최소공배수, gcd는 최대공약수이다) x = lcm / pb = (qa * pb) / gcd / pb = qa / gcd = 1 y = lcm / qa = (qa * pb) / gcd / qa = pb / gcd = 2 위처럼 x, y를 구할 수 있다. 그런데 이때 x, y에 최대공약수가 존재할 수 있다. 우리는 최소가 되는 결과값을 원하기 때문에 최대공약수가 있다면 해당 값으로 나누어줘야 한다. 따라서 x, y의 gcd를 구하여 나누어준다음 다른 비율들..

이 문제를 풀면서 어려웠던 건.. 이 문제가 DP가 맞는가? 였다. 요즘 (DP, 그리디, 브루트포스) 종류의 문제를 만나면 갈피를 잡지 못하는 것이 가장 힘들다. 배낭 문제라는 사실을 알았을 땐, 아.. 그치 배낭 문제지..라고 금방 이해되지만 혼자서 그 생각을 해내는 게 가장 어려운 것 같다. 이 문제는 최근에 만난 DP 문제들처럼 약간의 응용이 필요하다. 문제의 목표는 M이상의 메모리를 확보하면서 가장 적은 Cost를 사용하는 것이 목표이다. 그렇다면 DP 관계(?)를 설정할 때 다음과 생각해 볼 수 있다. DP 배열은 2차원 배열로 구성하고 배낭 문제 처럼 접근한다고 하자. 그렇다면 1, 2 선택지 중에 어떤 것을 골라야할까? DP[앱의 index][앱의 memory] 로 구성 DP[앱의 inde..

개 킹 받는 매개변수 탐색 문제 풀이를 자세하게 작성해보았다. 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러 개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈칸을 사이에 ..

외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다. 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 ..

바이러스 조건에 대한 설명이 참 부족한 문제 같다. 굉장히 많은 사람들을 혼란하게 만든 듯.. 나도 참 이해가 안됐었는데 이렇게 생각하니까 그나마 이해가 됐다. 1. 우리가 구하고자 하는 건 빈 공간에 바이러스가 퍼지는 시간이다. 즉 ( 2 == 활성, * == 비활성, 0 == 빈 공간) 2 0 0 * 이라면, 답은 2초이다. 2. 비활성 바이러스가 활성 바이러스가 되는 데 걸리는 시간은 1초가 맞다. 즉 2 0 * 0 이라면, 답은 3초이다. 3. 비활성 바이러스가 활성 바이러스가 되는데 걸리는 시간은 이런 경우에 고려할 필요가 없다. 즉 2 * * * 이라면, 답은 0초이다. 왜냐하면 승원이가 구하고자 하는 시간은 "빈" 공간에 바이러스(비활성, 활성 상관없음)를 전파시키는데 걸리는 시간이기 때문이..