반응형

Algorithm 66

피보나치 수열 (재귀 vs 비재귀)

아래는 피보나치 수열입니다. 1. 재귀 버전 이는 재귀 알고리즘으로 아래와 같이 구현 할수 있습니다. fib(n): if (n = 1 or n = 2) return 1 else return fib(n - 1) + fib(n - 2) 이는 재귀 알고리즘으로 구현한 치명적인 예 입니다. 시간이 너무 오래 걸립니다. 100번째 피보나치 수를 계산하기 위해서 fib(100)을 수행하면 평생 기다려도 결과를 볼 수 없습니다. 이렇게 엄청난 시간이 걸리는 이유는 한번 계산해 놓은 결과를 계속 호출하여 지수함수적인 중복을 일으키기 때문이다. 이 문제를 다음과 같이 수정하여 fib2(100)은 어마어마하게 시간을 단축 시킵니다. 2. 비재귀 버전 fib2(n) : f[1] ← f[2] ← 1 //f[2] ← 1과 f[..

Algorithm 2023.06.17

2개의 json key 값을 비교하는 방법

요즘 다니는 회사는 산업용 스마트폰을 직접 제조하는 회사를 다니고 있습니다. 산업용 스마트폰이기 때문에 미국의 아마존과 같은 대형 공장에서 쓰이는 스마트폰을 제조하는데요. 이곳에서 저는 EMM(Enterprise Mobility Management)을 담당하는 팀에 소속해 있습니다. 공장 직원들이 사용하는 업무용 스마트폰이기 때문에 공장에서 원하는 스펙과 기능들을 충족 시켜주는 안드로이드 소프트웨어 개발로 지원하고 있지요. 그 기능들 중에서 프로비저닝 이라는 기능이 있습니다. 제가 설명하는 내용보다 조금 더 넓은 개념으로 쓰이는데요. 제가 사용하는 '프로비저닝'은 안드로이드 스마트폰의 설정한 설정값들을 공장 직원들 업무용 폰에도 똑같이 적용해 주는 것이 '프로비저닝'입니다. 1. 요구사항 '프로비저닝' ..

Algorithm 2023.06.10

[백준 1021] 회전하는 큐

문제 설명 크기가 N인 덱(deque)이 주어지고, 덱의 첫 번째 위치는 1, 덱의 마지막 위치는 N으로 지정합니다. 이때, 덱에서 M개의 수를 뽑아내려고 합니다. 뽑아내는 순서가 주어질 때, 뽑아내는 과정에서 덱이 최소로 회전하는 횟수를 구하는 문제입니다. 이때 덱은 아래 3가지 연산만 할 수 있습니다. (f1연산) 첫번째 원소를 뽑는다. {a1…ak} → {a2…ak} (f2연산) 왼쪽으로 한칸 이동. {a1…ak} → {a2…ak, a1} (f3연산) 오른쪽으로 한칸 이동. {a1…ak} → {ak, a1…ak-1} 동작 HTML 삽입 미리보기할 수 없는 소스 java 코드 import java.util.ArrayDeque; import java.util.Deque; import java.util...

Algorithm 2023.02.25

display flex5, align-items align-content , 아이템 정렬 방법

display : flex 에서 교차축을 기준으로 item을 어떻게 정렬 할까요? ​ 1. align-items align-items 속성은 교차축을 기준으로 item 을 정렬 하는 방법 입니다. 교차축은 'flex-direction : 값' 의 값의 반대 가 되는 축을 의미 합니다. 비슷한 속성인 align-content를 기본값으로 설정 해야 사용 할 수 있습니다. ​ ​ 2. align-content align-content 속성 또한 교차축을 기준으로 item 을 정렬 하는 방법 입니다. 교차축은 'flex-direction : 값' 의 값의 반대 가 되는 축을 의미 합니다. align-items 는 item이 1줄일 경우에 사용 합니다. align-content 는 item이 2줄 이상일 경우에..

Algorithm 2021.03.17

접두사, 접미사를 이용한, KMP 문자열 매칭 알고리즘 2 with Java

KMP 문자열 매칭 알고리즘 오늘은 문자열 찾기 알고리즘인 KMP(Knuth-Morris-Pratt) 알고리즘에 대해서 공부 하겠습니다. ​ ​ 1. 문자열 매칭(String Matching) 우리들이 흔히들 사용하는 브라우저에서 Ctrl + F(찾기) 기능에서 사용 coding-food-court.tistory.com 1. 접두사, 접미사 일치 테이블 만들기 그렇다면, KMP 알고리즘의 핵심은 패턴 문자열의 접두사와 접미사 일치 길이를 가지고 있는 일치 테이블을 만드는 것 입니다. 일치 길이를 알고 있어야, 해당하는 만큼 점프하여 문자열 매칭이 이루어지는지 탐색 할 수 있으니까요. (k : 0부터 시작하는 인덱스) (i : 1부터 시작하는 인덱스) 1. k와 i의 문자가 같으면 일치 테이블의 값을 일치..

Algorithm 2021.03.16

KMP 문자열 매칭 알고리즘 vs 순차 탐색 알고리즘

1. 문자열 매칭 알고리즘 (KMP 알고리즘) 문자열 매칭 알고리즘에 대해서 알아보겠습니다. 먼저 문자열 매칭을 위해서는 단순 반복을 통하여 문자열을 찾아 낼 수 있는 방법이 있습니다. 이를 java로 구현해 보겠습니다. package idea; public class SimpleComparisonString { /** * 단순 문자열 찾기 알고리즘 * KMP 라는 더 효율적인 알고리즘을 사용 하기 전에 구현 * @참고 https://blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240660061&categoryNo=128&parentCategoryNo=0&viewDate=&currentPage=4&postListTopCurrentPage=1&from=post..

Algorithm 2021.03.15

크루스칼(Kruskal) 알고리즘 2, Union-Find를 이용한 크루스칼

크루스칼(Kruskal) 알고리즘 1, 최소비용신장트리 / Union-Find 원리 1. 크루스칼(Kruskal) 알고리즘 이란? 크루스칼 알고리즘은 최소 비용으로 모든 노드를 연결하는 알고리즘 입니다. 흔히 여러 도시가 있을때 각 도시를 최소 비용으로 연결 하는 문제에서 쓰입니다 coding-food-court.tistory.com ​ 1. 크루스칼(Kruskal) 알고리즘 절차 1. 엣지를 오름차순으로 정렬 2. 각 노드 마다의 루트 부모 노드를 자기 자신으로 할당 3. 오름차순으로 한 엣지로 연결되어 있는 두 노드의 최상위 부모 노드가 다른 두 노드를 찾아 냄(find 연산) 4. 최소 비용 값을 알기 위해서 엣지의 값을 더함 5. 두 노드의 최상위 부모 노드가 다르다면 더 작은 값을 다른 노드의 ..

Algorithm 2021.03.12

크루스칼(Kruskal) 알고리즘 1, 최소비용신장트리 / Union-Find 원리

1. 크루스칼(Kruskal) 알고리즘 이란? 크루스칼 알고리즘은 최소 비용으로 모든 노드를 연결하는 알고리즘 입니다. 흔히 여러 도시가 있을때 각 도시를 최소 비용으로 연결 하는 문제에서 쓰입니다. ​ ​ 2. 최소 비용 신장 트리(Minimum Spanning Tree) 위와 같은 그래프가 있을때, 6을 '노드' 또는 '정점' 이라고 부릅니다. 또한 25를 '비용' 또는 '엣지' 또는 '가중치' 라고 합니다. 크루스칼(Kruskal) 알고리즘으로 가능한 최소 비용으로 모든 노드를 연결하고 나면 최소 비용 신장 트리(Minimum Spanning Tree)가 만들어집니다. 가능한 최소 비용으로 모든 노드를 연결 하기 위해서는 비용이 가장 적은 엣지 부터 하나씩 연결 합니다. 하지만 트리는 여러 노드가 ..

Algorithm 2021.03.10

라빈 카프(Rabin-Karp), Hash 기반으로 문자열 빨리 찾기

라빈 카프 알고리즘은 hash 알고리즘을 기반으로 하고 있기 때문에 hash 알고리즘은 밑에 링크에서 다루도록 하겠습니다. Hash 알고리즘 1. Hash 알고리즘 예를 들어 43, 36, 44, 21, 25, 30, 22, 17 이라는 데이터를 가지고 있고, h(k) = k % 10 이라는 함수가 있습니다. 위 데이터를 h(k) 함수에 대입하여 얻은 값을 테이블에 인덱스로 사용하고,.. coding-food-court.tistory.com 라빈카프 알고리즘은 서로 다른 두 문자열을 비교시에 두 문자열의 해시 코드로 일치 여부를 판단하는 알고리즘 입니다. ​ ​ 1. 문자열 순차 탐색 긴글에서 특정 패턴에 해당하는 문자열을 비교 할때 어떻게 비교를 할까요? 찾고자 하는 문자열의 길이 N을 전체 문자열의 ..

Algorithm 2021.03.09

LCA 최소 공통 조상

최소 공통 조상 이란 트리(Tree) 구조에서 특정한 두 노드의 공통된 조상 중에서 가장 가까운 조상을 의미 합니다. 최소 공통 조상 알고리즘은 트리에서 두 노드 사이의 거리를 빠르게 구하는 등 다양한 계산에 활용될 수 있다는 특징이 있습니다. ​ 이 알고리즘은 일종의 다이나믹 프로그래밍 입니다. 이 때 트리는 반드시 이진 트리(Binary Tree)가 아니어도 일반적인 형태의 트리라면 적용할 수 있습니다. 위와 같이 트리 형태의 그래프가 주어졌을 때 노드 20과 15의 최소 공통 조상 노드를 구해 봅시다. 두 노드를 거슬러 올라가다 보면 공통 조상인 노드 1을 찾을 수 있습니다. ​ * 다이나믹 프로그래밍을 활용한 최소 공통 조상 알고리즘 1. 모든 노드에 대한 깊이(Depth)를 구합니다. 2. 모든..

Algorithm 2021.03.04
반응형