목록Algorithm/개념 (21)

오늘도 더 나은 코드를 작성하였습니까?

완전탐색(Brute-Force Search / Exhaustive Search)

정의 브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다. 수학 문제를 원시적으로 푸는 방법인 '수 대입 노가다'의 학술적 개념이다. 컴퓨터 공학의 알고리즘 분야 특히, 문제 풀이에 있어서는 컴퓨터 CPU의 빠른 연산속도를 이용해 가능한 모든 경우의 수 및 경로를 탐색하여 해답을 도출해내는 방법이다. 예시 문제) 14500 테트로 미노 문제 분석해 보기 N*M 크기의 2차원 직사각 배열이 주어진다. 아래 5가지 형태를 각각 좌우 대칭 및 회전을 하여 위 숫자 직사각 배열에 1개의 도형을 ..
Algorithm/개념 2023. 11. 22. 02:05
서로소 집합 DSU(Disjoint set - Union) / 합집합 찾기 (Union-Find) kotlin

Disjoint Set(서로소 집합) - 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합 DSU(Disjoint Set Union) - 데이터 구조는 여러개의 서로소 집합(겹치지 않도록) 원소(데이터)를 저장하는 자료구조이다. - union–find 또는 merge-find 라고도 부른다. - 두 서로소 집합을 합쳐 하나의 집합으로 만들 수 있다(union) - 2개의 서로 다른 원소가 같은 집합인지 "대표원소를 통해" 확인할 수 있다(find) 구현 예) 총 원소가 0번 원소부터 7번까지 8개의 원소가 있다고 가정하고, 처음에는 자기 자신만을 포함하는 총 8 개의 집합이 있다고 가정해 보자. 배열로 Index는 해당 원소, value는 속한 집합의 "대표원소" 이다. * 대표원소를 결정하는 방..
Algorithm/개념 2023. 11. 15. 19:47
최장 증가 부분 수열 (LIS, Longest Increasing Subsequence) feat.kotlin

정의 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 뽑아서 부분수열을 만들 수 있다. 이때, 만들어진 부분수열 중 오름차순으로 정렬된 길이가 가장 긴 수열을 최장 증가 부분 수열이라 한다. 예를 들어 다음 수열이 주어졌다고 하자. ---> 탐색을 한다 가정할때, 5 1 6 2 7 3 8 1 2 3 8 5 6 7 8 모두 길이가 4인 최장 증가 부분 수열이다. 문제로 익혀보기. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {1..
Algorithm/개념 2023. 11. 6. 03:10
비트마스킹(BitMask) 활용 feat. kotlin

비트마스킹은 0000 0000 0000 0000 0000 0000 0000 0000 31자리수의 2진수를 통해 해당 비트가 켜져있냐 꺼져있냐를 통해 2147483647의 모든 상태를 효율적으로 표현할 수 있으며 단순 정수 연산으로 속도도 매우 빠르다. * 모든 조합 구해보기. val arr = arrayOf("철수", "영희", "민수", "민지") fun fullCombination() { // 0 부터 (1 shl arr.size) 10000(2) - 1까지 모든 선택을 나타내는 수까지 반복. for (i in 0 until (1 shl arr.size)) { val result = mutableListOf() for (j in 0 until arr.size) { // 어떤 비트가 선택되 었는지 확인..
Algorithm/개념 2023. 10. 27. 00:23
이전 Prev 1 2 3 4 5 6 Next 다음