hwooo

https://www.acmicpc.net/problem/11779   풀이다익스트라를 이용해 출발-도착 도시 간의 최소 비용을 구했다.현재 저장된 비용은 다른 노드들에 의해 갱신되므로 큐에 저장된 비용보다 작을 수 있다. 이런 경우는 실행하지 않아야 이미 방문했지만 큐에 남아있던 도시를 재방문하는 경우를 막을 수 있다. 최소 비용의 경로를 구하기 위해, 해당 도시의 직전 도시를 저장해서 경로를 저장했다.경로는 도착도시부터 시작해서 거슬러 올라갔으며, 출발 도시의 직전 도시는 출발 도시의 값으로 저장해두어현재 도시 != 직전도시일 때까지 올라가며 저장 후 출력했다.코드import java.io.BufferedReader;import java.io.IOException;import java.io.Input..

https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이헤어지는 지점을 어떻게 잡아야 할 지 모르겠어서 다른 분들의 접근방식을 참고했다.모든 분기에서 헤어진다는 가정 하에 path[s][node] + path[node][a] + path[node][b]의 최솟값을 구하면 된다.s, a, b 지점은 고정되어 있지만 헤어지는 node가 다 다르므로 플로이드-와샬 알고리즘을 이용하여 모든 노드 간의 최소 거리를 구했다.이후 모든 분기점을 node 지점으로 지정하며 최소값을 구했다.C/C++ 코드#in..

https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이규칙을 찾아봤으나 규칙이 없고, user는 100명 이내, emoticons의 길이는 최대 7이다.이 경우 emoticon 하나당 적용할 수 있는 할인율은 0% ~ 40%까지 총 5가지이므로 모든 경우의 수를 확인해도  200만이 되지 않아 완전탐색으로 답을 구했다.C/C++ 코드#include #include #include using namespace std;int percents[5] = {0, 10, 20, 30, 40};int s..

https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이dfs로 현재 방문하지 않은 노드를 확인한 후, 해당 노드와 연결된 모든 노드들을 방문처리 한다.위의 작업을 할 때마다 네트워크의 개수를 늘려가며 네트워크를 찾는다.C/C++ 코드#include #include using namespace std;bool visited[200] = {false, };void dfs(vector>& computers, int n, int now) { visited[now] = true; for (i..

https://leetcode.com/problems/group-anagrams/ 풀이주어진 문자열을 알파벳 순으로 정렬한 후 이를 key로 가진 map을 하나 만든다. 문자열들을 순회하며 알파벳 순으로 정렬한 후, 해당 값과 같은 key가 있다면 해당 value에 값을 추가하고, 아니라면 map에 해당 쌍을 추가한다.C/C++ 코드class Solution {public: vector> groupAnagrams(vector& strs) { unordered_map> sorted; for (string& s : strs) { string tmp = s; sort(tmp.begin(), tmp.end()); sorte..

https://school.programmers.co.kr/learn/courses/30/lessons/43164# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이처음엔 알파벳 순으로 정렬한 후 BFS로 탐색했으나, 이렇게 탐색할 경우 답이 없는 경우를 파악하기 어려웠다.그래서 다른 사람의 풀이를 본 후, 알파벳 순으로 정렬 후 DFS로 탐색하며 답이 아니라면 백트래킹으로 탐색하는 방법을 사용했다.C/C++ 코드#include #include #include using namespace std;bool visited[20001];vector answer;bool dfs(vector>& tickets..

https://leetcode.com/problems/rotate-image/description/ 풀이결과적으로 봤을 때 한 번에 네 군데의 값이 바뀌므로바깥쪽 바퀴부터 안쪽까지 순회하며 각 라인의 값을 저장한 후 한 번에 바꿨다.C/C++ 코드class Solution {public: void rotate(vector>& matrix) { int size = matrix.size(); int leftIdx = 0, rightIdx = size - 1; int l, r, u, d; while (leftIdx r -> d -> l for (int i = leftIdx; i  Java 코드class Solution { pub..

https://leetcode.com/problems/combination-sum/description/풀이후보의 수가 적고, 특정 규칙을 찾을 수 없어 모든 경우를 탐색했다.재귀로 순회하며 모든 경우를 확인한 후, target일 경우의 수 집합을 저장한다. 이 때 중복을 제외하기 위해 현재 원소의 인덱스를 함께 넘겨 해당 위치부터 순회하도록 구현했다.C/C++ 코드class Solution {public: vector> combinations; void findCombinations(vector& candidates, int& target, vector nowCombination, int nowSum, int idx) { if (nowSum == target) { ..