알고리즘/개념정리9 순열, 조합 오늘은 코딩테스트에서 자주 마주치는 순열과 조합에 대해서 정리해보려한다. 순열 순열은 서로다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것이다. 이를 식으로 나타내면 nPn=n!(Factorial) 으로 나타낼 수 있다. 예시로 nP3을 구현해보자면, 순열의 반복적인 일은 숫자를 한개씩 뽑는일이다. 가능한 모든 수를 시도하면서 기존 수와 중복되지 않게 하나의 수를 선택한다. 이는 3중 for문을 사용해서 구현할 수 있다. 하지만 3처럼 숫자가 정해지지 않는다면, for문의 갯수를 알 수 없으므로 구현할 수 없다. 이 상황에서는 재귀를 사용해서 순열을 구현한다. 재귀로 구현하기 p메소드에서는 순열에 포함될 수를 하나씩 뽑는다. p메소드에서 해야될 일을 다음과 같다. 1. 가능한 모든 수를 시도 2. 다음수.. 2022. 9. 12. 자바 정렬하기 Comparable, Comparator는 둘다 객체를 비교하기 위해서 사용한다. 이 두 인터페이스를 사용한다면 우리가 원하는 기준을 만들어서 객체를 비교할 수 있게된다. 본질적으로 객체는 사용자가 기준을 정해주지 않는 이상 어떤 객체가 더 높은 우선순위를 갖는지 판단 할 수기 때문이다. 그렇다면 Comparable, Comparator 두개의 차이는 무엇일까? Comparable은 "자기 자신과 매개변수 객체를 비교" 한다. Comparator는 "두 매개변수 객체를 비교" 한다. 공식문서는 다음과 같다. [Comparable] docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html#method.summary Comparable (Java Platfo.. 2022. 9. 12. BFS,DFS Bfs와 Dfs는 그래프 전체를 탐색하는 방법이다. BFS 너비 우선 탐색 너비 우선 탐색 이란 시작 노드를 방문한 후 시작 노드에 있는 인접한 모든 노드들을 우선 방문하는 방법이다. 시작 노드로부터 가까운 지점을 먼저 방문하고 먼 지점은 나중에 방문한다. 인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용한다. 큐생성 루트 v를 큐에 삽입 while(큐가 비어있지 않은 경우){ t 2022. 8. 11. 객체 배열 객체배열 만들기 배열 여러개 구현할 필요 없이 배열부분에 객체를 넣어줄 수 있다. 스택, 큐, 1차원 배열에 넣어 줄 수 있다. 반복문안에 들어가면 메모리 터질수도! 신경써서 만들어주기 Stack stack = new Stack() stack.push(new Tower(height, position)) static class Tower { int height; int position; public Tower(int height, int position) { this.height = height; this.position = position; } } 2022. 8. 9. 이전 1 2 3 다음
