알고리즘 문제풀이
-
[프로그래머스/Level 3] 합승 택시 요금 (C++)알고리즘 문제풀이/프로그래머스 2021. 4. 22. 14:38
programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 카카오 기출 문제 다익스트라를 통해 시작점에서부터 합승 거리의 최소 비용을 구하고, 다시 한번 다..
-
[프로그래머스/Level 2] 괄호 회전하기 (C++)알고리즘 문제풀이/프로그래머스 2021. 4. 16. 14:29
programmers.co.kr/learn/courses/30/lessons/76502 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 문자열 s의 크기만큼 괄호를 왼쪽으로 한칸씩 회전하면서 스택을 이용하여 올바른 괄호인지 검증하는 문제였습니다. #include #include #include using namespace std; // 괄호를 왼쪽으로 한칸 회전 string rotate(string str) { string res = str; char tmp = res[0]; res.erase(0, 1); res.push_back(tmp); return res; } // 올바른 괄호인지 검증 bool isCorrect(string str) { stack st; for(int i = 0;..
-
[프로그래머스/Level 1] 음양 더하기 (C++)알고리즘 문제풀이/프로그래머스 2021. 4. 16. 14:26
programmers.co.kr/learn/courses/30/lessons/76501 코딩테스트 연습 - 음양 더하기 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 re programmers.co.kr signs 벡터의 값이 false인 경우, 동일한 인덱스의 absoulutes 값을 음수로 바꿔 더해주면 되는 간단한 문제입니다. #include #include using namespace std; int solution(vector absolutes, vector signs) { int answer = 0; for(int i = 0; i < sign..
-
[프로그래머스/Level 3] 최고의 집합 (C++)알고리즘 문제풀이/프로그래머스 2021. 4. 15. 14:31
programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만 programmers.co.kr 곱이 최대가 나오기 위해서 집합 원소들간의 차이가 최소가 되어야 합니다. 따라서 연산을 줄이기 위해서, 먼저 합s와 원소 개수n을 나눈 몫으로 집합을 채웁니다. 그래서 만약 s % n이 0이 아니라면, 집합 원소들간의 차이를 최소로 만들기 위해서 n-1번째 원소부터 나머지 크기만큼 1씩 더하면 최고의 집합을 만들 수 있습니다. #include #inc..
-
[백준/BOJ] 1436번 영화감독 숌 (C++)알고리즘 문제풀이/백준 2021. 4. 12. 15:57
www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 완전 탐색, 브루트 포스 문제였습니다. 해당 블로그를 참고하여 해결했습니다. 0. 665 1. 666 2. 1666 3. 2666 4. 4666 5. 5666 6. 6660 7. 6661 .... title 값을 665로 초기화하고, 이를 반복문에서 1씩 더한 값을 문자열로 변환하여 "666"을 포함할 때마다 cnt를 증가시켜 N과 같아질 때 종료하게끔 구현하면 되는 문제입니다. #include using n..
-
[프로그래머스/Level 3] 줄 서는 방법 (C++)알고리즘 문제풀이/프로그래머스 2021. 4. 12. 14:39
programmers.co.kr/learn/courses/30/lessons/12936 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr next_permutation이나 DFS를 이용하여 모든 순열을 구해서 문제를 해결하면 효율성 테스트를 통과할 수 없습니다. 따라서 찾으려는 특정 순열만 바로 찾을 수 있게끔 구현해야합니다. 문제의 예제를 가져와 풀이를 설명해보도록 하겠습니다. n = 3, k = 5의 조건을 가지고, 1~3의 숫자로 만들 수 있는 순열의 경우의 수는 다음과 같습니다. 그리고 여..
-
[프로그래머스/Level 2] 배달 (C++)알고리즘 문제풀이/프로그래머스 2021. 4. 6. 09:44
programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 다익스트라 알고리즘을 이용하여 해결할 수 있는 문제였습니다. 1번 정점에서의 각 정점까지의 모든 최단 거리를 구하고, K보다 작거나 같은 정점의 개수를 구하면 됩니다. #include #include #include using namespace std; vector graph[51]; int dist[51]; void D(int node) { prio..
-
[백준/BOJ] 17070번 파이프 옮기기 (C++)알고리즘 문제풀이/백준 2021. 3. 28. 16:36
www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 삼성 A형 기출문제 : DFS 파이프는 오른쪽, 아래, 대각선 아래로 이동할 수 있고, 파이프가 놓여있는 경우에 따라 취할 수 있는 액션이 달라집니다. 파이프가 가로로 놓여있는 경우 오른쪽으로 이동 대각선 아래로 이동 파이프가 세로로 놓여있는 경우 아래로 이동 대각선 아래로 이동 파이프가 대각선으로 놓여있는 경우 오른쪽으로 이동 아래로 이동 대각선 아래로 이동 파이프의 움직임을 dx[]..