본문 바로가기

자바

 (73)
[백준] 14889 스타트와 링크 (JAVA) https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 이 문제를 처음 보았을때는 개인적으로는 실버3 같이 느껴지지 않았다. 나는 처음에 사람들의 집중하기보다는 점수들의 조합에 집중해서 어려웠던것 같다. 알고리즘의 개요는 다음과 같다. 모든 사람들의 조합을 구하고 각 조합당 낼수있는 시너지들의 총합을 구하고 이를 스타트와 링크로 나누너 계산해 가장 작은값을 출력하면 된다. 자세한것은 코드를 보면서 이해가 될것이다. import java.io.BufferedReader..
[백준] 15650 N과 M (2) (JAVA) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 이 문제는 저번에 풀었던 N과 M (1)문제에서 오름차순이 추가되었다는것을 제외하고는 전부 동일하다. 그래도 다시한번 더 설명을 해놓을테니 혹시라도 이러한 문제를 처음풀거나 여전히 어려운 사람들은 보기 바란다. 이 문제는 DFS와 비슷한 백트래킹을 사용한다. 여기서 백트래킹이 무엇이냐 하면 유망하지않은 노드는 선택하지 않는다는것이다. 예를 들어 이번에 포스팅하는 문제를 예시로 들어 설명을 ..
[백준] 14888 연산자 끼워넣기 (JAVA) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 이 문제는 저번과 마찬가지로 백트래킹에 대해 알고있다면 어떠하게 풀지 감이 오는 문제였다. 나는 처음 이문제를 접하였을때 매경우 최적의 경우를 찾아내는 방법이 있는줄 알고 고민하였으나 브루트 포스라는 카테고리를 보고 그냥 전부 돌리기로 생각했다. 여기서 변수는 숫자의 개수를 나타내는 N, 최대값 MAX 최소값 MIN, 숫자들을 담을 ar..
[백준] 15649 N과M(1) (JAVA) 풀이 이 문제는 예전에 풀었던 N-queen과 동일한 백트래킹문제이다. 실버3의 낮은 난이도에 속하는데 백트랙킹의 기본 원리를 알면 쉽게 풀수있다. 백트래킹은 DFS와도 비슷한데 다른점이라면 DFS와는 다르게 해당 노드가 유망하지 않으면 취하지 않는다는 것이라는것이다. 이 문제에서 위의 말을 적용하면 만약 앞서 수열에서 이미 선태한 수가 있다면 선택한 수는 제외하고 순회를 한다는 것이다. 그리 어렵지 않은 코드니 보면 쉽게 이해할수있을듯 하다. 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.util.Str..
[백준] 9663 N-Queen (JAVA) 풀이 위의 문제는 백트랙킹의 기초적인 문제라고 할수있겠다. 이 문제를 접하게 된 경로는 solved에서 문제를 풀다 백트랙킹 문제를 맞닥뜨려 풀려고 하였으나 관련문제를 풀어본적이 없어 풀지를 못했다. 이러한 내 자신에거 실망을 하여 백트랙킹의 기초문제를 풀려고 찾아보았고 가장 기초적인 문제를 찾아서 풀었다. 문제는 크기가 n x n인 체스판에서 퀸을 몇개나 놓을수 있냐는 문제이다. 이러한 방식은 마지 스택을 이용한 미로찾기 처럼 하면되는데 미로찾기에서는 이차원의 배열을 만들어 사용했다면 여기서는 1차원의 배열을 이용해 열을 index값으로, 행을 원소값으로 생각하여 풀면 된다. 자세한것은 아래의 코드를 보면 될듯하다. 코드 import java.util.Scanner; class Main{ public ..
[백준] 2156 포도주 시식 (JAVA) https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 이 문제는 계단오르기와 비슷한 유형의 문제이다. 우선 이전 포스팅에서도 말했듯이 현재 위치에서의 연속된 수를 구해서 풀이를 하는것이 아닌 경우를 나눠서 진행해야한다. 그러나 계단오르기와 다른점이 있다면 마지막 포도주는 선택을 안해도 된다는 것이다. 여기서 나는 조금 헤매었는데 결국은 dp중 최대값을 계속해서 선택을 하면 된다는 것이다. dp[x] = Math.max(Math.max(find(x..
[백준] 2579 계단 오르기 (JAVA) https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 나는 DP에 자신있다고 생각했는데 오만이였다. 나는 문제에 접글할때 재귀가 아닌 반복문으로만 생각을 하였고 이는 나를 오답으로 이끌었다. 사실 약 5달전에 풀어보았던 문제지만 다시 공부를 하며 풀어보았다. 그러나 생각대로 풀리지는 않았다. 조금더 공부에 신경을 써야 할것 같다. 알고리즘에 대하여 알아보기전 풀이에 도움을 받은 블로그에 대해서 링크를 남기겠다. https://st-lab.tistory.co..
[백준] 1932 정수 삼각형 (JAVA) https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 이 문제는 전형적인 DP로 DP를 조금 풀어보았더라면 쉽게 해결할수있는 문제이다. 알고리즘의 개요는 이러하다. 위에서부터 내려오는 방식과 밑에서부터 올라가는 방식이 있는데 나는 밑에서부터 올라가는 방식을 사용해서 문제를 해결했다. 우선 DP라는 2차원 배열과 ary이라는 2차원배열을 생성후 입력값을 ary에 저장한다. 그러고 난뒤 가장 ary의 가장 아랫부분을 dp에 저장하고 그 다음에는 다음과 같은 식을 수행한다 dp[i][j] = ary[i][j] + Math..
[백준] 1697 숨바꼭질 (JAVA) 풀이 처음에 이 문제를 보고 어떠한 규칙을 찾기위해 노력을 했었다. 그러다 문득 바이너리 서치처럼 한번에 하나씩 하면 될것 같다는 생각이 들어 바이너리 서치로 접근을 해보았다. 그러나 바이너리 서치는 +1-1 *2중 무엇이 최적인지 몰랐고 그리디 알고리즘도 맞지 않았다. 그리하여 어떻게 하면 좋을까 생각을 하다 그냥 시간 생각하지말고 무작정 시간을 더하면 되지않을까? 라는 생각을 하게 되었고 그러한 생각을 꾸준히 하다보니 단순히 +1, -1, *2를 해서 특정배열에 담으면 될것 같다는 생각을 하게 되었고 이는 곧바로 정답으로 가게 되었다. 풀이의 발상은 단순하다 만약 현재의 위치가 x라면 x-1, x+1 x*2의 위치에 현재의 시간+1을 더하고 queue에 집어넣는것이다. 그러고 전부 끝나면 현재 que..
[백준] 7576 토마토 (JAVA) 풀이 이 문제는 이 전에 풀었던 미로탐색(2178)과 궤를 같이 하는 문제이다. 나는 미로탐색처럼 간단할줄 알고 덤볐으나 생각할게 조금있었다. 우선 이 문제에서는 시작점이 주어지지 않았으며 하루가 지날때 마다 영향을 받는 토마토는 다양해서 조금 더 생각한것 같다. 그리고 반복문을 생각보다 많이 돌려 문제를 풀면서 시간초과를 많이 신경 썼다. 알고리즘은 다음과 같다. 처음에 box라는 2차원 배열에 토마토의 위치등을 저장할때 토마토가 있는 곳들, 즉 1로 입력값이 주어지는 위치는 바로바로 큐에 집어넣었다. 그리고 저장이 전부 끝난후에는 바로 BFS함수로 들어가서 그래프 탐색을 진행하였다. 참고로 왜 DFS가 아닌 BFS를 사용했는지 궁금하다면 https://goto-pangyo.tistory.com/23 ..

티스토리툴바