Algorithm/BOJ42 [백준] 20365번 블로그2 자바 문제 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 문제 풀이 어차피 연속된 색깔은 한 번에 가져와서 처리할 수 있으므로 연속된 색깔을 묶어줘야 한다. 'BBRBRBBR' → 'BRBRBR' 로 생각해서 처리해도 된다는 말이다. 처음에 char배열을 이용해서 첫 값을 넣고 그 뒤 값부터 반복을 돌면서 문자가 다를경우에만 체크해서 배열에 넣어줬다. 근데 생각해보니 어차피 연속되지 않으니까 무조건 brbr... 또는 rbrb...이런식으로 갈텐데 굳이 문자를 다시 압축해서 가지고 있을 필요가 없었음.. 따라서 .. 2022. 4. 20. [백준] 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. 이전 1 2 3 4 5 6 7 다음