알고리즘 문제풀이/프로그래머스
-
[프로그래머스/Level 3] 불량 사용자 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 24. 17:08
programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 카카오 인턴 기출 카카오 기출문제였던 순위검색처럼 banned_list와 매칭될 수 있는 user_id의 모든 경우의 수를 비트 연산을 이용해서 구하려고 시도했는데, 올바른 접근 방법이 아니었던 것 같습니다. 두 아이디의 길이, 그리고 *이 아니고 다른 문자가 같은지를 통해 해당 아이디가 불량 사용자의 후보가 될 수 있는지 확인하고, 이를 DFS를 통해 모든 경우의 수를 구합니다..
-
[프로그래머스/Level 2] 방문 길이 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 24. 14:25
programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr DP 문제인줄 알았는데 단순 구현 문제였습니다. 이전 문제와는 다르게 visit배열을 4차원으로 선언하여 점이 아닌 간선의 방문을 체크해야합니다. 또한 어느 방향으로 특정 간선을 지나던 해당 간선은 완전히 방문되었다고 처리하므로, 양방향으로 방문했다고 처리해줘야합니다. 그리고 좌표의 시작점이 (0, 0)이고 범위는 (-5, -5) ~ (5, 5) 인데, 간선의 방문을 체크하기 위해 인덱스를 음수를 사용할 수 없기 때문에, 시작점의 좌표를 (5, 5)로 옮기고, 범위를 (0, 0) ~ (10, 10)으로 위와 같이 수정하였습니다. 마지막으로 배열에서는 (0,..
-
[프로그래머스/Level 3] 거스름돈 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 22. 16:50
programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr DP 유형의 문제 dp[n]의 점화식을 'n원을 만들 수 있는 조합의 수'로 정의합니다. 여기서 조합의 수라고 정의한 이유는 동전을 더하는 순서에 따라 답이 달라질 수 있기 때문입니다. 예를들어 1, 2, 5 종류로 3원을 만들 때, 다음과 같이 1+1+1 = 3 2+1 = 3 1+2 = 3 1원과 2원을 사용하는 경우가 중복되어서 나오는 경우가 발생합니다. 따라..
-
[프로그래머스/Level 3] 가장 긴 팰린드롬 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 18. 00:27
programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr DP를 이용하여 팰린드롬의 길이가 가장 긴 경우를 찾는 문제입니다. 예전에 풀었던 백준 10942번을 참고했습니다. #include using namespace std; bool dp[2501][2501]; int solution(string s) { int answer = 1; for(int i = 0; i < s.siz..
-
[프로그래머스/Level 3] 보행자 천국 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 16. 16:33
programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr DFS와 DP를 이용하여 해결한 문제입니다. 문제의 조건 중, '2번' 사항을 구현하는 것이 약간 어려움을 겪었고, 결국 다른 풀이를 보며 힌트를 받아 코드를 작성했습니다. dp 저장 배열을 3차원으로 선언하고, 현재 좌표를 기준으로 값이 2일 때, for문으로 진행하는 방향(i)과 DFS를 진행하면서 저장된 이전 방향(z)이 같은 경우에만 다음 탐색을 진행하게끔 구현..
-
[프로그래머스/Level 3] 순위 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 15. 14:11
programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 플로이드 와샬을 이용하는 문제였습니다. 해당 알고리즘을 이용하여 모든 정점에서 다른 정점으로 갈 수 있는 여부(경기 결과를 알 수 있는지)를 확인합니다. 예를들어 a->b이고 b->c이면 a->c 가 된다는 것을 의미합니다. n = 5, [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 가 입력값으로 주어졌을 때, 플로이드 워셜을 이용하면 다음과 같이 배열이 완성됩니다. 출/도 1 2 3 4 5 1 false true false false true 2 fals..
-
[프로그래머스/Level 3] 이중우선순위큐 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 10. 13:51
programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 최소 힙과 최대 힙 두개를 이용하여 구현하였습니다. 구현은 두개의 힙을 이용했지만, 실제로는 하나의 힙을 이용하는 것이므로, 현재 남은 원소의 개수를 기록할 cnt 변수를 두는 것이 핵심이었습니다. #include #include #include #include using namespace std; vector solution(vector operations) { vector answer; int cnt = 0; priority_queue minPq; // 최소 힙 priority_queue maxPq; // 최대 힙 for(auto o : operat..
-
[프로그래머스/Level 3] 디스크 컨트롤러 (C++)알고리즘 문제풀이/프로그래머스 2021. 2. 9. 17:45
programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 우선순위 큐를 이용하여 비선점 SJF 스케줄링을 구현하는 문제였습니다. #include #include #include #include #include using namespace std; int solution(vector jobs) { int answer = 0, idx = 0, time = 0; // idx : jobs의 인덱스, time : 현재 실행시간 // 작..