본문 바로가기

Algorithm65

[백준] 23741번 야바위 게임 자바 문제 23741번: 야바위 게임 첫 번째 줄에 정점 수 $N$, 간선 수 $M$, 게임 시작 시 공이 놓여있는 정점 번호 $X$, 공이 든 컵이 움직인 횟수 $Y$가 주어진다. ($1 \leq N, Y \leq 10^3$, $1 \leq M \leq 10^4$, $1 \leq X \leq N$) 다음 줄부터 $M$ www.acmicpc.net 문제 풀이 dfs+dp 문제. 처음에 dfs로만 했다가 시간초과떴다. dfs로는 시작 정점에서 움직인 횟수를 카운트하면서 모든 경우에 대해 도착 지점을 확인한다. dp로는 해당 지점과 같은 카운트를 가지고 온 경우는 처리하지 않도록 표시해둔다. DP[i][j] = i노드의 j번의 횟수로 가는 모든 경우를 처리 했는가? → true DFS에서는 해당 노드와 카운트를 .. 2022. 4. 17.
[백준] 9012번 괄호 자바 문제 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 풀이 처음 보자마자 스택이 떠오르긴 했는데 구현 과정에서 굳이...? 라는 생각이 들어서 여는 괄호 "(" 를 판별하는 인덱스 변수 하나를 이용해서 풀었다. 여는 괄호가 나올 때마다 idx++ 해주고, 닫는 괄호가 나오면 idx-- 해준다. 이 때, idx가 음수가 되면 여는 괄호가 나오지도 않고 닫는 괄호가 나온 것이기 때문에 바로 break를 수행한다. 소스 코드 public class b_9012 { public s.. 2022. 4. 14.
[백준] 1904번 01타일 자바 문제 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 풀이 N의 증가에 따라 결과값을 잘 생각해봐야 dp임을 알 수 있다. N=1의 경우, 1 -> 1 N=2의 경우, 00, 11 -> 2 N=3의 경우, 001, 100, 111 -> 3 N=4의 경우, 0011, 0000, 1001, 1100, 1111 -> 5 .... 쭉 보면 N(i) = N(i-1) + N(i-2) 의 점화식으로 도출할 수 있다. 그 이유는 짝수개일 때와 홀수 개일 때 00 또는 1을 붙여서 가져오면 되기 때문이다. 소스 코드 publ.. 2022. 4. 13.
[백준] 1937번 욕심쟁이 판다 자바 문제 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제 풀이 dfs와 dp의 조합..! 처음에 dp생각 못하고 dfs로만 모든 경우 구하면서 max값 갱신하다가 시간초과가 떴다. 왜 dp를 생각못했을까..ㅠ int[][] visited 배열 하나 선언해두고, 해당 칸에서 갈 수 있는 길이를 저장해둠으로써 좀 더 효율적인 로직을 만들 수 있다. ✔️dfs 알고리즘 1. 해당 칸 방문이 되었으면 그 값 바로 리턴 2. 그렇지 않으면 1로 초기화 후, 상하좌우로 이동하면서 현재 값을 최대로 갱신한다... 2022. 4. 7.
[백준] 11055번 가장 큰 증가 부분 수열 자바 문제 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 풀이 구글링했다. 역시 DP는 너무 어려워.. 어떻게 이런 방법으로 풀 생각을 하지 라고 생각했다.. 알고리즘은 반복문을 돌면서 dp배열에 현재 인덱스까지의 최대 배열 합을 갱신해나가면서 배열을 채우고 가장 큰 값을 반환하면 되는 거였다. 코드에서 의문이었던 점은 현재 i번째의 배열 값과 그 전까지의(j) 배열 값들을 확인하는 반복문에서 i까지의 값이 증가되는 것을 확인하지 않고 그 j의 값 자.. 2022. 3. 17.
[프로그래머스] 자물쇠와 열쇠 자바 문제 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 문제 풀이 1. 행렬 좌표값 받아 둘 Point 클래스 선언 //좌표 클래스 class Point { int r, c; public Point(int r, int c) { this.r = r; this.c = c; } } 2. key의 돌기, lock의 홈 좌표를 받아둘 두 개의 ArrayList 생성 - lockList - keyList 3. lockList : r, c가 작은 값부터 정렬 4. keyList는 각도 회전이 가능하므로 총 4가지 방법으로 정렬을 함 - r↑ c↑ - r↑ c↓ - r↓ c.. 2022. 3. 8.

티스토리툴바