알고리즘 문제풀이/프로그래머스
-
[프로그래머스/Level 2] 순위 검색 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 8. 16:40
programmers.co.kr/learn/courses/30/lessons/72412 s[0] >> s[1] >> s[2] >> s[3] >> num; getCombi(stoi(num)); } for(auto &s : scores) { sort(s.second.begin(), s.second.end()); } for(auto &q : query) { int score; stringstream ss(q); ss >> s[0] >> num >> s[1] >> num >> s[2] >> num >> s[3] >> num; score = stoi(num); vector v = scores[s[0] + s[1] + s[2] + s[3]]; if(v.size() != 0) { auto it = lower_boun..
-
[프로그래머스/Level 3] 섬 연결하기 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 5. 17:22
programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 다익스트라를 이용하여 해결하였습니다. 다만 시작점에서 각 정점까지의 누적 최단거리가 아니라, 해당 노드를 한번만 지나고 그 값이 최단거리가 되어야 합니다. 이렇게 되면 시작점이 어디냐에 따라 최소값이 다르게 나올 수 있기 때문에, 시작점을 0부터 n까지 모두 진행해보면서 어떤 시작점으로 다익스트라를 시작할 때 최소값을 구할 수 있는지 알아내야합니다. 테스트케이스 예 4, [[0, 1, 5], [0, 2, 3], [1, 2, 1], [1, 3, 2], [2, 3, 4]] : ..
-
[프로그래머스/Level 3] 네트워크 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 4. 23:20
programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 처음 DFS 진입이 몇번 일어나는지 구하면 되는 문제입니다. #include #include using namespace std; bool visit[201]; void DFS(vector computers, int idx, int n) { for(int i = 0; i < n; i++) { if(!visit[i] && computers[idx][i] == 1) { vi..
-
[프로그래머스/Level 3] 풍선 터트리기 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 4. 17:48
programmers.co.kr/learn/courses/30/lessons/68646 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 예전에 문제를 해결하지 못해서 다른 풀이를 참고하여 글을 정리했는데, 다시 풀어보니 기존 방식이 이해가 안가서 해당 블로그를 참조하여 새롭게 풀이를 정리합니다. 각 자리 풍선이 최후까지 남아있는지 확인 하기 위해서 현재 위치가 i라고 했을 때, (0 ~ i - 1)의 최소값과 (i + 1 ~ 끝)의 최소값을 비교합니다. 현재 위치의 풍선보다 왼쪽과 오른쪽의 풍선이 둘다 작으면 해당 풍선은 최후까지 남아있을 수 없습니다. (인접한 풍선 중 번호가 더 작은 걸 최대 1번만 터트릴 수 있..
-
[프로그래머스/Level 3] 2 x n 타일링 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 3. 12:56
programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 백준의 11726번과 동일한 문제입니다. #include using namespace std; int dp[60001]; int solution(int n) { dp[1] = 1; dp[2] = 2; for(int i = 3; i
-
[프로그래머스/Level 2] 피보나치 수 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 1. 16:52
programmers.co.kr/learn/courses/30/lessons/12945 코딩테스트 연습 - 피보나치 수 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = programmers.co.kr #include #include #include using namespace std; int dp[100001]; int F(int n) { if(dp[n] != -1) return dp[n]; if(n..
-
[프로그래머스/Level 3] 등굣길 (C++)알고리즘 문제풀이/프로그래머스 2021. 1. 29. 14:48
programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 각각의 좌표는 해당 좌표를 갈 수 있는 경우의 수를 의미한다. 학교를 기준으로 왼쪽과 위에서 계속 합쳐지면서 경우의 수가 구해진다. (위의 그림을 보면 이해가 갈 것이다.) 이를 통해 얻을 수 있는 점화식은 다음과 같다. dp[n][m] = dp[n - 1][m] + dp[n][m - 1] #include #include using namespace std; int..
-
[프로그래머스/Level 3] N으로 표현 (C++)알고리즘 문제풀이/프로그래머스 2021. 1. 29. 13:14
programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr DP 유형의 문제이지만 DFS를 이용한 완전탐색으로 해결한 문제 +N, -N, *N, /N +NN, -NN, *NN, /NN +NNN, -NN, *NN, /NN .... 반복적인 작업을 통해 만약 N을 사용한 갯수(cnt)가 9이상이라면 가지를 뻗지 않고 리턴, 위의 작업을 하며 만들어진 수(sum)이 number와 같다면 최소값을 갱신해줍니다. #include #include using namespace std; int answer = 9, N, Number; void DFS(int now, int cnt) { if(cnt >= 9) return; if..