본문 바로가기

Problem Solving34

[알고리즘] 유클리드 호제법 & 백준(최대공약수와 최소공배수) 유클리드 호제법 유클리드 호제법을 알기 전에 먼저 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다. 우리가 알고자 하는 유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘이다. (A와 B의 최대공약수는 B와 A를 B로 나눈 나머지의 최대공약수와 같다는 것이다.) 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, r)와 같다는 말이다. (gcd()는 최대공약수를 나타내는 표기이다.) 예시 입력으로 보면, gcd(24, 18) = gcd(18, 6) = gcd(6, 0)인 것이다! 여기서 b가 0이 되는 순간의 6이 바로 최대공약수가.. 2022. 12. 13.
[알고리즘] 이진 트리, 이진 검색 트리 & 백준(이진 탐색 트리, 트리의 순회) 이진트리(Binary Tree) : 노드가 왼쪽 자식(left chile)과 오른쪽 자식(right child)만 가진다. 자식이 없을 수도 있다. (최대 두 개의 자식 노드를 가지는 트리 형태의 자료구조로서, 단순히 값을 저장하기 위한 용도로 사용되기 보다는 효율적인 탐색 혹은 정렬을 위해 사용된다.) 완전 이진 트리(Complete Binary Tree) - 마지막 레벨을 제외하고, 모든 레벨에 노드가 가득 찬다. - 마지막 레벨은 왼쪽부터 채우고 끝까지 꽉 차지 않아도 된다. - Heap, 우선순위 큐에서 사용하는 트리 구조이다. * 힙(Heap): 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리(complete binary tree)를 기본으로 한 자료구조이다. 이진 .. 2022. 10. 12.
[알고리즘] BFS 뿌셔 DFS 뿌셔 BFS - BFS = Breath-First Search - 가까운 노드부터 우선 탐색 : s로부터 거리가 k+1인 한 정점을 만나기 전에, s로부터의 거리가 k인 정점을 모두 발견하는 알고리즘 (CLSR에 적힌 정의) - 큐 자료구조를 이용: 1. 탐색 시작 노드를 큐에 삽입, 방문 처리 => Queue에 들어있는 애들 = frontier 2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 => frontier 갱신 1) 큐에서 popleft() (popleft()한 값 u / deque이기 때문에 popleft()를 통해서 큐의 맨 앞 요소를 빼줌) 2) u의 인접 노드 v 를 방문했는지 확인 3) 방문 안 했으면 큐에 v 삽입 + v의 dist.. 2022. 10. 10.
[알고리즘] 그래프와 트리, 전위순회, 중위순회, 후위순회& 백준(트리 순회) 그래프 그래프는 현상이나 사물을 정점(Vertex) 또는 노드(Node), 간선(Edge)으로 표현하기 위해 사용한다. - 노드(Node) : 위치를 말함, 정점(Vertex)라고도 함 - 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선을 뜻함(Link 또는 Branch라고도 함) - 인접 정점(Adjacent Vertext) : 간선으로 직접 연결된 Vertex(또는 Node) 1) 무방향 그래프(undirected graph) - 방향이 없는 그래프로 간선을 통해 노드는 양방향으로 갈 수 있음 - 보통 노드 A,B가 연결되어 있을 경우 (A,B) 또는 (B,A)로 표기 2) 방향 그래프(directed graph) - 간선에 방향이 있는 그래프로 방향이 가르키는 곳으로만 갈 수 .. 2022. 10. 8.
[알고리즘] 스택 & 백준(탑, PPAP) * Deque을 활용하여 스택을 구현하는게 더 효율적이다. [파이썬/Python] Collections - Deque 들어가며 코딩테스트에 응시할 때 빠르게 찾아볼 수 있도록 따로 정리한 내용입니다. 공부하시기에는 빈약한 내용일 수 있음을 미리 알려드립니다. 공식 문서를 참고할 때에는 대부분의 기업이 mong9data.tistory.com 1. 2493: 탑 문제 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이.. 2022. 10. 8.
[Python] 노드(Node) - 자료구조 기본 단위 노드 관리할 데이터를 보관(존재)하는 곳을 노드(Node)라고 한다. 즉, 자료구조에서 관리하고 있는 정보들 중 하나를 저장하고 있는 단위이다. 주로 연결 리스트라고 불리는 링크드 리스트에서 사용되며 연결리스트에서 노드는 데이터 값 + 포인터로 구성되어 있다. 대체로 자료구조를 공부할 때 이 노드를 클래스로 직접 구현한다. 하지만 자료구조에서 구조적 설계보다 연산(메소드)이나 연산으로 인한 구조적 변화에 학습을 집중해야될 때는 노드를 따로 구현하지 않는다. 이 경우 기본적으로 제공하는 자료형(대표적으로 리스트)으로 주로 진행한다. 즉, 구조적 설계를 필요로 할 때 노드를 클래스로 직접 구현한다. 2022. 10. 7.
[Python] 가장 파이썬스러운 enumerate 활용법 문제의 출력 조건이 정답 조건에 해당하는 원소의 인덱스를 출력하는 것이었는데 enumerate를 활용하여 인덱스를 추출하는 과정을 돌아가지 않고 바로 뽑을 수 있다는 것을 알게 되었다. 일반 for문을 사용하는 것이 가장 파이썬스럽지 않은 방법이라고 한다. ^^ enumerate 함수를 이용하면 출력형식이 무조건 tuple 형식으로 나오기 때문에 인덱스 값만 빼오고 싶거나, 원소값만 빼오고 싶은 경우 위와 같은 두 방식을 이용하여 추출할 수 있다. abc = ['A', 'B', 'C'] # 일반 for문: for 원소 in 목록: # 목록 => 리스트, 튜플, 문자열, 반복자 등 순서가 있는 모든 데이터 타입 for letter in abc: print(letter) # 일반 for문: 리스트의 인덱스와.. 2022. 10. 6.
[Python] 리스트를 join 함수 활용하여 문자열로 만들기 리스트에 있는 특정 str 값들을 뽑아서 어떤 단어이다! 라고 설명하고 싶은데 구현이 안 되는 부분이 있었다. join() 함수를 사용하여 리스트 내의 원소들을 문자열로 합쳐줄 수 있다. join() 함수는 기준을 가지고 문자열로 엮는데 위 사진에서는 공백을 활용하여 문자열을 붙이게끔 만들어주었다. 또한, join() 함수 안에 들어갈 해당 리스트를 넣는데 stack[-4:]를 넣어줬기 때문에 뒤에서 4번째까지의 원소를 의미한다. 뒤에서 네번째까지의 원소를 문자열로 출력하게 되면 PPAP가 나오는 것을 확인할 수 있다. stack = ['P', 'P', 'A', 'P', 'P', 'A', 'P'] print("스택 뒤에서 4번째 원소: ", stack[-4]) print("스택 뒤쪽의 4개 원소: ", .. 2022. 10. 6.
[알고리즘] 이분 탐색, 투 포인터 알고리즘 & 백준(두 수의 합, 두 용액) 이분탐색에 문제를 풀다가 두 용액이라는 문제가 나왔고, start, end, mid를 놓고 계속 풀었기 때문에 mid값을 어떻게 설정해야하는지에 대한 어려움이 있었다. 두 용액 문제의 알고리즘 분류를 보니 두 포인터(- 투 포인터)가 있어서 이를 활용해야함을 알았다. 이분 탐색이란? 정렬된 배열에서 target의 존재 여부와 위치를 알려준다. 재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다. 투 포인터 알고리즘이란? 포인터가 C언어에서의 포인터가 아니다. 정말 말그대로 가리키는 두 개의 포인터라고 생각하면 된다. 이름처럼 양 끝을 각각 포인터로 설정한 다음, 포인터의 위치를 안쪽으로 옮기며 주어진 연산을 반복해 최적값을 찾아내는 방식이다. 투포인터 알고리즘의 장점은 리스.. 2022. 10. 6.

티스토리툴바