potato's devlog

최소공배수, 최대공약수를 구하는 알고리즘을 정말 간단하게 구현할 수 있으면서도, 계속 for문을 돌리고있고,,, 시간낭비를 할 때가 많다. 스스로 기억하기 위해서 적어두는 유클리드 호제법! 꼭 기억하고 있도록 하자 🔖 유클리드 호제법 이란? (feat. 최대공약수) 유클리드 호제법은 두 개의 정수(자연수) 사이에서의 최대공약수를 구하는 알고리즘이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. -wiki 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를..

🙋🏻‍♀️ 이분그래프 위 사진처럼 그래프가 '두개의 색'으로 표현되는 것을 이분그래프라고 한다. 빨간정점과 검은정점 두 그룹으로 나뉘었는데, 같은 그룹끼리는 인접하지 않아야한다. 즉, 그래프의 모든 정점이 두 그룹으로 나뉘어지고 서로 다른 그룹의 정점만이 간선으로 연결된 그래프를 말한다. 👻 이분그래프의 특징 이분 그래프인지 확인하기 위해서는 BFS와 DFS 탐색 방법을 이용할 수 있다. DFS와 BFS를 통해서 그래프를 탐색하게 되면, 같은 depth에 있는 정점은 같은 색을 갖게 되는 것이다. 연결 요소의 개수를 구하는 방법과 유사하다. 모든 정점을 방문해서 검사하기 때문에 시간복잡도는 O(V+E)로 그래프 탐색 알고리즘과 같다. 🧑🏻‍💻 이분그래프인지 확인해보는 방법 ⚠️ 주의사항: 서로 인접한 정..

🙋🏻‍♀️ 백트래킹이란? 백트래킹은 모든 경우의 수를 전부 고려하는 알고리즘이다. 일종의 탐색 알고리즘으로, DFS, BFS 로 모두 구현 가능하다. 백트래킹은, 답이 될 수 없는 후보는 더이상 탐색하지 않고 다시 돌아가는 알고리즘이다. 모든 경우의 수를 고려하는 브루트포스보다 더 시간을 절약할 수 있다. 완전탐색의 대표적인 방법에는 DFS가 있다. 재귀를 이용해서 현재시점에서 계속해서 방문할곳을 탐색하고, 방문한다. 반면, 백트래킹은 비효율적인 경로를 차단하고 목표지점에 도달할 수 있는 가능성이 존재하는 곳만 탐색하기 때문에 일종의 가지치기라고도 부른다. 🙋🏻‍♀️ 백트래킹 절차 DFS 수행 - 유망한 노드 검토 - 서브트리 이동 - 백트래킹 수행 1. DFS 수행 : 재귀를 호출하면서 DFS를 그대로..

최장 증가 부분 수열 (LIS,Longest Increasing Subsequence) 이란? 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 "최장 증가 부분 수열"이라고 한다. - 나무위키 🌳 ▷ 예시를 들어보자. [ 3, 5, 7, 9, 2, 1, 4, 8] 다음과 같은 수열이 있다고 하자. 이 수열에서 몇 개의 수를 제거해서 부분수열을 만들 수 있다. 몇 개의 수를 제거해서 오름차순으로 이루어진 수열을 최장 증가 부분 수열이라고 하였는데, 즉, '공차'가 존재하지 않아도 부분수열이라고 본다는 것이다. (규칙적이지 않고 오름차순이면 된다는 뜻) 따라서 위 수열에서 도출될 수 있는 부분수..

Dynamic Programming (동적 계획법) 동적계획법(다이나믹 프로그래밍) 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간을 내어 풀 때 사용한다. - Wikipedia ▷ 코딩테스트에서의 DP 코딩테스트의 단골 문제로 출제되고 있기에 필수적으로 알아야하는 개념 중 하나이다. 간혹 제약사항에 주어지는 숫자의 범위가 크고, 경우의 수가 엄청 많은 문제들이 대부분 DP(동적계획법) 을 활용하여 풀어야 하는 문제이다. Dynamic Programming (동적 계획법) 방법 모든 작은 문제들을 한 번만 풀어야 한다. 따라서 정답을 구한 작은 문제의 답은 어딘가에 메모해놓는..

1. 큐 (Queue) 1.1 큐 (queue)란? 가장 먼저 넣은 데이터를 꺼낼 수 있는 구조 대기행렬을 생각, 먼저 기다린 사람이 먼저 혜택을 받는다 FIFO (FIrst In, First Out) 방식 = LILO (Last In, Last Out) 방식 1.2 큐의 구조 1.3 큐는 어디서 많이 쓰일까? 큐는 주로 운영체제에서 멀티태스킹을 구현하기 위해서 프로세스 스케쥴링 방식을 구현하기 위해 많이 쓰인다 1.4 큐의 용어 Enqueue (인큐) = 데이터를 넣는 기능 Dequeue (디큐) = 데이터를 꺼내는 기능 (큐에서 데이터는 삭제된다.) 1.5 파이썬에서 Queue 구현하기 파이썬에서 인큐와 디큐는 put, get으로 구현할 수 있다. import queue #큐 생성 q = queue...

-- 본 포스팅은 이것이 취업을 위한 코딩 테스트다 with 파이썬 책을 참고하여 작성되었습니다. 1. DFS Depth First Search, 깊이 우선 탐색 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘 주로 스택을 활용하는 방식임 스택 : 후입후출) 동작방식 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 스택의 최 상단 노드에 방문하지 않은 인접노드가 있다면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 동작방식을 아래 그래프를 예시로 살펴보자. 마지막에 "스택이 들어간 순서" 를 한데 모아보면, 1,2,7,6,8,3,4,5 가 된다. ▶ DFS를 코드로 구현해보기 위와..

-- 본 포스팅은 이것이 취업을 위한 코딩 테스트다 with 파이썬 책을 참고하여 작성되었습니다. 1. 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘은 DFS 와 BFS가 있음 2. 그래프 표현 방식 그래프의 구성 : 노드(정점), 간선(Edge) 그래프를 코드로 표현하는 방법은 2가지가 있다 2.1 인접행렬 표현 방식 2차원 배열로 그래프의 연결관계를 표현하는 방식이다. 아래 그래프를 표로 표현하면 오른쪽의 표처럼 표현이 될 것이다. 이 그래프를 2차원 리스트로 구성하게 되면 아래와 같다 INF = 999999 #무한대의 비용 선언 #2차원 배열을 활용하여 그래프를 표현 graph = [ [0, 7, 5], [7, 0 INF], [5, INF, 0] ] print(..