https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 난이도 최단거리 / 난이도 ⭐️⭐️⭐️/ 1.5시간 문제풀이 최단거리 문제이다. 다익스트라 알고리즘을 알고있으면 쉽게 풀 수 있으나, 몰라서 오래걸렸다. #include #include #include #include #include #define INF 1000000000 using namespace std; int solution(int n, vector edge) { int answer = 0; vector vertex(n+1..
https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 난이도 완전탐색 / 난이도 ⭐️/ 10분 문제풀이 #include #include using namespace std; vector solution(int brown, int yellow) { vector answer; // 1 24 => 26*2 + 3*2 - 4 = 54 // 2 12 => 8 + 28 - 4 = 32 // 3 8 => 10 + 20 - ..
#include #include #include #include using namespace std; // 10^7 bool comp(const string p1, const string p2){ if(p1.size() < p2.size()){ return true; }else{ return false; } } bool solution(vector phone_book) { bool answer = true; sort(phone_book.begin(), phone_book.end()); int pattern_size; for(int i=0; i< phone_book.size() - 1; i++){ if(phone_book[i]

https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 난이도 해시(map) / 난이도 ⭐️⭐️(시간복잡도 때문에 +1) / 15분 문제풀이 선수의 수 10^5 완전탐색) 10^5 * 10 ^ 5 * 20 이중 포문O(n^2)으로 풀이할 경우 10^12로 100 억이다. 시간 초과에 걸린다. 보통 알고리즘 문제에서 1억(1초)을 마지노선이라고 생각하고 풀이해야한다. 해시) map 자료구조의 경우 ..
https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 난이도 DFS(에라토스테네스의 체 + DFS + set) / 난이도 ⭐️⭐️⭐️ / 50분 문제 풀이 소수를 찾는 알고리즘만 알고 있으면 쉽게 풀 수 있는 문제이다. 1) 소수찾는 함수를 만들기 2) 숫자카드로 만들 수 있는 가장 큰 숫자를 구한 뒤, 에라토스테네스의 체 알고리즘을 통해 가장 큰 숫자 까지의 소수를 가진 배열은 만든다. 3) dfs..
https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 문제풀이 DFS / 난이도 ⭐️ / 30분 처음에 읽었을때 위상정렬 생각이 났지만 그래프가 순환하기 때문에 불가능하다는걸 깨달았다. airport별로 map에 알파벳 순으로 정렬된 vector를 저장하여 풀었다. vector를 넣을 때부터 정렬해서 넣어줬기 때문에 가장 처음 만들어진 경로가 정답이다. 함정은 ["COO", "BO..
https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 풀이 DFS or 비트연산 / 난이도 ⭐️ / 15분 재귀 또는 비트연산으로 풀 수 있다. 비트연산 풀이가 익숙하지 않은 경우, dfs를 활용하면 된다. 정답 풀이1 (재귀) #include #include using namespace std; int result = 0; void dfs(vector &..