본문 바로가기

분류 전체보기174

[백준] 1759번: 암호 만들기 (Java) 💡문제 분석 요약암호의 알파벳 개수 L과 사용한 문자의 종류 C를 입력받아서, 가능성 있는 암호들을 모두 구하는 문제이다.시간 제한: 2초메모리 제한; 128MB 💡알고리즘 설계C개의 문자열을 오름차순으로 `alpha` 배열에 저장하고, 자음&모음의 여부를 `check` 배열에 저장한다.start를 0부터 백트래킹을 시도한다.백트래킹 메서드매개 변수로 `start` (시작위치), `length` (암호 길이)를 받는다.`length` 가 L이면암호의 모음, 자음 최소 개수 조건을 확인하고, `result` 에 추가한다. (중복 방지를 위해 `LinkedHastSet` 타입으로 `result` 를 정의함)start부터 C-1까지 작업을 수행한다.`password[length]` 에 현재 위치의 알파벳을.. 2024. 7. 26.
[백준] 1182번: 부분수열의 합 (Java) 💡문제 분석 요약N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열에서 그 수열의 원소를 모두 더한 값이 S가 되는 경우의 수를 구하는 문제이다.시간 제한: 2초메모리 제한: 256MB 💡알고리즘 설계`numbers` 배열에 N개의 정수를 입력받는다.부분 수열의 길이(`depth`)는 1~N까지 가능하다. 각 길이에 대해 백트래킹을 수행한다.백트래킹 메서드현재 깊이가 목표 깊이와 같으면, (`curDepth == depth`)부분수열의 합(`sum`)이 S인지 확인하고 `result`를 갱신한다.그렇지 않으면, 현재 위치(`start`)부터 N까지의 숫자에 대해해당 숫자를 `sum`에 더한다.다음 위치로 이동하여 메서드를 재귀 호출한다.백트래킹 후 `sum` 에서 해당 숫자를 뺀다. (원.. 2024. 7. 25.
[백준] 6987번: 월드컵 (Java) 💡문제 분석 요약월드컵 조별 리그의 결과를 입력받아, 입력받은 결과가 가능한지 아닌지 판별하는 문제이다.시간 제한: 1초메모리 제한: 128MB 💡알고리즘 설계문제 조건한 팀의 경기 수는 5회각 팀은 다른 모든 팀과 한 번씩 경기 ⇒ 총 15경기각 경기 결과는 승-패, 무-무, 패-승 중 하나 ⇒ 총 3가지자료구조int[] team1, int[] team2: 각 라운드별 경기를 진행하는 팀int[][] gameInputResult: 입력받은 각 팀의 경기 결과(승,무,패) 횟수int[][] gameResult: 백트래킹 과정에서 계산하는 각 팀의 경기 결과 횟수int[] result: 각 테스트 케이스의 결과를 저장하는 배열백트래킹라운드 0부터 시작해서 각 경기 결과를 가정하며 탐색각 라운드에서 3가.. 2024. 7. 24.
[백준] 15651번: N과 M (3) 💡문제 분석 요약“1부터 N까지 자연수 중에서 M개를 고른 수열” 조건을 만족하는 길이가 M인 수열을 모두 구하는 문제이다. 같은 수를 여러 번 골라도 된다.시간 제한: 1초메모리 제한: 512MB 💡알고리즘 설계N, M을 입력받는다.수열을 저장할 `sequence` 배열을 생성한다.백트래킹을 사용해 길이가 M인 모든 가능한 수열을 생성한다.현재 깊이(`depth`)가 M과 같아지면 수열을 출력한다.1부터 N까지의 수에 대해:현재 수를 수열에 추가한다.`depth + 1` 깊이로 재귀 호출한다. 💡코드import java.io.*;public class Main { static int n, m; static int[] sequence; static StringBuilder sb = .. 2024. 7. 23.
[백준] 16883번: N과 M (9) 💡문제 분석 요약자연수 N, M을 입력받아, “N개의 자연수 중에서 M개를 고른 수열”을 만족하는 길이가 M인 수열을 모두 출력하는 문제이다.시간 제한: 1초메모리 제한: 512MB 💡알고리즘 설계입력받은 N개의 수를 정렬한다.백트래킹을 사용해 길이가 M인 모든 가능한 수열을 생성한다.각 단계에서 사용하지 않은 숫자를 선택한다.선택한 숫자를 수열에 추가하고, 다음 단계로 넘어간다.수열의 길이가 m이 되면 결과에 추가한다.생성된 수열들을 LinkedHashSet에 저장해 중복을 제거하고 오름차순을 유지한다.사용한 주요 변수:numbers[]: 입력받은 N개의 수를 저장하고 정렬하는 배열sequence[]: 현재 만들고 있는 수열을 저장하는 배열visited[]: 각 숫자의 방문 여부를 저장하는 배열.L.. 2024. 7. 22.
[백준] 2178번: 미로 탐색 💡문제 분석 요약N x M 크기의 미로에서 (1, 1)에서 (N, M)까지 이동하는데 필요한 최소의 칸 수를 구하는 문제이다.시간 제한: 1초메모리 제한: 192MB 💡알고리즘 설계줄의 개수 N, 칸의 개수 M 를 입력받고, (N, M)의 미로 정보를 입력받는다.BFS 메서드를 호출하여 미로를 탐색한다.BFS 메서드`Queue` 타입의 큐를 생성한다. (탐색할 좌표를 저장함)시작 위치 (1, 1)를 큐에 넣는다.큐가 빌 때까지:큐의 맨 앞의 값을 꺼낸다. ⇒ 현재 위치 (`cur`)`cur`의 상하좌우를 탐색한다.탐색 위치 (x, y)가 미로의 범위에 속하고, 이동 가능한 경로 (`graph[x][y] = 1`)일 경우해당 위치를 큐에 넣는다.해당 위치를 방문 처리한다. (`graph[x][y] = .. 2024. 7. 20.
[백준] 1697번: 숨바꼭질 💡문제 분석 요약수빈의 위치를 N, 동생의 위치를 K로 입력받는다. 수빈의 위치를 X라고 할 때 X-1, X+1, 2*X로 이동할 수 있고, 이동할 경우 1초가 소요된다. 이 때 수빈이 동생을 찾을 수 있는 가장 빠른 시간을 구하는 문제이다.시간 제한: 2초메모리 제한: 128MB 💡알고리즘 설계수빈의 위치 `n` 과 동생의 위치 `k` 를 입력받는다.위치에 따른 이동 시간을 저장하는 `time`배열을 생성한다. (0 초기화)`time`배열의 값이 0일 경우 방문하지 않은 것으로 처리한다. (= 이동 시간이 0)`time[n]` 을 1로 설정하고, BFS를 이용해 `k`위치까지의 이동 시간을 계산한다.BFS 메서드시작 위치를 큐에 넣는다.큐가 빌 때까지:큐의 맨 앞의 값을 가져온다. ⇒ 현재 위치 `.. 2024. 7. 19.
반응형