전체

백준 14889번 스타트와 링크 [ Java ]

14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 두 팀으로 나누기 위해 백트래킹 함수를 N과M (4)와 같은 방법으로 작성했습니다. 4가지인 경우는 인덱스 기준으로 (0,1) (2,3) , (0,2) (1,3) , (0,3) (1,2) , (1,2) (0,3) , (1,3) (0,2) , (2,3) (0,1) 이런식으로 세어지고 start 배열을 정했을 때 나머지를 세어주는 형식으로 link 배열을 만들었습니다.

백준 14888번 연산자 끼워넣기 [ Java ]

14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. www.acmicpc.net dfs를 이용해서 모든 경우를 탐색하는(브루트 포트) 문제였습니다.

백준 2580번 스도쿠 [ Java ]

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 잔 실수가 많아서 하나하나 디버깅 하는 과정이 오래걸렸습니다.

백준 1018번 체스판 다시 칠하기 [ Java ]

1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 좌표 하나를 기준으로 8x8씩 확인해 나가는 것을 모든 좌표를 해야해서 메소드로 따로 해주었고 BW의 구별은 boolean으로 최솟값을 찾는것은 stack에 넣어서 정렬후 제일 첫 번째 인덱스(최솟값)을 출력해주었습니다.

백준 15624번 피보나치 수 7 [ Java ]

15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 동적계획법으로 푸는데 메모리가 너무 커 배열을 이용하면 안되고 0번째의 경우도 처리해주어야 했습니다.

백준 11051번 이항 계수 2 [ Java ]

11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 고등학교때 배우는 파스칼 삼각형의 원리를 알고 있다면 금방 생각나는 점화식 입니다. nCr = n-1Cr-1 + n-1Cr

백준 9461번 파도반 수열 [ Java ]

9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하 www.acmicpc.net 피보나치 수열과 유사합니다.

백준 1904번 01타일 [ Java ]

1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수 www.acmicpc.net 이전에 풀었던 문제랑 같은 점화식이라서 a(n) = a(n-1) + a(n-2) 초항만 변경해서 풀었습니다.

백준 11726번 2xn 타일링 [ Java ]

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 규칙성 찾아서 점화식을 세우는 DP문제 입니다.

백준 1152번 단어의 개수 [ Java ]

1152번: 단어의 개수 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다. www.acmicpc.net 입력 받은 값들을 띄어쓰기를 기준으로 쪼개서 배열에 저장해주었습니다. 저장하는 과정에서 공백으로 시작할 경우 빈 배열이 생기는 현상이 있어서 따로 처리해주었습니다. 그리고 공백만 입력되는 경우도 따로 처리해주었습니다.