DFS5 [ps java] BOJ 15663 N과 M (9) 해설 "백트래킹" 대표 시리즈인 N과 M 시리즈 9번 문제 [실버2]역시 문제 조건 N ※ 백트래킹은 재귀를 활용하므로 보통 시간복잡도가 O(N^N), O(N!) 꼴이다 풀이의 핵심은 중복을 피하는 것이며, 이에 대해 두 가지 풀이 방법이 있다1) HashSet 사용 풀이2) 중복 방지 로직 풀이 https://www.acmicpc.net/problem/15663문제N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력한 줄에 하나씩 문제의 조건.. 2025. 1. 7. [ps java] BOJ 15650 N과 M (2) 해설 "백트래킹" 대표 시리즈인 N과 M 시리즈 [실버3]문제 조건 N ※ 백트래킹은 재귀를 활용하므로 보통 시간복잡도가 O(N^N), O(N!) 꼴이다 https://www.acmicpc.net/problem/15650문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다.입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.예제 입력 13 1예제 출.. 2025. 1. 6. 코딩테스트 빈출 유형 정리 [코딩테스트 주요 알고리즘]- 구현 및 시뮬레이션 - 문자열 처리(해시테이블 or 스택)- 완전 탐색(브루트 포스)- 이진 탐색(매개변수 탐색)- 그래프 탐색(DFS, BFS)- 백트래킹- DP- 그리디- 투포인터 [가끔 나오는 알고리즘]- 정렬- MST(크루스칼)- 최단경로(다익스트라, 벨만-포드, 플로이드-와샬)- 위상정렬- 모든 쌍 최단경로 문제- 분리집합- 트리의 지름 구하기- 트라이 2024. 8. 4. [알고리즘] ep5-2+) DFS, BFS 구현 문제1) DFS 구현입력으로 주어지는 그래프의 DFS 순회 결과를 출력하는 프로그램을 작성하시오. 입력 그래프의 성질:n (1 ≤ n ≤ 100) 개의 정점과 m (1 ≤ m ≤ 1,000) 개의 간선으로 구성정점은 1 ~ n 사이의 정수로 번호가 매겨져 있고, 정점의 번호는 모두 다름모든 간선은 무방향 간선이고, 한 정점에서 임의의 다른 정점으로 가는 경로는 반드시 존재구현 조건:그래프는 인접리스트 구조를 사용하여 표현해야 한다.인접 정점의 조사 순서: 정점 u의 인접 정점(or 부착 간선)들을 번호가 작은 정점부터 조사한다. (즉, 아래 DFS 의사 코드의 for 문에서 인접 정점들을 번호가 작은 정점부터 큰 순서대로 조사하라. 조사 순서에 따라 방문 결과가 달라질 수 있음에 유의할 것)입력:첫 줄에.. 2024. 7. 22. [알고리즘] ep5-2) 그래프 순회 그래프 순회(graph traversal): 모든 정점과 간선을 검사함으로써 그래프를 탐험하는 체계적인 절차- 수도권 전철망의 모든 역(정점)의 위치를 출력- 항공사의 모든 항공편(간선)에 대한 노선 정보를 수집- 웹 검색엔진의 데이터 수집 부문은 웹의 하이퍼텍스트 문서(정점)와 문서 내 링크(간선)를 검사함으로써 서핑 그래프의 순회로는 DFS, BFS 두 가지가 있다그래프 G에 대한 DFS 순회 또는 BFS 순회의 활용은 아래와 같다- G의 모든 정점과 간선을 방문- G가 연결그래프인지 결정- G의 연결요소들을 계산- G의 신장 숲을 계산 ① 깊이우선탐색(DFS, Depth-First Search) by 스택(재귀)n개의 정점과 m개의 간선을 가진 그래프에 대한 DFS는 O(n + m) 시간 소요 "D.. 2024. 7. 21. 이전 1 다음
