전체태그 보기

#알고리즘 (97개의 포스트)

[프로그래머스 고득점Kit] #3 힙
wan088
힙이란? 힙(Heap)은 완전 이진트리의 일종으로서 일반적으로 root에 최소값이 오는 최소힙과 최대값이 오는 최대힙으로 구분된다. 같은 완전이진트리라 그런지 이진탐색트리와도 비슷한데, 이쪽의 경우 좌우와 상관없이 부모노드가 자식노드보다 작다/크다의 조건만을 갖는 트리이기 때문에 조금 다르다. 이를 일종의 반 정렬상태, 느슨한 정렬상태라고 부르기도 한...
[프로그래머스 고득점Kit] #2 스택/큐
wan088
스택 / 큐란? 스택(Stack)은 FIFO(First In First Out) 큐(Queue)는 LIFO(Last In First Out) 스택의 경우, 끝에서 삽입, 확인, 삭제연산이 일어날 경우 사용하고, 큐는 사용범위가 워낙 광범위해서 특정하기 힘든데, 일단 BFS에서 주로 사용한다. 🚀주요 사용하는 기능 in JAVA QueueV...
그래프 알고리즘 정리
wan088
그래프? 정점과 간선들로 이루어진 집합. 즉 트리 역시 그래프에 속한다고 할 수 있다. - 그래프를 표현하는 세가지 방법 1.간선 리스트 말그대로 배열에 간선들을 저장한다. 가장 간단하게 구현되지만 한 정점의 간선에 대한 정보를 얻으려면 모든 간선리스트를 탐색해야 하기 때문에 벨만-포드 알고리즘과 크루스칼 알고리즘 같은 일부 알고리즘이 아...
[프로그래머스 고득점Kit] #1 해시
wan088
해시란? Key-value쌍으로 데이터를 저장하는 자료구조 🚀주요 사용하는 기능 in JAVA HashMapK, V map 타 언어의 Dictionaray와 같은 역할을 하는 자료구조. 가장 중요한 점은 역시 기적적인 Hash의 성능을 통해 저장된 Key에 해당하는 Value를 O(1)의 시간복잡도로 검색이 가능하다는 것. (충돌 및 재해시를 ...
qoszino

책을 샀다

2019년 8월 7일3개의 댓글
알고리즘의 이해를 위해서 책을 사봤다. Dimo라는 유튜버분의 추천을 받은 '누구나 자료구조와 알고리즘' 그리고 '알고리즘, 인생을 계산하다' 라는 책이다. 오늘 도착했고, 비교적 얇은 전자의 책을 조금 읽어봤는데 깃헙에 예제소스도 따로 있고, 쉽게 설명해주어서 개념을 다시 잡기에 좋은 것 같다. 더 읽어봐야지 알겠지만! 그리고 인생을 계산하는 알고리즘...
BFS는 낯설어서
skyepodium

BFS는 낯설어서

2019년 7월 28일2개의 댓글
BFS (Breath-First-Search, 너비 우선 탐색) 은 시작점에 인접한 다른 정점을 모두 방문하고, 다른 정점에 대해서도 인접한 또 다른 정점을 모두 방문하는 방법입니다. 여기서, 인접하다는 의미는 두 정점이 하나의 간선으로 연결되어 있다는 의미입니다. 라고.. 저는 누가 물어보면 말할래요 ~찡긋 그림을 통해 설명드리겠습니다. ...
코드포스 520B Two Buttons
skyepodium

코드포스 520B Two Buttons

2019년 7월 27일0개의 댓글
빨간색, 파란색 고르는것은 항상 매트릭스가 생각나 두개의 버튼 n에서 m을 만들기 위한 최소 버튼 클릭수를 계산하는 문제 내 마음대로 번역 바시야(Vasya)는 신기한 장치를 찾았습니다. 패널의 앞부분은 빨간 버튼, 파란 버튼, 양의 정수를 보여주는 디스플레이가 있습니다. 1) 빨간 버튼을 누르면, 장치는 디스플레이의 숫자에 2를 곱합니...
백준 16236 아기 상어
skyepodium

백준 16236 아기 상어

2019년 7월 21일0개의 댓글
문제 아기 상어가 물고기를 잡아 먹을 수 있는 시간을 구하는 문제 ~으아 문제가 정말 길어요~ 1. n 공간의 크기 (2 = n = 20) 2. 지도의 크기 n * n, (1 * 1 에는 최대 물고기가 1마리 있습니다.) 3. 상어, 물고기 크기는 모두 자연수입니다. 4. 지도 정보 1) 상어 - 위치 - 상어의 위치는 숫자 9로 표시...
pa324

boj 2193 - 이친수

2019년 7월 17일0개의 댓글
~c++ include iostream using namespace std; long long d[91]; int main() { int n; cin n; d[1] = 1; d[2] = 1; for (int i = 3; i = n; i++) { d[i] = d[i - 1] + d[i-2]; } cout d[n] endl; ret...
pa324

BOJ 11057 오르막 수

2019년 7월 16일0개의 댓글
~c includestdio.h int dp1001; int main(){ int count = 0; int i,j,k,n,m; scanf("%d",&n); for(i = 0; i = 9; i++){ dp1 = 1; } for(i = 2; i = n; i++) { for(j = 0; j = 9; j++){ for(k = j; k =...
pa324

BOJ10844 - 쉬운 계단 수

2019년 7월 16일0개의 댓글
문제 45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 입력 첫째 줄에 N이 주어진다. N은 1보다 ...
pa324

백준9095 - 1,2,3,더하기

2019년 7월 15일0개의 댓글
설명 4를 만들 수 있는 조합은 아래와 같습니다. ~ 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 ~  끝에 있는 숫자를 기준으로 오름차순으로 정렬하면 규칙을 찾을 수 있습니다. 끝자리가 1로 끝나는 경우에서 끝에 있는 1을 제외하고 자세히 살펴보겠습니다.  1+1+1, 1+2+1, 2+1+1, 3인데 3을 제외하...
pa324

백준11727 - 2×n 타일링 2

2019년 7월 15일0개의 댓글
문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 해당 문제는Dynamic Programmin으로 해결할 수 ...
pa324

BOJ 1463 - 1로 만들기

2019년 7월 13일0개의 댓글
문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 10...
doontagi
image.png 문제 파악 삽입 정렬 과정에 관한 정보를 바탕으로 정렬되기 전 수열을 찾는 문제이다. 삽입 과정 정보를 인데스로 사용하여 원래 수열의 위치를 하나씩 파악할 수 있으므로 삽입 과정을 vector로, 인덱스를 이용해 찾고자 하는 수 를 찾는 컨테이너를 트립으로 두면 문제를 NlogN의 시간 복잡도로 해결할 수 있다. 숫자를 하나씩 ...
doontagi
image.png 문제 접근 값을 계산하는 과정에서 값을 검색하고 비교하는 과정이 필요하므로 이진 검색 트리를 활용하는 것이 좋겠다는 생각이 들었다. 이를 위해 C++의 표준 라이브러리 중 이진 검색 트리 기능을 하는 set을 사용하려고 했다. 문제에 대한 값이 들어오면 그 값보다 큰 값을 가진 인덱스들에 대해 라면의 값을 확인하려고 했다. se...
doontagi

트리 - 이진 검색 트리

2019년 7월 9일0개의 댓글
이진 검색 트리란 image.png 이진 트리란 노드의 자식을 최대 두 개까지만 가질 수 있는 트리를 말한다. 이진 검색 트리는 이진 트리의 왼 쪽 자식을 부모 노드보다 작은 값, 오른 쪽 자식을 부모 노드 보다 큰 값으로 두어 만들어진 트리를 말한다. 이진 검색 트리는 효율적인 연산들을 제공한다. 이진 검색 트리는 어떤 값을 찾을 때 연결 리스트...
doontagi

트리 문제2 - 요새

2019년 7월 8일0개의 댓글
image.png 문제 파악 원형으로된 요새의 벽을 가장 많이 통과 하는 경우를 구하는 문제이다. 요새의 벽 끼리 겹치는 경우는 없기 때문에 요새가 겹치는 지를 파악하는 아이디어는 쉽게 생각났으나 트리 자료 구조를 표현하는 방식에서 시간이 너무 오래 걸려 포기했다. 가장 많이 겹치는 구간을 구하는 방법은 트리 구조로 된 모습에서 가장 긴 리프에서...
doontagi
문제 파악 image.png 그래프의 한 정점에서 인접한 정점끼리는 감시 카메라를 공유하는데, 이 때 모든 갤러리를 감시하는 감시 카메라의 최소 대수를 구하는 문제이다. 직관적으로 생각했을 때는 정점 별로 감시 카메라를 둔다고 가정했을 때 인접 정점들을 확인하면서 감시 카메라가 설치 되었는지 안되었는지를 체크 하면서 하나씩 늘려나가야 되는데 그 시작...
doontagi
강결합 컴포넌트란 강연결 요소라고도 불리는 강결합 컴포넌트는 유향 그래프 내에서 정의되는 개념이다. 유향 그래프에서 두 정점 사이에서 양 쪽 모두 이동할 수 있는 경로가 존재하면 두 정점은 같은 강결합 컴포넌트(SCC)에 속해 있다고 말한다. 만약 같은 SCC에 속한 두 정점 중 한 정점이 또 다른 정점과 같은 SCC에 속해 있으면 세 정점간 오고 가는 ...