본문 바로가기
728x90

Algorithm

Algorithm/정리 2022. 7. 15. [알고리즘] 순열 vs 조합 vs 부분 집합 (순조부) 순열 (Permutation) 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 서로 다른 n개 중 r개를 택하는 순열은 nPr 순열을 생성하는 방법 반복문을 통한 순열 생성 : 순열의 갯수가 적을때, 순열의 길이가 변동이 없을때 재귀 호출을 통한 순열 생성 : boolean[ ] 사용 비트마스킹을 통한 순열 생성 : 정수와 비트연산자를 사용 현 순열에서 사전 순으로 다음 순열 생성 ( NextPermutation ) 배열을 오름차순으로 정렬한 후 시작 아래 과정을 반복하여 사전 순으로 다음으로 큰 순열 생성 뒤쪽부터 탐색하며 교환위치 ( i-1 ) 찾기 ( i:꼭대기 ) 뒤쪽부터 탐색하며 교환위치 ( i-1 )와 교환할 큰 값 위치 ( j ) 찾기 두 위치 값 ( i-1, j ) 교환 꼭대기위치..
[알고리즘] 최장 공통 부분 수열 (LCS, Longest Common Subsequence)
Algorithm/정리 2022. 7. 2. [알고리즘] 최장 공통 부분 수열 (LCS, Longest Common Subsequence) 최장 공통 부분 수열 LCS (Longest Common Subsequence) 주로 최장 공통 부분수열(Longest Common Subsequence)을 나타내지만 최장 공통 문자열(Longest Common Substring)을 말하기도 한다. 최장 공통 문자열(Longest Common Substring)은 반드시 부분 문자열이 연결된 형태여야한다. banana, vbankn 최장 공통 부분수열(Longest Common Subsequence)은 떨어져있어도 상관없다. bdanvv, vbkkanm 이번에 다룰 LCS 알고리즘은 최장 공통 부분수열(Longest Common Subsequence)이다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종..
Algorithm/정리 2022. 3. 16. 진수 변환 (10진수 > n진수 / n진수 > 10진수) 1. 10진수 -> n진수 변환 Integer.toString(int n, int radix) 10진수로 입력된 n을 radix진수 형태로 변환한다. public class Solution { public static void main(String[] args) { int a = 25; System.out.println("10진수 -> 2진수"); System.out.println(Integer.toBinaryString(a)); System.out.println(Integer.toString(a,2)); System.out.println("10진수 -> 3진수"); System.out.println(Integer.toString(a,3)); System.out.println("10진수 -> 4진수");..
728x90

티스토리툴바