꾸준함

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였습니다.일반적인 다익스트라 알고리즘처럼 가중치를 더해나가는 것이 아니라 등산로 내 최대 가중치를 업데이트하는 방식으로 코드를 작성해야 했습니다.  개발환경: Programmers IDE   지적, 조언, 질문 환영합니다! 질문 남겨주세요~

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 저는 다익스트라 알고리즘을 통해 푼 문제인데 정석 풀이를 보면 플로이드-와샬 알고리즘으로 푼 문제였습니다. 일단 제가 푼 코드를 기반으로 설명을 진행하고 추후에 플로이드-와샬 코드도 올리도록 하겠습니다. 알고리즘은 아래와 같습니다. 1. 시작점 s를 기준으로 다익스트라 알고리즘을 진행하고 그 결과를 sDistance에 저장합니다. 2. [1, n] 지점을 순회하며 각 지점을 기준..

문제 링크입니다: https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재석이는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2

문제 링크입니다: https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입 www.acmicpc.net 기존에 풀었던 다익스트라 문제들과는 달리 2차원 행렬을 입력받아 풀어야했던 문제였습니다. 전형적인 ..

문제 링크입니다: https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때 www.acmicpc.net 현재 알고리즘 스터디를 진행할 때 파트가 다익스트라 알고리즘과 세그먼트 트리이기 때문에 이 두 알고리즘을 중점적으로 업로드..

문제 링크입니다: https://www.acmicpc.net/problem/16528 다익스트라(Dikjstra) 문제인데 조금 꼬아서 낸 문제였습니다.전형적인 다익스트라 문제와 다르게 '고속도로 유지 비용'이라는 변수도 추가되었습니다. 알고리즘은 아래와 같습니다.1. 고속도로 유지 비용이 추가되었기 때문에 pair 대신 Edge 구조체를 정의해줍니다.-> 우선순위 큐를 사용할 것이기 때문에 < 연산자도 정의해줍니다.a) 거리가 가까울수록b) 거리가 같다면 가격이 저렴할수록c) 우선순위가 높습니다.2. 전형적인 다익스트라 알고리즘을 진행합니다.i) e.city에서 next.city로 가는 거리가 기존에 저장된 거리보다 가깝다면 거리를 업데이트하고 유지 비용도 업데이트해주고 우선순위 큐에 해당 정보를 넣어..

문제 링크입니다: https://www.acmicpc.net/problem/1504 V1과 V2를 꼭 지나야하므로 아래와 같은 두 가지 경우를 고려해야합니다.1. 1 -> V1 -> V2 -> N2. 1 -> V2 -> V1 -> N 따라서, 다익스트라 알고리즘을 1, V1, V2에 대해 전부 수행한 뒤 1번과 2번 중 최소인 경우를 출력합니다.또한, 경로가 존재하지 않는 경우 -1을 출력해야하는데 987654321을 3번 더해주면 int 오버플로우가 발생하므로 answer가 INF 이상이거나 0 미만일 때 -1을 출력하도록 처리해줘야합니다. #include #include #include #include #include #include using namespace std; const int MAX = ..

문제 링크입니다: https://www.acmicpc.net/problem/11779 전형적인 다익스트라 문제에 경로까지 파악하는 문제였습니다.학교에서 자료구조를 배울 때 지하철 경로 구하기 문제와 동일한 문제였기 때문에 쉽게 풀 수 있었습니다.경로는 거리를 업데이트할 때마다 경로도 업데이트하며 스택 개념을 이용해 구하면 됩니다! #include #include #include #include #include #include using namespace std; const int MAX = 1000 + 1; const int INF = 987654321; int N, M; int trace[MAX]; //경로 파악 위해 vector graph[MAX]; vector dijkstra(int start, i..

문제 링크입니다: https://www.acmicpc.net/problem/5901 다익스트라 알고리즘을 이용해 푸는 문제였습니다. 알고리즘은 아래와 같습니다.1. 장터가 있는 마을을 입력받고, 해당 마을에 장터가 있다고 표시합니다.2. 양방향 그래프를 입력받고 각각의 마을에 대해 다익스트라 알고리즘을 통해 최단경로를 계산합니다.3. 어디에 거주를 할지 모르기 때문에 모든 경우의 수를 파악합니다.i) next_permutation을 이용하여 K! 순열을 확인합니다.ii) 처음과 끝은 해당 거주지로부터 출발하므로 양 끝 경로도 더해서 계산해야합니다.iii) ii) 중 최소의 값이 정답입니다. #include #include #include #include #include #include using name..

문제 링크입니다: https://www.acmicpc.net/problem/5719 알고리즘 자체를 구상하는데는 큰 어려움이 없는 문제입니다.1. 우선, 다익스트라 알고리즘을 통해 source->destination까지의 최단 경로를 구합니다.2. 해당 최단 경로를 삭제합니다.3. 다시 다익스트라 알고리즘을 통해 source->destination까지의 최단 경로를 구합니다. 1번은 http://jaimemin.tistory.com/555에서 이미 다익스트라 알고리즘을 구현한 적이 있기 때문에 쉽게 할 수 있었지만 2번이 문제였습니다.최단 경로를 어떻게 삭제할지 고민하다가 crocus님의 블로그(http://www.crocus.co.kr/682)를 참고한 결과 BFS를 이용해 최단 경로를 삭제할 수 있다..