알고리즘

설명 입력의 범위가 5000으로 작기 때문에 queue를 이용해 풀면 되지만 배열에서 shift 연산자를 쓰는 것에 비용이 크다고 판단해서 자료구조 연습겸 Circular Linked List를 이용해 풀었다. 그렇다고 일반적인 Circular Linked List는

JS의 경우 Stack 클래스를 구현하지 않고 일반 배열로 선언해서 풀어도 되지만 이번 문제도 자료구조 복습겸 Stack 클래스를 직접 구현해서 풀었다.그나마 코드량을 줄일 수 있게 작성한 부분이 있어 아래에 적어 본다.여기서 JS 객체의 성질을 이용해 stack\[c

전형적인 stack을 이용해서 푸는 문제'('일 때는 스택에 쌓고 ')'일 때는 stack에서 빼서 올바른 괄호 쌍인지 판단하면 된다.JS풀이는 이전에 푼 문제에서 Stack 클래스를 구현해놔서 구현한김에 굳이 Stack class를 복붙해서 가져와서 '('를 stac

자료구조 Queue를 구현해서 해결할 수 있는 문제.JS는 언어적으로 Queue를 지원하지 않아서 Queue Class를 선언해서 풀었다.문제에서 주어지는 N이 200만으로 작기 때문에 JS의 배열을 Queue로 생각하고 구현해도 되지만 이전에 코테풀 때 Array의

자료구조 Queue를 사용해서 푸는 문제.문제에서 요구하는대로만 풀면 풀리는 쉬운 문제.JS풀이와 C++풀이는 모두 동일하지만 JS는 이전에 큐 2문제에서 사용한 Queue 자료구조를 그대로 가져와 풀었다.

자료구조 Deque 구현 문제.JS에서는 Deque 자료구조를 제공하지 않아 직접 double-linked-list로 구현.구현 자체는 이전에 구현했던 자료구조 Queue와 유사하다.\[참고]c++에서는 역시 Deque 자료구조를 제공하고 있기 때문에 해당 자료구조 사

문제 설명만 보고 무슨 말인지 이해가 가지 않아 유튜브 영상에서 해당 문제에 대한 설명을 들었다. (영상링크)문제를 이해하니 그냥 Stack 자료구조를 사용해서 쉽게 풀 수 있는 문제였다.JS에서 stack은 그냥 배열로 사용해도 되지만 이전에 푼 스택문제에서 사용한

후위 표기식에 대한 정확한 계산법은 구글링을 통해 알았다.스택을 이용하면 될꺼라 아이디어가 떠올랐고 JS는 일반 배열을 스택으로 사용해서 풀고, C++은 제공하는 stack 자료구조를 활용했다.JS 풀이의 경우 eval 함수를 통해 연산식을 바로 계산할 수 있다는 점이

이전에 프로그래머스에서 풀어본 문제 유형(well-known이라고 해야하나..?)너무 문제가 똑같고 풀이가 기억나서 그대로 풀었다.레이저에 해당하는 ()부분을 다른 문자로 replace하고, 그 문자가 레이저라고 생각하고 answer에 값을 더해줬다.값은 레이저를 만나

와 너무너무 어이없게 실수를 해서 거의 2시간 정도 푼 것 같다...처음에 JS로 풀었고, JS의 1번 풀이와 같이 풀었는데 시간초과 나길래'아 역시 JS배열은 shift 연산에서 비용이 많이 들어 시간초과가 나는구나'라고 생각했다.그래서 이전 자료구조 Queue를 사

이번에는 Node.js 풀이가 없다...이번 문제 덕분에 삽질을 또 엄청나게 했다.본인은 처음에 Node.js로 먼저 풀고 c++로 푸는데 아무리 Node.js로 풀어도 메모리 초과가 나길래 c++로 풀었다.c++로 풀고나서 백준의 node.js 정답 코드를 확인했는데

괄호쌍은 곧 Stack 문제이다.문제는 숫자를 계산할 때 어떻게 하냐였는데 num이라는 변수의 초기값을 1로 셋팅하고(와 \[를 만나면 각각 2와 3을 곱해준다.그러다가 )와 ]를 만나면 계산한 값을 더해주고 각각 2와 3으로 다시 num을 나눠준다.이때 값을 더해주는

오랜만에 골드 문제를 푸니 어려웠다..재귀를 통해 dfs를 구현하여 문제를 해결했다.괄호쌍의 인덱스를 들고 있고, 그 괄호쌍을 제거할지 말지를 결정하여result에 담아줬다.((0))과 같은 input이 주어지면 첫 번재 괄호쌍을 제거하나 두 번째 괄호쌍을 제거하나 결

문제를 보자마자 생각나는 건 전체를 다돌면서 푸는 O(n^2) 풀이였다.하지만 문제 조건의 N이 500,000이었기 때문에 O(n^2)의 풀이는 포기하고 다른 풀이를 생각했다.결국 생각해내지 못하고 다른 사람의 풀이를 참고했는데, 스택을 이용한 풀이였다.앞에서부터 스캔

문제 조건에 N이 최대 20만이기 때문에 O(N^2)풀이는 풀지 못한다는 것을 파악했다.고민해보았지만 문제 풀이 방법이 생각나지 않아 다른 사람의 풀이를 참고했는데 스택 자료구조를 사용해서 풀면 되었다.x축에 맞닿는 원 좌표기준으로 왼쪽을 괄호의 open 오른쪽을 괄호

아직 골드 정도의 난이도는 스스로 풀이를 떠올리는데에 힘이 드는 것 같다.다른 사람의 풀이를 참고했고 이 문제는 스택 자료구조를 사용해서 풀 수 있다.주어진 문자열을 앞에서 부터 하나씩 체크하면서 answer에 결과를 더해준다.일반 알파벳일 경우 그냥 더해주고, 다른

이전에 큐2 문제를 풀어서 범위도 더 적고 큐의 구현사항은 동일하기 때문에이번에는 JS로 풀지 않고 C++ queue STL 사용법 복습겸 C++으로만 풀었다.

전형적인 스택문제... 이젠 괄호 얘기만 꺼내도 스택이라고 떠오른다.크게 어려운 점은 없었고 C++의 경우 띄어쓰기로 input을 나눠받아 일반적인 cin >> 을 사용하면 input 개수가 달라져 한 줄씩 입력받는 getline 함수를 검색해서 알게 되었다.

처음에 문제 이해를 못했는데 문제를 이해하면 바로 풀리는 문제A끼리 괄호쌍, B끼리 괄호쌍이라고 생각하고 풀면 된다.문제말대로 문자 각자 위에 선을 그은 후에 같은 문자쌍끼리 선이 겹치지 않고 묶이는지 확인하면 된다. -> 이게 괄호쌍 문제랑 동일하다.

자료구조 Deque를 사용해서 푸는 문제JS의 경우 덱이 없어서 완벽한 덱은 아니지만 문제에서 주어진 N은 50보다 작거나 같은 자연수라는 조건 때문에 Array를 extends하여 심플하게 구현했다.그리고 필요한 rotate 함수를 파이썬의 덱처럼 멤버변수로 추가하여

일반적인 배열을 쓰면 시간초과 날 것같아 JS는 포기하고 C++에서 제공하는 자료구조를 사용해서 풀려고 했다.다른 사람의 풀이를 참고했는데 C++은 deque를 2개둬서 커서를 기준으로 leftDQ, rightDQ를 둬서 문제의 요구사항대로 연산을 수행하고 결과를 리턴

Deque 자료구조를 사용해서 푸는 문제JS의 경우 Deque가 없기 때문에 이전에 푼 문제에서 Deque 자료구조를 만들었던 것을 가져와서 풀이했다.그리고 iterator 프로토콜을 사용해 spread 연산자를 사용해서 마지막 출력을 쉽게 할 수 있도록 generat

index로는 바로 배열의 요소에 접근할 수 있지만 poketmon의 이름으로는 바로 인덱스를 알려면 검색을 해야 한다. 바로 알 수 있도록 해쉬맵 자료구조를 사용하면 된다.JS의 경우 Map을 사용해도 되지만 기본으로 제공하는 객체에 해당 인덱스를 담아서 답을 구했다

같은 문자가 주어지지 않아서 map이나 set이나 아무거나 상관없이 써서 풀어도 되는 문제c++은 set을 써볼겸 set을 사용해서 풀었다.

C++의 priority_queue는 최대 힙이므로 그냥 STL을 사용해서 풀었다.JS의 경우 Heap 자료구조가 없어서 직접 구현했는데 실수를 좀 해서 다른 사람의 풀이를 참고했다.

Deque 자료구조를 사용해서 풀었다. direction 변수를 하나 정해놓고 마지막에 역방향이라면 역방향으로 return하고 정방향이면 그대로 return하는 방식을 사용했다.처음에 문제요건이 10만 \* 100 이라 1000만 정도면 일반배열로도 통과되지않을까 했지

이 문제를 보고 stack을 떠올릴 수 있다는게 부럽다...처음에 감을 못잡아서 다른 사람의 풀이를 보고 스택으로 안풀고 그냥 hashmap으로 하면 되는거 아닌가해서 풀었는데 예제 testcase만 통과하고 나머진 실패했다.hashmap을 사용한 풀이는 0을 만나기전

stack을 두 개 사용해서 푸는 문제정방향, 역방향으로 스택을 사용해서 현재 위치 기준으로 높은 것들의 집합의 개수를 더해준다. 그리고 자기 자신을 추가해서 이후에 찾는 빌딩의 높이가 더 낮을 경우 자기 자신도 더 높은 빌딩에 추가되므로 이렇게 계산한다.마지막으로 빌

c++의 priority_queue를 이용해서 풀었다.해당 자료구조의 사용법을 익힐 수 있는 문제였다.(compare 구조체 관련)이 문제는 JS에서 priority queue가 없어 나중에 priority queue 자료구조를 직접 만든 다음에 다시 풀어서 다시 글을

HashMap을 이용해서 푸는 문제JS는 기본 object를 사용했고, C++은 map STL을 사용해서 풀었다.C++ map 사용법을 익힐 수 있었던 문제다.

메모리 제한이 12MB...minHeap을 하나 두고 입력을 받을 때마다 넣으면서 Heap의 사이즈가 N보다 커지만 계속 pop 해줘서 결과를 모두 수행한 Heap의 top이 정답이 되는 문제p.s. 이 문제도 NodeJS는....no답

우선순위 큐를 두 개(minHeap, maxHeap)두고, 각각의 sync를 조절해서 풀면 되는 문제.뭔가 이번 문제부터 Node.js로 풀면 백준의 경우 같은 로직이어도 메모리초과가 너무 빈번하게 일어나서 백준은 C++로만 풀어야 하나 싶다...

maxHeap과, minHeap을 두 개 동시에 관리하면서 푸는 문제.두 개의 Heap의 sync를 맞춰야 해서 arr을 체크용으로 두고, 삭제되었는지를 판단해서 계산

왼쪽에 최대힙, 중앙값, 오른쪽에 최소힙으로 구성한다.숫자를 입력받고, 현재 middle 값과 비교해서 왼쪽에 넣을지 오른쪽에 넣을지 비교.홀수개 입력받을 때마다 middle 값을 적절히 조절해준다.

dfs, bfs 두 가지 모두 풀 수 있는 문제dfs는 보통 stack 또는 재귀를 활용해 풀고,bfs는 queue를 사용해서 푸는 것을 복습했다.

전위순회, 중위순회, 후위순회 복습 문제오히려 이 문제는 input 값을 셋팅하는 것이 더 어려웠던 것 같다.

분할 정복법으로 푸는 문제.오랜만에 분할 정복법 풀이를 복습할 수 있었다.

삭제되었다는 노드의 표시를 -2로 두고,삭제된 노드를 부모로 갖는 모든 노드를 삭제시킨다.그 후에 삭제가 되지 않았으면서 부모가 없는 노드의 갯수를 세서 리턴해주었다.

전위 순회로 초기에 돌기 때문에 첫 번째 값이 루트 노드가 된다.루트 노드를 정하고 data를 모두 확인하면서 이진 검색 트리를 만족하도록 트리를 구성했다.트리를 구성한 후에는 후위 순회를 돌아 출력하여 답을 구했다.

개념 자체를 알고 있으면 쉬운 문제...싸이클이 없는 노드의 경우 무조건 해당 간선이 단절선이 된다.그리고 해당 정점에서 연결된 간선이 2개 이상일 경우 해당 정점이 단절점이 된다.

생각해보면 확률이 동일하기 때문에 leaf 노드에만 빗물이 쌓이게 된다.따라서 확률은 (leaf 노드의 수) / W가 된다. 그래서 leaf 노드의 수를 dfs로 찾아준 후에 정답을 반환했다.

풀이 자체는 쉬웠다. 간선에 parent와 children이라는 변수를 저장해서 셋팅한 후에 찾고자하는 두 노드의 공통 조상을 찾기 위해 첫 번째 target1의 공통 조상을 모두 set 자료구조에 담고, 이후 두 번째 target2의 공통 조상을 탐색하면서 해당 조상

생각해보면 -1이 나올 경우가 N이 1과 3일때 뿐이어서 해당 숫자일 경우 -1을 리턴해줬다.나머지는 greedy 문제답게 최대한 5원짜리 동전을 많이쓰려했고, 많이쓰려했지만 나머지가 홀수일 경우 하나빼주면 짝수가 되서 무조건 2로 나누어 떨어지기 때문에 아래와 같이

문제 조건대로만 풀면 되는 문제.그나마 아이디어로는 cache를 set 자료구조로 둬서 이미 존재했던 수인지를 판단하기.이미 존재한 경우 루프를 빠져나오고 cache의 사이즈를 리턴하면 정답을 얻을 수 있다.