본문 바로가기

알고리즘 문제87

[백준] 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.
[백준] 1012번: 유기농 배추 💡문제 분석 요약배추를 심은 배추밭의 정보를 입력받아, 배추가 모여있는 곳이 몇 군데인지(최소의 배추흰지렁이 수) 출력하는 문제이다.시간 제한: 1초메모리 제한: 512MB 💡알고리즘 설계`boolean[][] land` 에 배추가 있는 경우 true, 없는 경우 false로 설정한다.`land` 를 순회하며 배추가 있을 경우해당 위치를 false로 설정하고 `count` 를 증가시킨다.해당 위치로 dfs 메서드를 호출한다.dfs 메서드해당 위치의 상하좌우를 순회하여 배추가 있을 경우해당 위치를 false로 설정한다.해당 위치로 dfs 메서드를 재귀 호출한다. 💡코드import java.io.*;public class Main { static boolean[][] land; static .. 2024. 7. 18.
[백준] 11724번: 연결 요소의 개수 💡문제 분석 요약방향없는 그래프의 간선 정보를 입력받아, 연결 요소를 출력하는 문제이다.시간 제한: 3초메모리 제한: 512MB 💡알고리즘 설계boolean[][] graph 에 그래프 간선 정보를 저장한다. (양방향)모든 정점을 순회하며 방문 여부 검사해당 정점을 방문하지 않은 경우 (visited[i] = false)dfs 메서드 호출한다.연결 요소 개수(count)를 증가시킨다.dfs 메서드현재 정점을 방문 처리한다.해당 정점과 연결된 정점이 아직 방문하지 않은 경우 (graph[index][i] && !visited[i])해당 정점을 재귀적으로 dfs 호출한다. 💡코드import java.io.*;public class Main { static int n, k; static boo.. 2024. 7. 17.
[백준] 2667번: 단지번호붙이기 💡문제 분석 요약주어진 지도 정보를 통해 연결된 집들의 단지를 찾아 단지 수와 각 단지 내 집의 수를 오름차순으로 출력하는 문제이다.시간 제한: 1초메모리 제한: 128MB 💡알고리즘 설계`int[n][n] house` 에 지도 정보를 저장한다.`house` 의 모든 위치를 반복집이 존재하고 방문하지 않은 경우 (`house[i][j] == 1 && !visited[i][j]`)단지 수(`count`)를 1 증가시키고, 단지 내 집의 수(`house_count`)를 1로 초기화한다.해당 위치을 방문 처리한다. (`visited[i][j] = true`)dfs 함수를 호출해 해당 위치의 상하좌우 집을 검사한다.`house_counts`에 현재 단지내 집의 수를 추가한다.dfs 함수현재 집의 상하좌우를 .. 2024. 7. 16.
반응형