CS (15) 썸네일형 리스트형 유클리드 호제법(Euclidean algorithm) ‣ 유클리드 호제법 유클리드에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘으로, 두 수의 최대공약수를 구하는 알고리즘이다. 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 것으로, 서로 호(互)와 덜(나누기) 제(除)를 써서 호제법이다. ‣ 예시: 1071과 1029의 최대공약수 계산하기 [일반적인 방법] 일반적으로 최대공약수를 구한다고 생각한다면, 먼저 소인수분해를 떠올린다. 1071 = 17 x 7 x 3 x 3 1029 = 7 x 7 x 7 x 3 두 수를 소인수분해한 결과, 공통된 소수를 찾으면 된다. 이를 통해 두 수의 최대공약수(GCD)가 " 7 x 3 = 21 "인 것을 알 수 있다. 하지만, 이 방법은 수가 커질 수록, 소인수분해를 수행하기 어려워진다는 단점이 있다. 유.. N진법 ⚠️ 코드 없이, 설명만 작성된 글입니다.[N진법]?10진법에 익숙한 우리에게 N진법은 다소 어색하게 느껴진다.하지만, 우리는 이미 일상에서 다양하게 N진법을 접하고 있다.예를 들어 생각해 보자.연필은 한 다스는 12자루이다.그럼 연필이 30개면? 2다스 6자루가 된다.즉, 10진수로 30은, 12진수로 26이된다.연필 12자루 / 셔터스톡아직 애매한가?그럼 계란의 경우도 생각해보자.계란은 한판에 30개로 구성된다.그럼 계란이 3판에 3개가 추가로 있다면 총 몇 개의 계란이 있는 것일까?답은 93개이다.즉, 30진수로 33은 10진수로 93이 되는 것이다.우리는 이처럼, 이미 자연스럽게 다양한 진법을 실생활에 사용해 왔다. 단순하게 아래와 같이 생각하고, 변환법을 바로 알아보자.N진법 = 모든 자리 수가.. 힙(Heap) 🥪🥅목표우선 순위 큐를 위하여 만들어진 자료구조, 힙(Heap)에 대해 이해한다.배열을 사용하여 힙(Heap)을 구현할 수 있다.힙(Heap)의 삽입과 삭제를 이해한다. 🤔시작 전…우선순위 큐(Priority-Queue)란?데이터틀이 우선순위를 가지고 있고, 우선순위가 높은 데이터가 먼저 나간다.자료구조삭제되는 요소스택(Stack)가장 최근에 추가된 데이터큐(Queue)가장 먼저 들어온 데이터우선순위 힙(Priority-Queue)가장 우선순위가 높은 데이터우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다. 이 중에서 힙(Heap)으로 구현하는 것이 가장 효율적이다.표삽입삭제순서 없는 배열O(1)O(n)순서 없는 연결 리스트O(1)O(n)정렬된 배열O(n)O(1)정렬된 연결리스트O(n)O(1)힙O.. 스택(Stack) 🥪Stack목표스택(Stack)의 기본 연산을 이해한다.Kotlin과 Python으로 Stack을 구현할 수 있다.📖개념한쪽 끝에서만 자료를 넣고 뺼 수 있는 LIFO(Last In First Out) 형식의 자료구조🧮연산스택(Stack)은 LIFO를 따른다. 즉, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.pop(): 스택에서 가장 위에 있는 항목을 제거한다.push(item): item 하나를 스택의 가장 윗 부분에 추가한다.peek(): 스택의 가장 위에 있는 항목을 반환한다.isEmpyty(): 스택이 비어있을 때 true를 반환한다. ⚒️구현문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다.배열과 달리 스택은 상수시간(O(1)에 i번째 항목에.. 큐(Queue) 🥪🥅목표큐(Queue)의 기본 연산을 이해한다.Kotlin과 Python으로 Queue를 구현할 수 있다.📖개념컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식이다. 🧮연산큐(Queue)는 FIFO(First-In-First-Out)을 따른다.add(item) : item을 리스트의 끝부분에 추가한다.remove(): 리스트의 첫 번째 항목을 제거한다.peek(): 큐에서 가장 위에 있는 항목을 반환한다.isEmpty(): 큐가 비어있을 때에 true를 반환한다. ⚒️구현Kotlin으로 구현한 큐 예시 코드는 아래와 같다.class Queue { private val items = mutableListOf() fu.. [네트워크] 캐시(Cache) 캐시(Chache) 자주 사용하는 데이터나 값을 미리 복사해 놓은 임시 장소 아래와 같은 저장공간 계층 구조에서 확인할 수 있듯이, 캐시는 저장 공간이 작고 비용이 비싼 대신 빠른 성능을 제공한다. 파레토의 법칙과 지역성의 원리보통 개발을 할 때, "캐시로 처리하겠다"는 "나중에 요청할 결과를 미리 저장해둔 후 요청이 오면 빠르게 처리해 주겠다"는 것을 의미한다.즉, 미리 결과를 저장하고 나중에 요청이 오면 그 요청에 대해서 DB 또는 API를 참조하지 않고 Cache를 참조하여 요청을 처리하도록 만들겠다는 것이다.앞서 작성한 것 처럼, 캐시는 자주 사용하는 데이터나 값을 미리 복사해 놓은 임시 장소이기 때문이다.캐시의 이런 동작 배경에는 파레토 법칙과 지역성 원리가 있다. 파레토 법칙은 "80%의 결과.. 시간 복잡도와 공간 복잡도 알고리즘 성능 평가 어떤 알고리즘이 있을 때, 그 알고리즘의 성능 평가는 어떻게 할 수 있을까요? 알고리즘 성능을 평가하기 위해 '복잡도(Complexity)'라는 척도를 사용합니다. 그 중 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)의 개념이 나오며, 동일한 기능을 수행하는 알고리즘이 있을 때, 복잡도가 낮을 수록 좋은 알고리즘이라 말합니다. 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 1_1. 시간 복잡도 시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미합니다. 같은 결과를 갖는 코드도 작성 방법에 따라 걸리는 시간이 달라지며, 같은 결.. 이전 1 2 다음
