본문 바로가기

baekjoon52

[백준] 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.
[백준] 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.
[백준] 1018번 체스판 다시 칠하기 JAVA (자바) 풀이 문제 1018 M x N 크기 보드 (검정색 & 흰색) 보드를 잘라서 8 x 8 크기의 체스판으로 만들기 체스판 규칙 : 검적생 흰색 번갈아서 칠할 것 잘라낸 보드 판을 체스판 규칙에 맞게 다시 칠해야 하는 최소 횟수를 구하시오 [입력] : 첫째 줄에 N과 M ( 8보다 크거나 같고 50보다 작거나 같은 자연수) : 둘째 줄부터 N개의 줄 보드 각 행의 색이 주어진다 ( B = 검은색, W = 흰색 ) [출력] : 다시 칠해야 하는정사각형 개수 [참고] 1. 맨 처음 시작 판을 기준으로 번갈아 색을 칠할 것! 첫 시작판을 한가지 색으로 고정하자! 흰색판일 경우로만 진행하는 것 흑과 백 경우의 수가 2개 이므로 boolean을 사용! (0과 1로 사용해도 괜찮다) 반대색은 무조건 64 - (count) 위.. 2024. 4. 11.
[백준] 15661번 링크와 스타트 JAVA (자바) 풀이 문제 15661 (비트마스킹) : 축구는 평일 오후에 하고 의무 참석도 아니다. : 축구를 하기 위해 모인 사람은 총 N명, 이제 스타트 팀과 링크 팀으로 사람들을 나눈다. (한 명 이상) : 번호를 1부터 N까지로 배정했고 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. (예시) N=4이고, S가 아래와 같은 경우를 살펴보자. 예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다. 스타트 팀: S12 + S21 = 1 + 4 = 5 링크 팀: S34 + S43 = 2 + 5 = 7 1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력.. 2024. 2. 26.

티스토리툴바