profile
Programmer
post-thumbnail

Javascript로 Deque를 직접 구현하는 이유

 Javascript로 Queue자료형을 통해 BFS관련 로직을 짜려고 하였다. 하지만 기존에 사용하던 python과는 다르게 <span style='background-color:   대신 javascript에는 배열의 첫번째 요소를 뽑아먹을 수 있는 shift

2022년 5월 18일
·
0개의 댓글
·
post-thumbnail

[JS] Leetcode.587 Erect The Fence

문제 링크 : https://leetcode.com/problems/erect-the-fence/ 이 문제는 Convew Hull(볼록 껍질) 알고리즘으로 대표적으로 세가지 방법이 존재합니다. 그 중 저는 MonotoChain 방법을 사용하였습니다. Convew

2021년 9월 4일
·
0개의 댓글
·
post-thumbnail

[JS] Leetcode 565. Array Nesting

문제 링크 : https://leetcode.com/problems/array-nesting/코드 설명 : k -> numsk -> nums\[numsk] 이런 순으로 탐색하기 때문에 아무래도 탐색했던 것들을 다시 탐색하는 경우가 발생할 수 있다. s0 =

2021년 9월 3일
·
0개의 댓글
·
post-thumbnail

Leetcode 146. LRU Cached

문제 링크 : https://leetcode.com/problems/lru-cache/Map 자료형을 Cache Memory로 구현하였다. 자세한 것은 코드를 보면서 설명하도록 하겠다. 생성자를 통해 cache 메모리의 총 크기와 cache 메모리를 담을 Ma

2021년 8월 31일
·
0개의 댓글
·
post-thumbnail

[Segment Tree] 백준 - 최솟값과 최댓값 2357번

최솟값과 최댓값 2357번N(1 ≤ N ≤ 100,000)개의 정수들을 구간별로 지정하여 선형적으로 최대 최소를 구하려면 상당한 시간이 소요된다. (시간복잡도 O(n^2)). 따라서 세그먼트 트리를 통해 풀 경우 O(logn)으로 구간을 탐색하기 때문에 훨씬 빠르게 최

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[Segment Tree] 백준 - 구간 합 구하기 2042번

구간 합 구하기구간 합 구하기가 단순하게 보면 굉장히 쉬울 수 있다. 단순히 선형적으로 입력받은 구간에 따라 값을 넣고 더해주면 되기 때문이다. 하지만 더하는 과정의 시간 복잡도는 O(n)이 걸리고 구간을 찾는 과정 또한 O(n)의 과정이 걸리게 됩니다. 따라서 우리는

2021년 6월 6일
·
0개의 댓글
·

트리

많은 자료 구조들은 기본적으로 선형 구조를 나타내기 위해 사용됩니다. 하지만 세상은 이것만으로 표현할 수 있을 만큼 만만치 않습니다. 선형으로 표현하기 어려운 형태의 자료 중 흔한 것으로 계층 구조가 있습니다. 자료 간 상하위 관계나 포함 관계가 존재하는 경우 계층

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[Greedy] 백준 - 센서 2212번

센서 2212번사실 문제를 이해하는 데 있어서 상당히 오랜 시간이 걸린 문제이다.예를 들어 입력받은 리스트가 1 6 9 3 6 7이고좌표상으로 표현하면 다음과 같다. Q. 만약 집중국이 하나라면 어떨까??A. 1~9까지의 모든 센서들을 감지해야 하므로 수신 가능 영역의

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[Greedy] 백준 - 단어 수학 1339번

단어 수학 1339번ABCDE + GCG를 예를 들어 살펴보면 자릿수가 제일 큰 수가 제일 큰 수인 9가 들어와야 하므로 A 는 9라는 것을 알 수 있다. 이런 식으로 자릿 수 순서대로 수를 배치할 수 있다. 하지만 C,G의 경우를 살펴보자.C와 G중 어떤 값을 더 큰

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[분할정복] 백준 - 히스토그램에서 가장 큰 직사각형 6549번

히스토그램에서 가장 큰 직사각형 6549번 이 문제는 해당 막대 그래프에 연결된 모든 직사각형들의 넓이를 모두 순회(즉, 2중 for문을 사용한다. )하여 풀면 쉽게 풀 수 있다. 하지만 이 경우 시간복잡도가 O(n^2)이다. 입력크기가 1,000,000,000이기

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[분할정복] 백준 - 버블 소트 1517번

버블 소트 1517번O(N^3)$ 알고리즘: 크기 2560인 입력까지를 1초 안에 풀 수 있습니다. 이때 $2560^3$은 대략 16억입니다.O(N^2)$ 알고리즘: 크기 40960인 입력까지를 1초 안에 풀 수 있습니다. 이때 $40960^2$은 대략 16억입니다.O

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[분할정복] 백준 - Z 1074번

Z 1074번 쿼드트리와 비슷한 방식으로 분할정복으로 문제를 풀려고 했으나 재귀함수다 보니 계속해서 시간초과문제가 발생하였다. 그래서 그냥 반복문으로 1,2,3,4분면을 구분하여 문제를 풀었다.

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[분할정복] 백준 - 행렬 곱셈 10830번

행렬 곱셈 10830번 A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. 이때 제곱의 크기를 나타내는 B의 크기가 1 ≤ B ≤ 100,000,000,000이다. 따라서 단순하게 행렬의

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[분할정복] 백준 - 색종이 만들기 2630번

색종이 만들기쿼드 트리의 문제와 유사한 문제와 코드라서 자세한 설명을 보고 싶으면 목록열기 클릭 -> 쿼드트리 코드를 한번 보시면 이해하기 쉬울 것이다.

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[분할정복] 백준 - 쿼드 트리 1992번

쿼드 트리 1992번이때, x는 w,b가 섞여있을때 나타낸 표시이다. (그림을 설명을 위해 퍼 온것이기 때문에 코드에서는 x에 대한 구현을 하지는 않을 것이다.) 분할 정복은 무엇인가? 우리는 재귀함수를 통해 수열이 1의 값이 될 때까지 분할한 후 병합하는 과정이다.

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[분할 정복] 카리츠바의 빠른 곱셈 알고리즘

다음과 같은 과정은 배열(1,2,3,4)에 있는 각 항들에 대하여 모든 배열(5,6,7,8)들의 각 항에 대해 모두 비교하기 때문에 O(n2)과 같은 시간 복잡도가 소요된다. 카라츠바의 빠른 곱셈 알고리즘은 수백, 수만자리나 되는 큰 두개의 정수를 곱하는 알고리즘이

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[Greedy] 백준 - 과제 13904번

하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다.웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오. 대표적인 그리디 문제이다. 그리디의 많은 문제들

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[Greedy] 백준 - Byte Coin 17521번

Byte Coin 17521번 요일 수 n, 초기 현금 W, 1일부터 n일까지 각 요일의 바이트 코인 가격이 주어질 때, n일 날 보유하고 있는 모든 코인을 매도할 때 보유하게 될 최종 현금의 최댓값을 출력하는 프로그램을 작성하시오.

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[Greedy] 백준 - 게임을 만든 동준이 2847번

게임을 만든 동준이 2847번 각 레벨 별로 문제들의 배점이 점점 증가하게 만들고 싶다. 각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구하는 프로그램을 작성하시오. 점수는 항상 양수이어야 하고, 1만큼 감소시키는 것이 1번이다. 항상 답

2021년 6월 6일
·
0개의 댓글
·
post-thumbnail

[DP] 백준 - 양 3154번

양 3154번 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대를 우리에서 쫓아낸다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다. 살아남은 양과 늑대의 수를 출력하는 프로그램을 작성하라. 전형적인 dfs,bfs 문제이

2021년 6월 6일
·
0개의 댓글
·