백준

[BOJ_4574] 스도미노쿠 (java)

문제링크 https://www.acmicpc.net/problem/4574 4574번: 스도미노쿠 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 www.acmicpc.net 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 재귀, 브루트포스, 백트래킹 스도미노쿠는 스도쿠 + 도미노를 의미하는 게임이다. 스도쿠의 규칙을 지켜주며, 도미노(2개의 쌍으로 이루어진 값)을 놓아주어 스도쿠를 풀어주는 문제이다. 도미노는 $(1,2), (1,3) (1,4) ... (7,8) (7,9) (8,9)$ 까지 1부터 9까지의 모든 값의 쌍으로 이루어져 있다. 그런데 $(1..

[BOJ_16197] 두 동전 (java)

문제링크 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 브루트포스, 재귀 문제는 두 동전을 보드판에 올려놓고 상하좌우 중 한 곳으로 이동시켜 주어 하나의 동전만 떨어뜨리는 방법을 구하는 문제이다. 단, 동전이 움직일 때 벽을 만나게 되면 움직이지 못하며, 그 외의 경우에는 모두 움직여 줄 수 있다. 떨어지는 경우는 동전이 보드의 배열 밖으로 나가는(범위를 벗어나는) 경우가 된다. 이 문제를 브루트포스로 ..

BOJ_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 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 브루트포스 연산자를 끼워 넣는 문제는 브루트포스로 해결하였다. 연산자의 개수는 숫자 배열의 크기 -1 이므로 최대 10개이다. 10개를 순서를 고려하여 나열하는 방법은 최대 10!이므로 시간초과 없이 해결할 수 있다. 따라서, 만들수 있는 모든 연산자의 경우의수를 만들어준 뒤 계산해 주면 쉽게 해..

[BOJ_16931] 겉넓이 구하기 (java)

문제링크 https://www.acmicpc.net/problem/16931 16931번: 겉넓이 구하기 크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다. 종이의 각 칸에 놓인 정육면체의 개수가 주어 www.acmicpc.net 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 시뮬레이션, 구현 겉넓이를 모두 구해주는 문제이다. 윗면과 아랫면 그리고 옆면으로 나누어 구현을 해주면 된다. 윗면과 아랫면 윗면과 아랫면의 겉넓이를 구하는 방법은 매우 간단하다. 조건에서 주어진 $n*m$에 블럭이 1개 이상 들어가야하므로 항상 넓이는 $n*m$이 된다. 옆면 옆면의 넓이를 구하는 방법은 4방면으로 붙어있는 도형을 확인하..

[BOJ_15685] 드래곤 커브 (Java)

문제링크 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 문제풀이 👨🏻‍💻 핵심 스킬 👨🏻‍💻 시뮬레이션 드래곤커브 문제를 봤을 때 굉장히 난해하다는 생각을 받았었습니다. 어떻게 그래프를 특정 점에서 90도씩 돌릴 수 있을까 고민을 많이 했는데, 생각해보니 그래프를 그릴 때 해당 점에서 어느 방향으로 이동하였는지만 알면 드래곤 커브를 구할 수 있었습니다. 드래곤 커브 문제는 특정 시작 점에서 시작 방향으로 1칸 이동하..

[BOJ_14499] 주사위 굴리기 (java)

문제링크 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제설명 더보기 더보기 더보기 문제 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 2 4 1 3 5..

[BOJ_2667] 단지번호붙이기 (java)

문제링크 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제설명 더보기 더보기 더보기 더보기 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 ..

[backjoon_11057] 오르막 수 (Java)

문제링크 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제설명 더보기 더보기 문제 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수..

[backjoon_2225] 합분해 (Java)

문제링크 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제설명 더보기 더보기 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 제한사항 제한시간 메모리제한 2초 128MB * 출처 : https://www.acmicpc.ne..

[backjoon_15990] 1,2,3 더하기 5(Java)

문제링크 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제설명 더보기 더보기 더보기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다. 1+2+1 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, ..

[Backjoon_11052] 카드 구매하기(Java)

문제링크 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제설명 더보기 더보기 문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 전설카드 레드카드 오렌지카드 퍼플카드 블루카드 청록카드 그린카드 그레이카드 카드는 카드팩의 형태로만 구매할..

[Backjoon_14391] 종이조각 (Java)

문제링크 https://www.acmicpc.net/problem/14391 문제설명 더보기 더보기 더보기 문제 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다. 영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다. 아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다. 각 조각의 합은 4..

[Backjoon_1182] 부분수열의 합(Java)

문제링크 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제설명 더보기 더보기 더보기 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 ..

[Backjoon_10971] 외판원 순회 2

문제링크 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제설명 더보기 더보기 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있..

[Backjoon_4375] 1 (Java)

문제 링크 https://www.acmicpc.net/problem/4375 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 요약 더보기 더보기 더보기 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성한다. 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. 1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다. 시간 제한 1초 메모리 제한 128MB 문제 풀이 n을 입력받아 n의 배수중 1로만 이루어진 가장 작은..

브루트포스(1) - 무작정 해보기

브루트 포스 알고리즘 모든 경우의 수를 해보는 알고리즘이다. 무작정 반복문을 돌려 구할 수도 있다. 브루트포스 알고리즘 예시 문제 : n이 주어졌을때, 1부터 n 중에 2의 배수의 수는? (1

최대, 최소공배수 그리고 소수

최대공약수(GCD) 두 수 a,b의 공통된 약수중 가장 큰 수 - 구하는 방법 1. 2부터 시작해서 a,b로 공통되게 나누어 떨어지는 것중 최대값을 구한다. O(n) -> n은 a,b중 최소값 2. 유클리드 호제법을 사용하기 // 나는 주로 재귀를 사용하는 편 public int gcd(int a, int b){ if(a%b == 0) return b; return gcd(a,a%b); } //반복문을 사용하여 구할수도 있음 public int gcd(int a, int b){ int temp; while(true){ if(a%b == 0) return b; temp = a % b; a = b; b = temp; } } 위 코드는 유클리드 호재법을 사용해서 구현해본 코드이다. 최소공배수(LCM) - 최소..

약수

약수를 구하는 방법 1. 1부터 n까지 %연산을 활용하여 구하기 2. 1부터 루트n까지 %연산을 활용하여 구하기 루트n까지만 비교해도 되는 이유는 약수는 짝을 지어 있기 때문이다. 약수의 개수가 홀수일 경우 root를 씌어준 값이 약수가 된다.(루트n까지 확인해야한다.) 시간복잡도 1번 방법 : O(n) 2번 방법 : O(√n) // 1번 방법 O(n) int n = 121; for(int i = 1; i