알고리즘 문제풀이/프로그래머스
-
[프로그래머스/Level 3] 숫자 게임 (C++)알고리즘 문제풀이/프로그래머스 2021. 5. 7. 12:00
programmers.co.kr/learn/courses/30/lessons/12987 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 programmers.co.kr 제가 제일 어려워하는 유형 중 하나인 그리디 문제였습니다. 사실 다 약함 일단 입력값의 크기가 최대 100,000 이라서 완전탐색으로는 TLE가 발생합니다. 그래서 DP, 이분탐색, 힙, 그리디 다양하게 생각해봤는데 도저히 문제를 해결하지 못해서 풀이를 참고했습니다. A팀의 출전 순서가 이미 공개되어 A 배열은 고정 시켜야 한다는 고정관념에 사로잡혀 문제를 해결..
-
[프로그래머스/Level 3] 길 찾기 게임 (C++)알고리즘 문제풀이/프로그래머스 2021. 5. 7. 11:07
programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 카카오 기출 유형 이진트리를 구현하고 이를 통해 다양한 순회 방법을 구현할 수 있는지 물어보는 문제였습니다. 풀이 id=1 x=5,y=3 left=null right=null id=2 x=11,y=5 left=null right=null id=3 x=13,y=3 left=null right=null id=4 x=3,y=5 left=null right=null id=5 x=6,y..
-
[프로그래머스/Level 2] 행렬 테두리 회전하기 (C++)알고리즘 문제풀이/프로그래머스 2021. 4. 29. 15:45
programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 삼성 역량 테스트 기출문제였던 백준 17144번 미세먼지 안녕과 비슷한 문제였습니다. 입력받은 좌표중 첫번째 좌표를 tmp 변수에 저장한 후, 이를 기준으로 값을 한칸씩 계속 땡겨가며 회전 처리를 해주었습니다. 마지막 부분만 tmp를 덮어 씌어주면 됩니다. 이런 방법으로 회전 처리를 하고, 할 때마다 최소값을 갱신해가면 쉽게 문제를 해결할 수 있습니다. #i..
-
[프로그래머스/Level 1] 로또의 최고 순위와 최저 순위 (C++)알고리즘 문제풀이/프로그래머스 2021. 4. 28. 17:50
programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 처음에 map을 이용하는 줄 알고 해매느라 시간이 좀 오래걸린게 아쉬웠습니다. 풀이는 단순히 완전탐색을 통해 번호 같은 수 갯수를 찾고, lottos 배열의 값이 0인 갯수를 찾습니다. 최고 순위는 same(같은 갯수) + zero(0의 갯수), 최저 순위는 same(같은 갯수)가 됩니다. #include #include usin..
-
[프로그래머스/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..