본문 바로가기

분류 전체보기539

[Algorithm] 유클리드 호제법 (최대공약수 & 최소공배수 구하기) 유클리드 호제법 유클리드 호제법이란, 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다. 의무교육 과정에서 최대공약수를 구하는 방법을 두가지 배울텐데 소인수분해와 호제법을 배운다. 호제법을 쓰다보면 위 경우처럼 수가 크면 계산이 복잡해지고, 약수를 한번에 찾기가 힘든 경우가 있다. 이 때, 유클리드 호제법을 이용해서 쉽게 구할수 있다. 유클리드 호제법은 두 정수의 최대공약수를 빠르게 구하는 방법이다. 하나만 기억해야하면 "A > B 일때, A와 B의 최대공약수는 B와 나머지 R의 최대공약수와 같다." 큰 수(A)를 작은 수(B)로 나눈다. ( A > B ) 만약 나누고 난 나머지가 0 이라면 작은 수가 최대공약수이다. 만약 나머지가 0이 아니라면, 작은 수(B)를 나머지(R)로 계속 나눈다. 이를.. 2023. 3. 24.
[Algorithm] (알고리즘 패턴) 슬라이딩 윈도우(Sliding Window) 슬라이딩 윈도우(Sliding Window) 알고리즘 패턴 윈도우(특정 범위)가 있을 때, 윈도우 내부 요소의 값을 이용하여 문제를 풀이하는 알고리즘이다. 배열이나 문자열같은 선형 구조에서 요소의 일정 범위값을 비교할 때, 사용하면 유용한 패턴이다. 투 포인터 패턴과 유사하다. 특정한 조건에 따라 window가 커지거나 닫히거나, 새로 생성될수도 있다. 예를 들어, 한 단어의 문자들 중 연속된 고유 문자의 길이가 가장 긴 부분을 출력할 때, 슬라이딩 윈도우와 같은 패턴을 사용할 수 있다. 프로세스 ex. [1, 3, 2, 6, -1, 4, 1, 8, 2] 라는 배열이 있는데, 연속적인 5개의 숫자의 합이 최대값을 구한다고 가정을 해본다. [1, 3, 2, 6, -1], 4, 1, 8, 2 합 : 11 1.. 2023. 3. 24.
[Design Pattern] 디자인 패턴이란 디자인 패턴이란? 디자인 패턴이란 기존 환경 내에서 반복적으로 일어나는 문제들을 어떻게 풀어나갈 것인가에 대한 일종의 솔루션 같은 것이다. 쉽게 말해 개발자들끼리 협업을 잘할 수 있도록 코드들의 패턴을 짬과 코드의 질, 효율성을 높히는 것이라 부를 수 있다는 것을 알 수 있다. 장점 개발자 간의 원활한 의사소통 소프트웨어 구조 파악 용이 재사용을 통한 개발 시간 단축 설계 변경 용청에 대한 유연한 대처 야근없이, 빠른 퇴근 가능 불필요한 리소스 낭비 방지 단점 객체지향 설계/구현 위주로 사용된다. 초기 투자 비용 부담 디자인 패턴 유형 Creation Design Pattern 객체의 생성에 관련된 패턴 객체의 생성 로직을 숨김으로써 유연성을 향상시킨다. Strutural Design Pattern 클래.. 2023. 3. 24.
[Daily Scrum] Meet 12. 2023-03-23 목요일 시간 : 22:00 ~ 22:30 진행 내용 : Todo list 공유, 내일 학습 계획 공유, 팀원간 소통 개인 학습 내용 : 프로그래머스 1문제(Lv. 2) 풀이 크루스칼, 세그먼트 트리, KMP 알고리즘 학습 2023. 3. 23.
[Programmers] (2021 카카오 채용연계형 인턴십) Lv 2. 거리두기 확인하기 https://school.programmers.co.kr/learn/courses/30/lessons/81302#fnref1 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr function solution(places) { return places.reduce((acc, data) => { // 굳이 완전 탐색을 써서 모든 경로를 찾아 itv를 비교하는 것보단, // itv가 2인 데이터인것들만 추출해서 그 사이 경로에 X가 있는지 체크하는 게 더 효율적이라 판단. const peoples = []; // P인 데이터만 담아둘 배열 data.forEach.. 2023. 3. 23.
[Algorithm] Segment Tree (구간 트리) Segment Tree (구간 트리) 구간 트리는 배열의 특정 구간에 대한 질의를 빠르게하기 위해 사용할 수 있다. 예를 들어 어떤 구간의 최소치를 구하고 싶다고 해보자. 보통 사용하는 방법은 구간 내 숫자를 하나하나 확인하면서 최소치를 찾는 것으로, O(N)의 시간이 걸린다. 이때 배열을 전처리해 구간 트리를 사용하면 O(N log N)의 시간에 찾을 수 있다. 구간 트리는 '주어진 배열의 구간들을 표현'하는 이진 트리를 만든다. 루트는 배열의 전체구간을 표현하고, 한 트리의 왼쪽 자식과 오른쪽 자식은 해당 구간의 왼쪽 반과 오른쪽 반을 표현한다. 각 노드는 해당 구간에 대한 계산 결과를 저장해둔다. 이렇게 전처리해둔 트리가 있다면 어떤 구간 [i, j]가 주어지면 이 구간을 구간 트리의 노드에 포함된.. 2023. 3. 23.
[Algorithm] KMP 알고리즘 (Knuth-Morris-Pratt Algorithm) 문자열 검색 문자열 검색 문제는 문자열 H가 주어졌을 때 문자열 N을 부분 문자열로 포함하는지 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제다. 이 문제를 풀 수 있는 가장 간단한 방법은 H의 가능한 모든 위치에서 다 시도해보는 방법이다. H의 각 위치의 부분 문자열이 N과 일치하는지 일일히 다 확인하는 것이다. 시작 위치의 수는 O(∣H∣)가 되고, 각각 비교에 걸리는 시간은 O(∣N∣)이 걸리기 때문에, 총 걸리는 시간은 O(∣H∣∣N∣)이다. C의 strstr(), C++의 string::find(), 자바의 indexOf(), 자바스크립트의 String.prototype.indexOf() 등 대부분 표준 라이브러리에서 사용된다. KMP(Knuth-Morris-Pratt).. 2023. 3. 23.
[Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm) 크루스칼 알고리즘 (Kruskal Algorithm) 이란 그래프 내의 모든 정점들을 가장 적은 비용(cost)으로 연결하기 위해 사용되는 알고리즘이다. 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 사용한다. 즉, 최소 신장 트리(MST, Minimum Spanning Tree)를 구하기 위한 알고리즘이다. 위 그래프가 있다고 가정할 때 노드의 개수는 5개고 간선의 개수는 6개다. 크루스칼 알고리즘의 핵심은 거리가 짧은 순서대로 그래프에 포함시키는 것이다. 크루스칼 알고리즘을 자세히 다루기 전에 신장 트리와 최소 신장 트리에 대해서 다뤄보자 신장 트리 (Spanning Tree) 신장 트리 (Spanning Tree)는 그래프의.. 2023. 3. 23.
[Daily Scrum] Meet 11. 2023-03-20 월요일 시간 : 22:00 ~ 22:30 진행 내용 : Todo list 공유, 내일 학습 계획 공유, 팀원간 소통 개인 학습 내용 : 프로그래머스 1문제(Lv. 2) 풀이 꼬리 재귀, 완전 탐색과 종류 학습 2023. 3. 21.
[Algorithm] 카데인 알고리즘 (Kadane's Algorithm) 카데인 알고리즘 (Kadane's Algorithm) 카데인 알고리즘은 DP (Dynamic Programing)의 기법중 하나인데 DP를 간단하게 설명하자면 다음과 같다. Dynamic Programing : 하나의 큰 문제를 풀기위해 그 문제를 작은 문제들로 나눠 풀어나간 후, 결국 하나의 큰 문제를 풀어내는 방법이다. 카데인 알고리즘은 최대 부분합 문제를 풀때 주로 사용된다. 최대 부분합 문제 Arr = [-2,1,-3,4,-1,2,1,-5,4]; 다음과 같은 배열이 주어질 때 위의 순서를 유지하고, 연속적이면서 가장 큰 합을 가지는 부분배열은 다음과 같다. [4, -1, 2, 1] -> 합 : 6 Arr[4] = -1 를 마지막 원소로 갖는 부분 합과, Arr[5] = 2를 마지막 원소로 갖는 부.. 2023. 3. 20.

티스토리툴바