본문 바로가기

Baekjoon98

[백준] 2178번 미로 탐색 JAVA (자바) 풀이 문제 2178(BFS)  : N×M크기 미로 101111101010101011111011: 1 = 이동할 수 있는 칸  0 = 이동할 수 없는 칸 : (1, 1) ~ (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구해라  서로 인접한 칸으로만 이동할 수 있고 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다  [입력] :  첫째 줄에 두 정수 N, M (2 ≤ N, M ≤ 100) :  다음 N개의 줄에는 M개의 정수로 미로   [출력] :  첫째 줄에 지나야 하는 최소의 칸 수를 출력     [문제접근] 좌표 사용 시 int[] 나 Point 사용→ int[] 배열을 사용Queue q = new LinkedList();q.add(new int[] {x,y});→ Point 사용import.. 2024. 6. 4.
[백준] 10974번 모든 순열 JAVA (자바) 풀이 문제 10974번 (백트래킹)  :  1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성   [입력] :  첫째 줄에 N(1 ≤ N ≤ 8)  [출력] :   첫째 줄부터 N개의 줄에 걸쳐서 모든 순열을 사전순으로 출력   [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹   문제 조건 1) 숫자 중복금지  문제 조건 2) 수열 원소 오름차순   종료 조건) 배열이 M만큼 채워지면 출력하고 boolean false  N과 M(1) 문제와 비슷하다 방문기록을 체크해가며 숫자를 추가한다   [코드]import java.io.*;import java.util.*;public class Main{ static int N,arr[]; static boolea.. 2024. 5. 27.
[백준] 4134번 다음 소수 JAVA (자바) 풀이 문제 4134 (수학, 브루트포스)정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성   [입력]  :  첫째 줄에 테스트 케이스의 개수   :  정수 n ( 각 테스트 케이스는 한 줄 )       [출력] :  n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력    [참고]  소수 찾기 공식 2 ~ 제곱근까지 입력받은 수로 나눴을 때 나누어 떨어지지 않아야 소수!나누어 떨어진다면 입력받은 수에서 +1씩 올려 계산해보기 런타임 에러 피하기입력받은 숫자 n의 범위가 크기 때문에 long 타입으로 바꿔줄 것!  [코드] import java.io.*;import java.util.*;public class Main{ .. 2024. 5. 9.
[백준] 6603번 로또 JAVA (자바) 풀이 문제 6603번 (백트래킹)  :  {1, 2, ..., 49}에서 6개 택  :  k개(k>6) 골라 집합 S 만들어 6개의 조합 만들기   [입력] :  각 줄의 첫 번째 수는 k (6     (입력 마지막 줄 = 0)  [출력] :  각 테스트 케이스마다 경우의 수 출력 (사전 순 / 중복 금지)  :  각 테스트 케이스 사이에는 빈 줄 출력   [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹  문제 조건 1) 숫자 중복금지  문제 조건 2) 수열 원소 오름차순   종료 조건) 배열이 M만큼 채워지면 출력하고 boolean false  N과 M(2) 문제 응용버전이다  마찬가지로 boolean이 필요없다 현재 숫자보다 무조건 다음 인덱스의 숫자가 커져야 하기 때문에  굳이 .. 2024. 5. 4.
[백준] 15652번 N과 M(4) JAVA (자바) 풀이 문제 15652번 (백트래킹)  :  1부터 N까지 자연수 중에서 M개를 고른 수열 (중복선택 가능)  :  고른 수열은 비내림차순비내림차순 : A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK    (예) N = 3, M = 2 인 경우    1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다    1, 1 / 1, 2 / 1, 3 / 2, 2 / 2, 3 이렇게 만든 수열을 한줄에 하나씩 출력한다   [입력] :  첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8) [출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X)   수열의 원소는 공백으로 구분해서 출력  : 수열은 사전 순으로 증가하는 순서로 출력   [과정]  탐색하자 → 브루트포스 / dfs →.. 2024. 5. 4.
[백준] 15650번 N과 M(2) JAVA (자바) 풀이 문제 15650번 (백트래킹)  :  자연수 N과 M이 주어졌을 때,    1부터 N까지 자연수 중에서 중복 없이 M개를 골라서 수열 구하기  :  고른 수열은 오름차순        (예) N = 3, M = 2 인 경우    1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다    1, 2 / 1, 3 / 2, 3 이렇게 만든 수열을 한줄에 하나씩 출력한다   [입력] :  첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8) [출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X)   수열의 원소는 공백으로 구분해서 출력  : 수열은 사전 순으로 증가하는 순서로 출력   [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹  문제 조건 .. 2024. 5. 3.
[백준] 5568번 카드 놓기 JAVA (자바) 풀이 문제 5568  (백트래킹)  : 카드 n장 (4 ≤ n ≤ 10)   각 카드 1이상 99이하의 정수 : 카드 k장 (2 ≤ k ≤ 4) 선택 후 가로로 나란히 정수를 만들기 : 만들 수 있는 정수는 모두 몇 가지일까? [입력] : 첫째 줄에 n, 둘째 줄에 k: 셋째 줄 ~ n개 줄에는 카드에 적혀있는 수 [출력] : 만들 수 있는 카드 개수  [과정] 조합 중복 방지 vs 결과 중복 방지조합 중복 (백트래킹으로 해결)조합 중복 방지란 (1,1)이 아닌 (1,2)처럼 서로 다른 조합을 말한다 결과 중복 (hashset으로 해결)결과 중복 방지란 (1,2)와 (2,1)을 같은 값으로 처리하는 것을 말한다    [코드]import java.io.*;import java.util.*;public class.. 2024. 5. 3.
[백준] 1120번 문자열 JAVA (자바) 풀이 문제 1120 (문자열, 브루트포스) 길이가 N으로 같은 문자열 X와 Y X와 Y의 차이 = X [i] ≠ Y [i]인 i의 개수 (예, X = ”jimin”, Y = ”minji” 이면, 차이 = 4) 짧은 문자열 앞 혹은 뒤에 아무 알파벳 추가 연산을 반복해 문자열 길이를 같게 만든다 이때, 문자열 길이가 같으면서, 차이를 최소로 하는 프로그램을 작성해라 [입력] : 첫째 줄에 A, B 길이 ( 최대 50 / A 길이 ≤ B 길이 / 소문자 ) [출력] : 최소의 차이 출력 [참고] 규칙찾기 문자열 길이 차이 구하기 A문자열에 몇개의 알파벳을 더 붙여야 하는지 알기 위해서 문자열 길이 차이 = A 문자열 길이 만큼 다 순회하고 남은 개수 예를 들어 A = abc, B = eabcd 라면 처음엔 A의 .. 2024. 4. 16.
[백준] 1057번 토너먼트 JAVA (자바) 풀이 문제 1057 (수학, 브루트포스) 토너먼트 과정 1번부터 N번의 선수 중 서로 인접한 번호끼리 스타를 한다 이긴 사람은 다음 라운드에 진출하고 최후의 한 명이 남을 때까지 진행 라운드의 참가자가 홀수명일 경우, 마지막 번호는 다음 라운드로 자동 진출 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다 (처음 정해진 순서 유지하면서) 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정 김지민과 임한수가 몇 라운드에서 대결하는지 출력해라 [입력] : 첫째 줄에 참가자 수 N, 김지민과 임한수의 번호 입력 ( 2 ≤ N ≤ 100,000 자연수 ) [출력] : 김지민과 임한수가 대결하는 라운드 번호 출력 (서로 대결하지 않을 때, -1을 출력) [참고] 규칙찾기 홀수일 경우 다음 라운드 순번 N/2.. 2024. 4. 16.
[백준] 2003번 수들의 합2 JAVA (자바) 풀이 문제 2003 N개의 수로 된 수열 = A[1], A[2], …, A[N] 수열의 i ~ j번째 수까지의 합 = A[i]+ … + A[j] = M이 되는 경우의 수 [입력] : 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000) : 다음 줄에는 A[1], A[2], …, A[N] (공백으로 분리 & 각각의 A[x]는 30,000을 넘지 않는 자연수) [출력] : 경우의 수 출력 [참고] 기준숫자를 하나 잡고 합이 M될 때까지 for문 돌리기 check(j) = 시작 숫자 일단 j를 입력받으면 바로 이전 숫자들과 합부터 계산 수열 합이 M이 되면 count하고 for문 break 수열 합이 M을 넘어서면 바로 for문 break [코드] import java.io.*; i.. 2024. 4. 11.

티스토리툴바