알고리즘49 순열, 조합 오늘은 코딩테스트에서 자주 마주치는 순열과 조합에 대해서 정리해보려한다. 순열 순열은 서로다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것이다. 이를 식으로 나타내면 nPn=n!(Factorial) 으로 나타낼 수 있다. 예시로 nP3을 구현해보자면, 순열의 반복적인 일은 숫자를 한개씩 뽑는일이다. 가능한 모든 수를 시도하면서 기존 수와 중복되지 않게 하나의 수를 선택한다. 이는 3중 for문을 사용해서 구현할 수 있다. 하지만 3처럼 숫자가 정해지지 않는다면, for문의 갯수를 알 수 없으므로 구현할 수 없다. 이 상황에서는 재귀를 사용해서 순열을 구현한다. 재귀로 구현하기 p메소드에서는 순열에 포함될 수를 하나씩 뽑는다. p메소드에서 해야될 일을 다음과 같다. 1. 가능한 모든 수를 시도 2. 다음수.. 2022. 9. 12. [SW Expert Academy Java] 4112 이상한 피라미드 탐험 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWJHmLraeEwDFAUH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이방법 처음에는 모든 숫자에게 높이를 부여하는 배열을 생성해서 bfs를 돌릴려 그랬다. 하지만 피라미드를 그려서 최적경로를 찾아보니 굳이 그럴 필요가 없다는 것을 알았다. while(num 2022. 9. 12. [백준 JAVA]13023 ABCDE 문제 13023번: ABCDE (acmicpc.net) 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net dfs를 활용해서 이어진 친구들을 세주었다. 풀이방법 무방향 그래프이기 때문에 배열 양쪽에 값을 넣어준다. list[to].add(from); list[from].add(to); 입력을 받고 dfs를 돌려준다. 인접한 경우를 재귀호출을 사용하며 count를 세준다. count가 5가되면(관계가 5명 이어지면) return 을 해주고 end를 true로 바꿔준다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStre.. 2022. 9. 12. [백준 JAVA & Python] 1260 DFS와 BFS 문제 1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net bfs, dfs를 연습해보기 좋은 기본문제이다. 풀이방법 무방향 그래프이기 때문에, 배열 양쪽에 값을 넣어주는 것이 포인트이다. list[to].add(from); list[from].add(to); dfs는 순열을 사용해서, bfs는 큐를 사용해서 구현하였다. 코드 java import java.io.BufferedReader; import java.io.IOExc.. 2022. 9. 12. 이전 1 2 3 4 5 6 7 8 ··· 13 다음
