thumbnail

그래프 BFS 문제2 - 어린이날

image.png 문제 파악 답이 될 수 있는 숫자를 구성하는 숫자가 정해져 있으므로, 답을 구성할 수 있는 숫자들을 그래프의 노드로 보고 BFS로 탐색하면서 최소가 되는 답을 찾을 수 있지 않을까 생각했다. 그러나 문제점은 이런 방식으로 탐색할 경우 답이 존재...

약 24시간 전0개의 댓글

그래프 - BFS 문제1 Sorting game

image.png 문제 파악 배열의 원소를 최소 횟수로 뒤집어 정렬된 배열을 만드는 문제이다. 배열의 최대 크기가 8이고 배열이 한 번 뒤집힐 때마다 다른 상태가 되며 정렬된 상태로 나아가야 된다는 점에서 착안해 배열의 현재 순서를 string으로 나타내 그래프...

2일 전0개의 댓글

그래프 - BFS

BFS란 BFS 너비 우선 탐색이란 그래프의 탐색 알고리즘 중 한 가지이다. 너비 우선 탐색은 깊이 우선 탐색과 그래프 탐색 방식의 두 축을 이루는데, 깊이 우선 탐색이 더 이상 경로가 없을 때 까지 계속 한 방향으로 들어가는 것과 달리 시작점과 가까운 노드부터 탐...

2일 전0개의 댓글

펜윅트리 문제1 삽입정렬 시간 재기

문제 풀이 이 문제에는 세 가지 풀이가 있다. 1. 펜윅 트리 활용 펜윅 트리는 구간합을 간단하고 빠르게 구할 수 있는 자료 구조이다. 구간합을 활용해서 이 문제를 푸는 방법은 펜윅 트리의 크기를 문제에서 주어진 정수 범위로 하는 것이다. 모든 정수에 대해여 펜윅...

3일 전0개의 댓글

이진수 마지막 비트와 and연산

마지막 비트 제거 and 연산자를 활용하면 이진수의 마지막 비트를제거할 수 있다. 10의 이진수 표현은 1010이다. 10에서 1을 뺀 9의 이진수 표현은 10의 마지막 비트를 뺀 1000이다. 따라서 10의 마지막 비트를제거하는 방법은 10에서 1을 뺀 값과 an...

3일 전0개의 댓글

펜윅트리

펜윅트리 배열의 구간합을 구하는 데는, 구간 트리를 활용할 수 도 있지만 그 구현이 복잡해 조금 더 단순한 형태인 펜윅트리를 사용하는 것이 더 좋다. 펜윅트리란 배열의 첫 몇 개의 원소인 부분합을 활용하면 구간합도 빠르게 계산할 수 있다는 원리에서 출발한 구조이다....

3일 전0개의 댓글

트리 - 구간트리 문제1 족보 탐험

image.png 문제 파악 트리의 최소 공통 조상을 구해서 트리의 노드에서 노드까지 가는 거리를 구하는 문제이다. 직관적인 방식을 떠올리면 시간 복잡도가 너무 커지게 되고, 트립을 쓰게 되면 구현이 어렵고 구간 트리를 활용한 문제 취지를 벗어나는 것 같아서 구...

3일 전0개의 댓글

트리 - 구간 트리

구간 트리란 image.png 어떤 배열이 주어졌을 때 그 배열의 특정 구간의 최소값을 알고싶다고 하자. 만약 배열 그 자체로 접근하고자 하면 구간에 속한 원소들을 일일이 확인해야 하기 때문에 n의 시간복잡도를 필요로 한다. 이를 효율적으로 수행하기 위한 구조가 ...

2019년 7월 11일0개의 댓글

카카오페이

카카오 페이 모바일에서 실행하는 법 * 핸드폰이랑 pc랑 같은 와이파이로 접속하고 pc ipv4주소를 백엔드 기본폴더에 있는 .configsecret폴더 development.json파일 allowedhosts 항목에 추가 * 카카오 개발자에서 웹 플랫폼 사이트 ...

2019년 7월 10일0개의 댓글

힙 - 문제1 변화하는 중간 값

image.png 문제 파악 새로운 원소가 주어졌을 때 컨테이너의 크기를 늘리면서 중간값을 찾고 그 중간값의 합을 계산하는 문제이다. 처음 생각했을 땐 힙에 값을 push하면 자동으로 정렬이 되니 중간 인덱스의 원소를 반환하면 된다고 생각했다. 그러나 힙은 최대값...

2019년 7월 10일0개의 댓글

image.png 힙이란 이진 검색 트리와 비슷한 형태의 구조를 가지고 있지만 트리보다 더 느슨한 대소 관계 조건을 가지고 있고 더 엄격한 모양 조건을 가지고 있는 구조를 말한다. 이진 검색 트리는 루트보다 작은 노드는 왼쪽 자식, 큰 노드는 오른쪽 자식의 규칙...

2019년 7월 10일0개의 댓글

트리 - 트립 문제1 삽입 정렬 뒤집기

image.png 문제 파악 삽입 정렬 과정에 관한 정보를 바탕으로 정렬되기 전 수열을 찾는 문제이다. 삽입 과정 정보를 인데스로 사용하여 원래 수열의 위치를 하나씩 파악할 수 있으므로 삽입 과정을 vector로, 인덱스를 이용해 찾고자 하는 수 를 찾는 컨테이...

2019년 7월 10일0개의 댓글

트리 - 트립

트립이란 이진 검색 트리는 한 쪽으로 쏠린 형태가 되면 비효율적인 연산이 나타나게 된다. 레드 블랙 트리와 AVL트리 같이 복잡한 트리 구조를 설계하면 항상 일정한 균형성을 보장한 이진 검색 트리를 만들 수 있다. 그러나 이는 실제로 설계하기 매우 어려우므로 가장 간...

2019년 7월 9일0개의 댓글

C++ map 클래스와 upper_bound, lower_bound 메서드

map 클래스 map클래스는 이진 검색 트리 기반의 자료 구조이다. 일반적인 이진 검색 트리는 한 방향으로 쏠린 형태로 만들어져 효율성이 떨어질 수 있는데 map은 레드 트리 구조로 되어 있어서 항상 일정한 효율성을 보장한다. 레드 트리 구조는 직접 구현하기 매우 복...

2019년 7월 9일0개의 댓글

트리 - 이진 검색 트리 문제1 - NERD2

image.png 문제 접근 값을 계산하는 과정에서 값을 검색하고 비교하는 과정이 필요하므로 이진 검색 트리를 활용하는 것이 좋겠다는 생각이 들었다. 이를 위해 C++의 표준 라이브러리 중 이진 검색 트리 기능을 하는 set을 사용하려고 했다. 문제에 대한 값이...

2019년 7월 9일0개의 댓글

트리 - 이진 검색 트리

이진 검색 트리란 image.png 이진 트리란 노드의 자식을 최대 두 개까지만 가질 수 있는 트리를 말한다. 이진 검색 트리는 이진 트리의 왼 쪽 자식을 부모 노드보다 작은 값, 오른 쪽 자식을 부모 노드 보다 큰 값으로 두어 만들어진 트리를 말한다. 이진 ...

2019년 7월 9일0개의 댓글

트리 문제2 - 요새

image.png 문제 파악 원형으로된 요새의 벽을 가장 많이 통과 하는 경우를 구하는 문제이다. 요새의 벽 끼리 겹치는 경우는 없기 때문에 요새가 겹치는 지를 파악하는 아이디어는 쉽게 생각났으나 트리 자료 구조를 표현하는 방식에서 시간이 너무 오래 걸려 포기했...

2019년 7월 8일0개의 댓글

트리 - 문제1 트리 순회 순서 변경

image.png 문제 풀이 전위 표기의 경우 루트 노드가 반드시 맨 앞에 오고 중위 표기에서 그 루트 노드를 기준으로 양 옆을 왼쪽 subtree 오른쪽 subtree로 나눠서 크기가 1이 될 때까지 재귀적으로 호출하는 간단한 문제이다. 먼저 끝난 함수일 수...

2019년 7월 8일0개의 댓글

그래프 DFS - 문제1 감시 카메라

문제 파악 image.png 그래프의 한 정점에서 인접한 정점끼리는 감시 카메라를 공유하는데, 이 때 모든 갤러리를 감시하는 감시 카메라의 최소 대수를 구하는 문제이다. 직관적으로 생각했을 때는 정점 별로 감시 카메라를 둔다고 가정했을 때 인접 정점들을 확인하면...

2019년 7월 8일0개의 댓글

그래프 - DFS와 강결합 컴포넌트

강결합 컴포넌트란 강연결 요소라고도 불리는 강결합 컴포넌트는 유향 그래프 내에서 정의되는 개념이다. 유향 그래프에서 두 정점 사이에서 양 쪽 모두 이동할 수 있는 경로가 존재하면 두 정점은 같은 강결합 컴포넌트(SCC)에 속해 있다고 말한다. 만약 같은 SCC에 속한...

2019년 7월 5일0개의 댓글