본문 바로가기

분류 전체보기156

[프로그래머스] 입국심사 (Java) 💡문제 분석 요약입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 주어질 때, 모든 사람이 심사는 받는데 걸리는 시간의 최솟값을 구하는 문제이다.$1 ≤ n ≤ 1,000,000,000$각 심사관이 한 명을 심사하는데 걸리는 시간(분): $1 ≤ time ≤ 1,000,000,000$심사관: $1≤ t ≤ 100,000$ 💡알고리즘 설계이진탐색을 사용.탐색 범위left(최소시간): 1right(최대시간): `n * max(times)` :가장 오래 걸리는 심사관이 모든 사람을 심사하는 경우탐색 수행mid(중간시간): `left + (right - left) / 2`이 시간동안 모든 심사관들이 심사할 수 있는 인원을 계산한다.범위 조정계산된 인원이 .. 2024. 7. 29.
[백준] 2661번: 좋은 수열 (Java) 💡문제 분석 요약1,2,3 으로만 이루어져 있는 길이가 N인 좋은 수열 중 가장 작은 수를 구하는 문제이다.좋은 수열은 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 없는 수열이다.시간 제한: 1초메모리 제한: 128MB 💡알고리즘 설계백트래킹 메서드 (`backTrack`)1, 2, 3 을 순차적으로 현재 수열(`seq`)에 추가한다.`seq` 에 숫자를 추가했을 때 좋은 수열인지 검사한다. (`isGoodSeq`)좋은 수열이면 숫자를 추가하여 메서드를 재귀 호출한다.`seq`의 길이가 N이 되면 출력하고 프로그램을 종료한다.좋은 수열인지 검사 (`isGoodSeq`)길이가 1인 부분 수열부터 시작해서 수열의 길이 절반까지 늘려가며 검사한다. (1부터 seq.length() / 2 까지)각.. 2024. 7. 27.
[백준] 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.
반응형