본문 바로가기

분류 전체보기

 (308)
[백준] 1011 Fly me to the Alpha Centauri (JAVA) https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 풀이 처음 보았을떄 어렵게 느껴져서 곰곰히 생각하다 스스로 반복문으로 해서 풀었다. 하지만 왜인지는 모르겠으나 오답처리가 되었고 다른 블로그를 보았다. 이번 문제의 경우는 카테고리가 수학이였는데 이러한 문제들을 풀때는 혼자 암산을 하거나 끄적거리면서 풀었는데 앞으로는 암산이 아닌 표형태로 풀어봐야 할것 같다. 풀이는 위의 블로그를 참고하였다. 코드 pa..
[백준] 1759 암호 만들기 (JAVA) https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 풀이 이 문제는 기존의 백트래킹문제를 풀어보았다면 쉽게 풀리는 문제였다. 기존의 백트래킹의 문제(N과M문제 시리즈들)들과는 다른점이라면 이번 1759번 암호만들기는 숫자가 아닌 문자가 주어졌다는 것이다. 하지만 그 뿐일뿐 숫자가 문자로 바뀌었다는것을 제외하고서는 전부 동일하다 사전식으로 출력을 한다든지 아니면 어떠한 조건이 있는 점이 말이다. 알고리즘의 개요는 다음과 같다 우선 입력값으로 L C값을 입..
[백준] 5639 이진 검색 트리 (JAVA) https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 이 문제는 기본적인 BST이다. 필자는 이전에 학교에서 BST를 배웠는데 그때는 c언어로 해서 그렇게 크게 어렵지 않았다. 그러나 지금은 자바로 해서 c언어로 할때보다 새로운 느낌이었다. 아무튼 문제의 풀이를 하자면 자바에서는 포인터의 개념이 없기 떄문에 다음과 같이한다. 1. node라는 클래스를 만들고 attribute로는 값을 저장하는 num과 왼쪽과 오른쪽 자식을 가리키게..
[백준] 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..

티스토리툴바