알고리즘 문제풀이/백준
-
[백준/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] ..
-
[백준/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. 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차원..
-
[백준/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개 사..
-
[백준/BOJ] 9251번 LCS (C++)알고리즘 문제풀이/백준 2021. 2. 14. 20:44
www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 새롭게 알게된 점 LCS의 개념을 알게됨 DP 유형의 문제, 위의 링크를 참고하여 해결했습니다. #include using namespace std; int dp[1001][1001]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); string s1, s2; cin >> s1 >> s2; for(int..
-
[백준/BOJ] 14502번 연구소 (C++)알고리즘 문제풀이/백준 2021. 2. 10. 14:34
www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 삼성 역량 테스트 기출 문제 : DFS + BFS 벽을 3개씩 세우는 모든 경우의 수는 DFS를 통해 구현하고, 이렇게 세워진 벽에서 바이러스가 퍼져나갔을 때 안전영역의 최대 개수는 BFS를 통해 구하도록 구현하였습니다. #include #include #include using namespace std; int n, m, answer; int map[9][9]; int dx[4] = {-1, 0, 1, 0}; int dy..
-
[백준/BOJ] 16948번 데스 나이트 (C++)알고리즘 문제풀이/백준 2021. 2. 9. 21:56
www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net BFS를 통해 해결할 수 있는 간단한 문제였습니다. #include #include #include using namespace std; int n, r1, c1, r2, c2; int map[201][201]; int dx[6] = {-2, -2, 0, 0, 2, 2}; int dy[6] = {-1, 1, -2, 2, -1, 1};..
-
[백준/BOJ] 16928번 뱀과 사다리 게임 (C++)알고리즘 문제풀이/백준 2021. 2. 8. 22:51
www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net BFS 유형의 문제입니다. 뱀과 사다리 부분의 구현이 추가된 것 빼고는 숨바꼭질 2와 비슷해서 쉽게 해결했습니다. #include #include using namespace std; int n, m; int map[101]; bool visit[101]; vector r, s; int dx[6] = {1, 2, 3, 4, 5, 6}; int snakeOrLadde..