알고리즘 문제풀이/프로그래머스
-
[프로그래머스/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..
-
[프로그래머스/Level 2] 게임 맵 최단거리 (C++)알고리즘 문제풀이/프로그래머스 2021. 3. 25. 11:08
programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 전형적인 BFS 문제였습니다. #include #include using namespace std; int N, M; vector Maps; bool visit[101][101]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; struct Info { int x, y, t;..
-
[프로그래머스/Level 1] 2016년 (C++)알고리즘 문제풀이/프로그래머스 2021. 3. 16. 10:09
programmers.co.kr/learn/courses/30/lessons/12901 코딩테스트 연습 - 2016년 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까 programmers.co.kr 별다른 설명없이 주석을 통해 문제를 이해할 수 있을 것 같습니다. #include #include using namespace std; string solution(int a, int b) { int total = 0; // 1일이 금요일인데 배열의 인덱스는 0번부터 시작하므로, "THU" 부터 초기화 string day[7] = {"T..
-
[프로그래머스/Level 1] 신규 아이디 추천 (C++)알고리즘 문제풀이/프로그래머스 2021. 3. 7. 14:58
programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 카카오 기출 문제 해결을 위해 알아두면 좋을 것 1. 대문자 소문자 변형이 필요할 때, transform() 함수를 사용한다. 2. 문자열에서 알파벳을 찾을 때, isalpha() 함수를 사용한다. 3. 문자열에서 숫자를 찾을 때, isdigit() 함수를 사용한다. 4. 문자열에서 특정 문자를 찾을 때, strchr() 함수를 사용한다. 문자열을 이용한 구현 문제였습..
-
[프로그래머스/Level 3] 멀리 뛰기 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 27. 21:36
programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 기초 DP 문제였습니다. dp[n]을 n칸을 오르기 위한 경우의 수로 정의하고, 이에 대한 점화식을 세우면 됩니다. 1칸과 2칸 이동을 할 수 있으므로, n칸에 도착하는 방법은 n-1칸을 오르는 경우의 수에 1칸을 오르거나, n-2칸을 오르는 경우의 수에 2칸을 오르면 됩니다. 따라서 점화식은 dp[n] = dp[n -..
-
[프로그래머스/Level 3] 스타 수열 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 26. 01:15
programmers.co.kr/learn/courses/30/lessons/70130 코딩테스트 연습 - 스타 수열 programmers.co.kr 1. map을 통해 원소들의 빈도 수를 구하기 2. map의 key를 교집합으로 설정하고, 이때 만들 수 있는 최대 스타 수열의 길이는 value(빈도 수) * 2 3. a의 배열의 a[i], a[i + 1] 값을 비교하고, 이 값들이 key와 같은지 비교하며 조건을 맞추기 4. 조건을 통과하면 현재 스타 수열의 길이는 2씩 갱신하고, 다음 비교를 위해 i++ 처리 5. 현재 key를 교집합으로 스타 수열이 길이를 구했으면 최대값을 갱신, 위를 계속 반복하기 #include #include #include #include using namespace std..
-
[프로그래머스/Level 3] 야근 지수 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 25. 16:36
programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 문제에서 야근 지수를 최소화 하기 위해서는 작업량의 최대값을 매번 줄여가야합니다. 이러한 최대값을 구하기 위해서 우선순위 큐를 이용한다면, 문제를 쉽게 해결할 수 있습니다. #include #include #include using namespace std; long long solution(int n, vector works) { long long answer..