알고리즘 문제풀이
-
[프로그래머스/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,..
-
[백준/BOJ] 10422번 괄호 (C++)알고리즘 문제풀이/백준 2021. 2. 22. 17:45
www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net DP 유형의 문제, 카탈린 수의 개념을 알고 있어야 함! 카탈린 수의 점화식은 아래와 같습니다. #include using namespace std; long long dp[2501]; // n쌍의 올바른 괄호를 만들 수 있는 경우의 수 int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int T, L; long long answer; dp[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원을 사용하는 경우가 중복되어서 나오는 경우가 발생합니다. 따라..
-
[백준/BOJ] 12869번 뮤탈리스크 (C++)알고리즘 문제풀이/백준 2021. 2. 19. 23:38
www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net DP 유형의 문제입니다. 처음에 단순히 문제의 입력값의 크기만 보고 BFS로 판단하여 문제를 풀다가 메모리 초과가 발생했습니다. 그래서 Top-Down 방식으로 접근하여 SCV의 체력이 음수가 되는 경우 인자를 0으로 바꿔 다시 재귀 탐색 처리를 해주고, 최소값을 메모이제이션을 통해 저장 후, 리턴하였습니다. #include #include #include using namespace std; int a[3], n; i..
-
[프로그래머스/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. 17. 23:35
programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr 카카오 기출 어려운 구현 문제였습니다. 문제 해결의 아이디어는 기둥과 보가 존재하는지 각각 2차원..
-
[프로그래머스/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)이 같은 경우에만 다음 탐색을 진행하게끔 구현..
-
[백준/BOJ] 12886번 돌 그룹 (C++)알고리즘 문제풀이/백준 2021. 2. 15. 15:20
www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net BFS 유형의 문제입니다. 메모리 초과로 인해 해당 블로그를 참고하여 문제를 해결했습니다. 포인트는 숫자가 3개로 고정되어 있기 때문에, 배열을 2개만 사용해도 된다는 점이었습니다. #include #include #include using namespace std; int a, b, c, d; bool visit[501][501]; // 숫자가 3개로 고정, 따라서 배열을 2개만 사용해도 된다. (3개 사..