본문 바로가기

분류 전체보기101

[백준] 17472번 다리 만들기2 자바 문제 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 풀이 BFS+DFS+크루스칼 이렇게 세개를 각각 적용해서 풀었다. 문제는...더럽지만...그냥 저 3개의 알고리즘 연습하는 데는 나쁘지 않은 것 같다... 1. 각 섬들 네이밍 해주기 : 다리를 만드려면 섬이 다른 걸 알아야 하기 때문 → DFS이용 2. 각 섬을 이을 수 있는 다리의 최소비용 구하기 → BFS이용 : 이 때 다리는 한 방향으로만 나아갈 수 있기 때문에 상하좌우의 for문을 먼저 쓰고 각 방향에 대해 bfs적용 3... 2022. 4. 20.
[백준] 9935번 문자열 폭발 자바 문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 풀이 이 문제를 풀면서 자바의 String 관련 내장함수를 찾아보았는데, 생각보다 많은 함수들이 있었고 이걸 이용해서 문자열을 하나하나 탐색하고 갱신하면서 풀었다. - indexOf( ) : 문자열에서 특정 문자가 시작되는 인덱스 리턴 - substring(시작idx, 끝idx-1) : 문자열 중 특정 부분을 뽑아내 리턴 - startWith( ) : 문자열이 지정한 문자열로 시작하는지(인자값) - replaceAll( ) : 문자열 중.. 2022. 4. 20.
[백준] 23742번 Player-based Team Distribution 자바 문제 23742번: Player-based Team Distribution 플레이어 $N$명이 $1$개 이상의 팀으로 나누어 게임을 진행하려 한다. 플레이어는 각각 정확히 한 팀에 속해야 한다. $i$번째 플레이어는 같은 팀에 속한 인원 수와 $a_i$를 곱한 것만큼의 점수를 www.acmicpc.net 문제 풀이 일단, 양수팀은 인원이 많으면 많을 수록 그 배수로 늘어나므로 양수팀끼리 묶는다. 또, 팀은 1명 이상이기만 하면 되므로 음수는 각각 다 1인 팀으로 묶는다. 양수가 많이 큰 수 이면 음수를 데려와서 그 인원수를 곱했을 경우 기존 점수합보다 더 커질수도 있으므로 음수팀에서 음수값이 더 작은 플레이어를 데려와 양수팀과 합쳐서 점수합을 갱신해나간다. 이때, 음수는 -값이 작은 것부터 넘긴다. 왜냐.. 2022. 4. 18.
[백준] 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.

티스토리툴바