자바스크립트 알고리즘 : 이분검색
이분검색을 통해 O(logN)의 복잡도로 탐색하는 방법을 배웁니다.
이분검색을 통해 O(logN)의 복잡도로 탐색하는 방법을 배웁니다.
GET 요청을 통해 데이터를 받아오고, 화면을 구성하는 문제입니다. App.js 아래 Breadcrumb, Nodes 두가지만으로 표현되다가, 이미지 파일 클릭 혹은 로딩시에 Modal을 뛰워주는 간단한 구조입니다.
입출력을 리스트 자료구조로 강제 받는 문제입니다. 문제에서 제공하는 메서드를 활용해서, 두 정렬된 리스트를 하나의 정렬된 리스트로 병합하면 됩니다.
투포인터 알고리즘을 응용하여 풀이했습니다. 1 ≤ l ≤ m, m+1 ≤ r ≤ N 의 조건을 살펴보면, l의 끝은 m이고, r의 시작은 m+1 이므로 두 배열은 연속해야만 하는 것을 알 수 있습니다. 따라서 l, m, r 세가지 포인터를 가지고, 첫번째 배열, 두번째 배열의 합계...
프로그래머스에서 제공하는 과제입니다. 검색어를 입력하면, 해당 키워드에 맞는 검색단어를 서버에서 받아오고 목록을 렌더링 하면 됩니다. 단, 시간은 3시간이 주어지고 다른 라이브러리 사용없이 순수 자바스크립트만으로 완성시켜야하므로 탄탄한 기본기가 요구되는 과제입니다.
전형적인 BFS 탐색 문제입니다. 2차원 좌표에서, 바이러스의 숙주가 될 좌표가 주어지고 (종류 1, 2) 상하좌우로 쭉 퍼져나갑니다. 이미 감염됬거나 치료제가 있을 경우에는 퍼지지 않지만, 다른 종류의 바이러스가 감염중일때 만난다면 종류 3으로 변하는게 조건입니다. 이는 진행거리...
같은 타입의 괄호로 닫을 수 있는 것은 물론이고, 순서도 지켜야한다고 명시되있습니다. 가령 ({)} 같은 형태로 주어진다면 false를 리턴해야할겁니다. 그래서 단순히 삽입할 원소와 배열 맨뒤의 원소만 비교하면 되기 때문에 스택 자료를 이용하여 풀이할 수 있는 문제입니다.
언뜻 배열로 착각하고 reverse같은 메서드들을 시도해볼 수 있지만, List의 형태로 주어지기때문에 배열에서 사용하는 메서드들을 사용할 수 없습니다.문제 설명에서, 각 List가 어떻게 구성되는지 알수있는 함수가 주어집니다.
문자열로 이루어진 배열이 주어집니다. 이 때 각 문자의 공통 접두사를 출력하면 되는 문제입니다.
연속된 두개의 문자의종류에 따라 값이 변경될 수 있습니다. 따라서 그 둘이 예외 케이스인지 확인해보고 그에 따라 적절한 값을 더해줍니다.
배열내 두 숫자를 더했을때, target을 만들 수 있는 두 숫자를 출력하는 문제입니다. 첫문제니까 가볍게 완전탐색으로 풀이했습니다.
해당 게시글은 Sukhjinder Arora의 “Hoisting in Modern JavaScript - let, const, and var” 를 읽고 번역 및 요약한 글입니다.
해당 게시글은 Eric Elliott의 “Master the JavaScript Interview: What is a Closure?” 를 번역하고 요약한 글입니다.
7-9. 결혼식
7-8. 회의실 배정
7-7. 좌표 정렬
7-6. 장난꾸러기 현수
7-5. Least Recently Used (카카오 캐시 문제 변형)
7-4. 삽입 정렬
7-3. Special Sort (구글 인터뷰)
7-2. 버블 정렬
7-1. 선택 정렬
6-7. 교육과정설계
6-6. 공주구하기
6-5. 쇠막대기
6-4. 후위식 연산 (postfix)
6-3. 크레인 인형뽑기 (카카오)
6-2. 괄호문자제거
6-1. 올바른 괄호
5-8. 모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)
5-7. 아나그램(해쉬)
5-6. 학급 회장(해쉬)
5-5. 최대 매출
5-4. 연속 부분수열 2
5-3 연속 부분수열 1
5-2. 공통원소 구하기
5-1. 두 배열 합치기
4-5. K번째 큰 수
4-4. 졸업 선물
4-3. 멘토링
4-2. 뒤집은 소수
4-1. 자릿수의 합
3-5. 문자열 압축
3-4. 가장 짧은 문자거리
3-3. 숫자만 추출
3-2. 유효한 팰린드롬
3-1. 회문문자열
2-7. 봉우리
2-6. 격자판 최대합
2-5. 등수구하기
2-4. 점수계산
2-3. 가위 바위 보
2-2. 보이는 학생
2-1. 큰 수 출력하기
1-17. 중복단어제거
1-16. 중복문자제거
1-15. 가운데 문자 출력
1-14. 가장 긴 문자열
1-13. 대소문자 변환
1-12. 대문자로 통일
1-11. 대문자 찾기
1-10. 문자 찾기
1-9. A를 #으로
1-8. 일곱 난쟁이
번외. forEach, map, filter, reduce method 작동 원리
1-7. 10부제
1-6. 홀수
1-5. 최솟값 구하기
1-4. 1부터 N까지의 합
1-3. 연필 개수
1-2. 삼각형 판별하기
1-1. 세 수 중 최솟값
웹 시작페이지로 사용할 수 있는 할일 목록을 만들려고 했습니다. 구현한 기능으로는 다음과 같습니다.
왜냐하면 각 정점들이 같은 부모를 가지고 있으면 하나의 집합임을 알 수 있습니다. 만약 두 정점이 이미 같은 집합일때 (같은 부모를 가지고 있을때), 두 정점을 이으면 사이클이 발생합니다.
1 부터 시작해서 각 숫자의 최적의해(최단거리 배열 히스토리)를 저장해두고 재사용하는게 핵심입니다. 가장 간단한 경우인 1일 경우부터 생각해보겠습니다.
정수를 담은 자료구조를 다루는 문제입니다. 명령은 I 와 D 두가지로 주어집니다. 이 때 D 명령을 통해 가장 큰 값을 빼거나 가장 작은 값을 뺄 수 도 있습니다. 따라서 항상 적은 시간복잡도로 최대값, 최소값을 제거할 준비가 되있어야 합니다.
DP로 풀이할 수 있는 문제입니다.
이분 그래프란, 정점들이 두 그룹으로 나뉘어지고, 같은 그룹의 정점끼리는 이어지지 않은 구조를 이야기 합니다. 이는 BFS 혹은 DFS 탐색을 통해 파악할 수 있습니다.
임의의 스택 2개 left와 right를 만들었습니다. 두 배열 사이에 포인터가 존재한다고 생각하면 이해하기 쉽습니다.
큐 자료구조 혹은 수학적 접근을 통해 해결할 수 있는 문제입니다. 저는 큐 자료구조로 풀이했는데 핵심적인 로직은 다음과 같습니다.
이진수 중에서, 다음규칙을 지키는 숫자를 이친수라고 합니다.
끊어진 기타줄의 개수 N과 기타줄 브랜드의 수 M개가 주어집니다. 각 브랜드에서는 기타줄을 6개 묶음과 낱개로 판매하는데, 각각의 가격이 주어집니다. 이때 최소한의 가격으로 적어도 N개 만큼 구매하는 프로그램을 작성하는 문제입니다.
요금표와 주차기록이 주어졌을때, 차량번호 작은순부터 내야하는 금액을 출력하는 문제입니다. 카카오 2022 유형은 복잡한 알고리즘은 요구하지 않고 시간내에 구현하기 까다로운 문제들로 구성된듯 합니다. 풀이계획은 금방 세웠지만 작성하는데에는 30분 가량 소모됬습니다.
정수 n이 주어졌을때, k진수로 변환시킨 뒤 각 자리에 소수를 얼마나 포함하고 있는지 확인하는 문제입니다. 이때 소수는 0을 포함하지 않습니다. 그래서 0을 기준으로 숫자를 나누어 확인하면 됩니다. 그에 따라 다음과 같은 것들이 필요하다고 생각했습니다.
구현이 까다로운 문제였습니다. 문제조건을 읽어보면 id별 신고당한 횟수를 알아야하는데 한사람이 같은사람을 여러번 신고하는건 신고로 치지 않는다고 합니다. 즉 set 자료형을 이용하면 되겠다는 느낌이 듭니다. 그러나 정답으로 출력해야 하는 건, 각 신고자의 신고가 성공(k번 이상 신...
1*1 정사각형으로 이루어진 직사각형의 길이와 높이, w, h가 주어집니다. 대각선으로 서로 이었을때 대각선을 포함하는 정사각형들은 제외된다고 했을때, 나머지 정사각형의 개수를 구하는 문제입니다.
투포인터 알고리즘을 응용하여 풀이했습니다. 1 ≤ l ≤ m, m+1 ≤ r ≤ N 의 조건을 살펴보면, l의 끝은 m이고, r의 시작은 m+1 이므로 두 배열은 연속해야만 하는 것을 알 수 있습니다. 따라서 l, m, r 세가지 포인터를 가지고, 첫번째 배열, 두번째 배열의 합계...
N*N 형태의 2차원 배열로 블럭의 높이가 주어집니다. 각 블럭을 제거하거나 쌓아올려 높이를 평평하게 만들어주는데, 제거와 추가의 가중치가 테스트케이스마다 다릅니다. 몇시간 도전하고 고민하다 결국 다른분의 해설을 듣고 DP형태로 풀이했습니다.
동적계획법 문제입니다. 다만 문제조건상 양옆의 인덱스를 참조해야하는데, 원형의 구조이기때문에 예외처리가 까다로운 부분이 있습니다. 그래서 1시간 정도 걸린 것 같습니다.
상대팀인 A를 오름차순으로 정렬하고 아군팀인 B를 최소힙 자료구조에 담습니다. 그 후 A의 각 원소를 탐색하면서, B의 가장 작은 원소와 비교하며 정답을 카운팅합니다. 만약 B의 원소가 더 작다면 pop한 그대로 버리면 됩니다. A는 오름차순으로 정렬되있기때문에, 작아서 버린 B의...
결론부터 말씀드리면 점화식은 dp[n] = dp[n-2]3 + dp[n-4]2 + dp[n-6]*2 + … dp[0] * 2 입니다.
좌표 3개가 주어졌을때, 3개의 좌표에서 출발하여 서로 만나는 최단거리를 구하는 문제입니다. BFS로 해결할 수 있습니다.
NXN 형태의 지도가 주어지고, 각 좌표는 0, 1(집), 2(치킨집)으로 이루어져있습니다. M개의 치킨집만을 남긴다했을때 총치킨거리(가장 가까운 치킨집에서 집까지의 거리)가 가장 짧은 경우를 구하면 됩니다.
출력을 바꿔서 말하면, 같은 루트를 가지고 있는 부품의 개수를 출력하면 된다. 부품의 최대 개수가 백만으로, 부품에서 count를 하면 시간초과판정을 받기에, 따로 해당 루트가 가지고 있는 부품의 개수를 카운팅하는 배열을 만들어준다.
반복문을 끝까지 돌게된다면, 조건을 만족하는 스킬트리란 이야기이므로 정답에 카운팅 해준다. for-else문을 이용해 flag를 사용하지 않았다. break로 탈출하게 되면 else문은 실행하지 않아 정답에 카운팅되지 않는다.
각 거리를 (2w)+1로 나누어주면 기지국을 얼마나 설치해야하는지 알 수 있다. (2w)+1 이 나오는 이유는, 범위가 양옆이므로 2*w, 그리고 기지국 설치된 위치까지 포함하기때문에 +1 이다. 이때 소수점이 나오면, 거리는 정수단위이므로 올림해줘야한다.
블록은 대칭, 회전이 가능하므로 총 19가지 모양이 가능하다. 각 모양에 따른 이동규칙을 배열로 만들어주고, 2차원배열에 전부 대입해본다. 최악의경우 19 * 500 * 500 으로 파이썬으로도 충분히 커버할만한 정도의 시간복잡도를 가지므로 가능하다 판단했다. 다만 모양에 따른 좌...
근데 문제조건을 다시 생각해보니 그냥 노드의 부모만 구하면 되는 문제라 BFS로 해결되는 걸 알았다.
탐색할 숫자를 문자열로 변환시켜 각 자릿수가 고장난 버튼에 속할경우, 무시하고 넘긴다. 모든 자릿수가 문제 없을 경우, 위에서 구한 공식 누른 자릿수 + abs(목표버튼 - 조합버튼)를 하고, 기존 이동량이랑 비교해서 최소값을 갱신한다.
n행은 ‘각 동전을 가지고 있을 때’, 를 의미한다. 즉 위의 예시라면 1원 동전일때 구할 수 있는 경우의 수, 그 후 1원 2원 동전일때의 경우의 수, 마지막으로 1원, 2원, 5원일때의 경우의 수를 구해주면 된다.
그 외 최적화를 위해, 그래프 문자를 아스키코드로 변환하여 정수로 받았다. 그리고 각 알파벳을 가지고 있는지 체크하는 배열을 만들어, 탐색에 들어갈땐 체크하고 탐색이 끝나면 알파벳을 제거해주었다.
파이썬의 덱 라이브러리를 이용해서 풀면 되겠다는 생각이 들었다. 처음 접근은 R을 받으면 reverse()로 뒤집고, D라면 popleft()로 제거하자고 생각했었지만, reverse()는 O(N)의 복잡도로 여러번 사용하게 되면 시간초과 판정을 받게 된다. 그래서 다른 방법을 생...
역시 문자열을 다루는 문제에서 Python이 빛을 발하는 것 같다.
더할 숫자는 3개로 고정되어있다. 배열내 원소의 개수는 50개 이하이다. 즉 3중 for문 혹은 조합 라이브러리를 사용해서 완전탐색을 통해 모든 경우의 수를 구해도 되겠다.
1번 노드에서 모든 노드까지의 최단거리. 즉, 다익스트라 알고리즘을 통해 구할 수 있다.
해당 블로그의 풀이를 보고 허탈하기까지 했다. 오히려 너무 어렵게 생각해서 공책에 끄적이고 틈을 찾는 걸 포기한 것 같다. 스페셜 저지 문제는 정답은 여러개가 될 수 있다. 따라서 다음부터는 간단한 방법으로 나올 수 있는 걸 고민해보는게 좋겠다.
작은 수들에서 직접 계산해보고 규칙을 찾아보았다. 찾아낸 규칙은 m - GCD(n, m) 이다.
나는 큐브의길이가 조건에 맞다면, 한번에 여러개를 집어넣으려고 해서 고생하고 실패했다. 재귀를 줄이려는 선택이였지만, 여러개를 집어넣는다면 남은 공간의 모양이 천차만별이기 때문에 3개의 재귀함수만으로 표현할 수 없었다.
새로 등분되는 배열들의 좌표를 구해 4개로 재귀한다. 그러다 가장 작은 지수 0에 도달하면, 각 숫자 하나를 가리키는 의미이다. 이때 목표 좌표가 맞다면 출력하고, 아니라면 카운팅하는 로직이다. 그러나 불필요한 재귀호출이 너무 많아 시간초과 판정을 받는다. 이를 줄이기 위해, 탐색...
이는 에라토스테네스의체를 응용하여 풀 수 있는 문제이다. 기본 에라토스테네스의 체는, 소수의 배수인 숫자들을 배열에서 지워나갔는데, 이를 변형해서 제곱수의 배수인 숫자들을 배열에서 지워내면 된다.
4보다 큰 모든 짝수는, 두 홀수 소수로 만들 수 있다는 골드바흐의 추측. 문제풀이에 앞서, 문제를 더 작은 두 단계로 나누었다.
에라토스테네스의 채를 이용해 N까지의 소수를 찾는 과정 중, 소수가 아닌 숫자들을 지울 때 k번째 지우는 숫자가 무엇인지 출력하는 문제.
자연수 N은 4백만 까지 주어진다. 이때 연속된 소수의 합으로 N을 만들 수 있는 가짓수를 구하면 된다. 이 문제도 작게 2개로 나누면 다음과 같다.
여러 정수로 이루어진 배열과, 인덱스 범위가 주어졌을때 해당 인덱스 범위의 합을 구하는 문제. 누적합 알고리즘을 이용해 풀 수 있는데, 해당 과정을 풀면 다음과 같다.
dp를 이용해 풀이할 수 있는 문제. dp라고 유형을 파악해도, 점화식은 매번 새로운 것 같아 시간이 오래 걸리는 것 같다.
위상정렬과 DP를 이용해서 풀 수 있는 문제. 1번 노드 부터 시작해서 소요시간을 DP에 기록하고, 이후 연결된 그래프들의 indegree를 제거하면서 탐색한다.
각 도시간 연결 정보가 주어졌을때, 계획한 도시들을 이동할 수 있는지 없는지 판단하는 문제다. 간선의 가중치가 있어 최적의경로를 구하는 문제도 아니고, 단지 연결되어있는지 확인하는 문제이기 때문에 목표 도시들이 같은 부모노드를 가지고 있는지 확인만 하면된다.
유니온 파인드 자료구조를 사용해 풀 수 있는 문제.
특정 노드에서 모든 노드까지의 최단거리를 구하는 문제. 이는 우선순위큐를 활용한 다익스트라 알고리즘으로 해결할 수 있다.
1번노드에서 시작하여 N번노드까지의 최단경로를 구하는 문제. 특이사항으로는, 간선이 양방향이며, v1, v2 노드를 반드시 거치고 목표 노드에 도달해야한 다는 점이다.
최댓값을 구하는 문제이기에, 동적계획법을 사용해야겠다고 생각이 들었다. 그래서 캐싱을 위한 n * k 형태의 2차원 배열을 만들어준다. n축은 각 물건을 나타내고, k축은 각 무게를 나타낸다.
간단한 매개변수 탐색문제.
집간의 중간거리를 이분탐색한다
기존에 한번 풀어봤던 최장길이 부분 수열 문제. 다만 이번엔 크기가 1,000,000으로 기존 dp풀이대로 하면 O(n**2)의 시간복잡도를 가지므로 통과할 수 없다.
이분탐색을 이용하여 풀이했다. 나눌수 있는 랜선길이의 범위는 (1 ~가진 랜선중 최대길이) 이고 주어지는 최대길이가 1,000,000로 범위가 크니 큰 범위를 빠르게 탐색할수 있는 이분탐색이 적합하다고 판단했다.
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다.
2차원 BFS문제와 다른건 z축이 생겼다는 점이다. 새로 알아야 할건 없지만 헷갈리기 쉽다.
핵심은 벽을 부쉈을 경우와 부수지 않았을 경우, 둘 모두의 최단거리를 구해야 한다. 이를 위해서 dp 배열에는 값을 2개를 담고, 큐에서는 현재 벽을 부쉈는지 여부를 판단하는 변수(is_break)를 넣어준다.
핵심 로직은 방문하지 않은 정점이 있다면 해당 정점과 연결된 정점들을 모두 방문처리하고 정답을 카운팅하는 것이다.
왜냐하면 각 정점들이 같은 부모를 가지고 있으면 하나의 집합임을 알 수 있습니다. 만약 두 정점이 이미 같은 집합일때 (같은 부모를 가지고 있을때), 두 정점을 이으면 사이클이 발생합니다.
1 부터 시작해서 각 숫자의 최적의해(최단거리 배열 히스토리)를 저장해두고 재사용하는게 핵심입니다. 가장 간단한 경우인 1일 경우부터 생각해보겠습니다.
정수를 담은 자료구조를 다루는 문제입니다. 명령은 I 와 D 두가지로 주어집니다. 이 때 D 명령을 통해 가장 큰 값을 빼거나 가장 작은 값을 뺄 수 도 있습니다. 따라서 항상 적은 시간복잡도로 최대값, 최소값을 제거할 준비가 되있어야 합니다.
DP로 풀이할 수 있는 문제입니다.
이분 그래프란, 정점들이 두 그룹으로 나뉘어지고, 같은 그룹의 정점끼리는 이어지지 않은 구조를 이야기 합니다. 이는 BFS 혹은 DFS 탐색을 통해 파악할 수 있습니다.
임의의 스택 2개 left와 right를 만들었습니다. 두 배열 사이에 포인터가 존재한다고 생각하면 이해하기 쉽습니다.
큐 자료구조 혹은 수학적 접근을 통해 해결할 수 있는 문제입니다. 저는 큐 자료구조로 풀이했는데 핵심적인 로직은 다음과 같습니다.
이진수 중에서, 다음규칙을 지키는 숫자를 이친수라고 합니다.
끊어진 기타줄의 개수 N과 기타줄 브랜드의 수 M개가 주어집니다. 각 브랜드에서는 기타줄을 6개 묶음과 낱개로 판매하는데, 각각의 가격이 주어집니다. 이때 최소한의 가격으로 적어도 N개 만큼 구매하는 프로그램을 작성하는 문제입니다.
전형적인 BFS 탐색 문제입니다. 2차원 좌표에서, 바이러스의 숙주가 될 좌표가 주어지고 (종류 1, 2) 상하좌우로 쭉 퍼져나갑니다. 이미 감염됬거나 치료제가 있을 경우에는 퍼지지 않지만, 다른 종류의 바이러스가 감염중일때 만난다면 종류 3으로 변하는게 조건입니다. 이는 진행거리...
결론부터 말씀드리면 점화식은 dp[n] = dp[n-2]3 + dp[n-4]2 + dp[n-6]*2 + … dp[0] * 2 입니다.
좌표 3개가 주어졌을때, 3개의 좌표에서 출발하여 서로 만나는 최단거리를 구하는 문제입니다. BFS로 해결할 수 있습니다.
NXN 형태의 지도가 주어지고, 각 좌표는 0, 1(집), 2(치킨집)으로 이루어져있습니다. M개의 치킨집만을 남긴다했을때 총치킨거리(가장 가까운 치킨집에서 집까지의 거리)가 가장 짧은 경우를 구하면 됩니다.
출력을 바꿔서 말하면, 같은 루트를 가지고 있는 부품의 개수를 출력하면 된다. 부품의 최대 개수가 백만으로, 부품에서 count를 하면 시간초과판정을 받기에, 따로 해당 루트가 가지고 있는 부품의 개수를 카운팅하는 배열을 만들어준다.
블록은 대칭, 회전이 가능하므로 총 19가지 모양이 가능하다. 각 모양에 따른 이동규칙을 배열로 만들어주고, 2차원배열에 전부 대입해본다. 최악의경우 19 * 500 * 500 으로 파이썬으로도 충분히 커버할만한 정도의 시간복잡도를 가지므로 가능하다 판단했다. 다만 모양에 따른 좌...
근데 문제조건을 다시 생각해보니 그냥 노드의 부모만 구하면 되는 문제라 BFS로 해결되는 걸 알았다.
탐색할 숫자를 문자열로 변환시켜 각 자릿수가 고장난 버튼에 속할경우, 무시하고 넘긴다. 모든 자릿수가 문제 없을 경우, 위에서 구한 공식 누른 자릿수 + abs(목표버튼 - 조합버튼)를 하고, 기존 이동량이랑 비교해서 최소값을 갱신한다.
n행은 ‘각 동전을 가지고 있을 때’, 를 의미한다. 즉 위의 예시라면 1원 동전일때 구할 수 있는 경우의 수, 그 후 1원 2원 동전일때의 경우의 수, 마지막으로 1원, 2원, 5원일때의 경우의 수를 구해주면 된다.
그 외 최적화를 위해, 그래프 문자를 아스키코드로 변환하여 정수로 받았다. 그리고 각 알파벳을 가지고 있는지 체크하는 배열을 만들어, 탐색에 들어갈땐 체크하고 탐색이 끝나면 알파벳을 제거해주었다.
파이썬의 덱 라이브러리를 이용해서 풀면 되겠다는 생각이 들었다. 처음 접근은 R을 받으면 reverse()로 뒤집고, D라면 popleft()로 제거하자고 생각했었지만, reverse()는 O(N)의 복잡도로 여러번 사용하게 되면 시간초과 판정을 받게 된다. 그래서 다른 방법을 생...
해당 블로그의 풀이를 보고 허탈하기까지 했다. 오히려 너무 어렵게 생각해서 공책에 끄적이고 틈을 찾는 걸 포기한 것 같다. 스페셜 저지 문제는 정답은 여러개가 될 수 있다. 따라서 다음부터는 간단한 방법으로 나올 수 있는 걸 고민해보는게 좋겠다.
작은 수들에서 직접 계산해보고 규칙을 찾아보았다. 찾아낸 규칙은 m - GCD(n, m) 이다.
나는 큐브의길이가 조건에 맞다면, 한번에 여러개를 집어넣으려고 해서 고생하고 실패했다. 재귀를 줄이려는 선택이였지만, 여러개를 집어넣는다면 남은 공간의 모양이 천차만별이기 때문에 3개의 재귀함수만으로 표현할 수 없었다.
새로 등분되는 배열들의 좌표를 구해 4개로 재귀한다. 그러다 가장 작은 지수 0에 도달하면, 각 숫자 하나를 가리키는 의미이다. 이때 목표 좌표가 맞다면 출력하고, 아니라면 카운팅하는 로직이다. 그러나 불필요한 재귀호출이 너무 많아 시간초과 판정을 받는다. 이를 줄이기 위해, 탐색...
이는 에라토스테네스의체를 응용하여 풀 수 있는 문제이다. 기본 에라토스테네스의 체는, 소수의 배수인 숫자들을 배열에서 지워나갔는데, 이를 변형해서 제곱수의 배수인 숫자들을 배열에서 지워내면 된다.
4보다 큰 모든 짝수는, 두 홀수 소수로 만들 수 있다는 골드바흐의 추측. 문제풀이에 앞서, 문제를 더 작은 두 단계로 나누었다.
에라토스테네스의 채를 이용해 N까지의 소수를 찾는 과정 중, 소수가 아닌 숫자들을 지울 때 k번째 지우는 숫자가 무엇인지 출력하는 문제.
자연수 N은 4백만 까지 주어진다. 이때 연속된 소수의 합으로 N을 만들 수 있는 가짓수를 구하면 된다. 이 문제도 작게 2개로 나누면 다음과 같다.
여러 정수로 이루어진 배열과, 인덱스 범위가 주어졌을때 해당 인덱스 범위의 합을 구하는 문제. 누적합 알고리즘을 이용해 풀 수 있는데, 해당 과정을 풀면 다음과 같다.
dp를 이용해 풀이할 수 있는 문제. dp라고 유형을 파악해도, 점화식은 매번 새로운 것 같아 시간이 오래 걸리는 것 같다.
위상정렬과 DP를 이용해서 풀 수 있는 문제. 1번 노드 부터 시작해서 소요시간을 DP에 기록하고, 이후 연결된 그래프들의 indegree를 제거하면서 탐색한다.
각 도시간 연결 정보가 주어졌을때, 계획한 도시들을 이동할 수 있는지 없는지 판단하는 문제다. 간선의 가중치가 있어 최적의경로를 구하는 문제도 아니고, 단지 연결되어있는지 확인하는 문제이기 때문에 목표 도시들이 같은 부모노드를 가지고 있는지 확인만 하면된다.
유니온 파인드 자료구조를 사용해 풀 수 있는 문제.
특정 노드에서 모든 노드까지의 최단거리를 구하는 문제. 이는 우선순위큐를 활용한 다익스트라 알고리즘으로 해결할 수 있다.
1번노드에서 시작하여 N번노드까지의 최단경로를 구하는 문제. 특이사항으로는, 간선이 양방향이며, v1, v2 노드를 반드시 거치고 목표 노드에 도달해야한 다는 점이다.
최댓값을 구하는 문제이기에, 동적계획법을 사용해야겠다고 생각이 들었다. 그래서 캐싱을 위한 n * k 형태의 2차원 배열을 만들어준다. n축은 각 물건을 나타내고, k축은 각 무게를 나타낸다.
간단한 매개변수 탐색문제.
집간의 중간거리를 이분탐색한다
기존에 한번 풀어봤던 최장길이 부분 수열 문제. 다만 이번엔 크기가 1,000,000으로 기존 dp풀이대로 하면 O(n**2)의 시간복잡도를 가지므로 통과할 수 없다.
이분탐색을 이용하여 풀이했다. 나눌수 있는 랜선길이의 범위는 (1 ~가진 랜선중 최대길이) 이고 주어지는 최대길이가 1,000,000로 범위가 크니 큰 범위를 빠르게 탐색할수 있는 이분탐색이 적합하다고 판단했다.
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다.
2차원 BFS문제와 다른건 z축이 생겼다는 점이다. 새로 알아야 할건 없지만 헷갈리기 쉽다.
핵심은 벽을 부쉈을 경우와 부수지 않았을 경우, 둘 모두의 최단거리를 구해야 한다. 이를 위해서 dp 배열에는 값을 2개를 담고, 큐에서는 현재 벽을 부쉈는지 여부를 판단하는 변수(is_break)를 넣어준다.
핵심 로직은 방문하지 않은 정점이 있다면 해당 정점과 연결된 정점들을 모두 방문처리하고 정답을 카운팅하는 것이다.
GET 요청을 통해 데이터를 받아오고, 화면을 구성하는 문제입니다. App.js 아래 Breadcrumb, Nodes 두가지만으로 표현되다가, 이미지 파일 클릭 혹은 로딩시에 Modal을 뛰워주는 간단한 구조입니다.
요금표와 주차기록이 주어졌을때, 차량번호 작은순부터 내야하는 금액을 출력하는 문제입니다. 카카오 2022 유형은 복잡한 알고리즘은 요구하지 않고 시간내에 구현하기 까다로운 문제들로 구성된듯 합니다. 풀이계획은 금방 세웠지만 작성하는데에는 30분 가량 소모됬습니다.
정수 n이 주어졌을때, k진수로 변환시킨 뒤 각 자리에 소수를 얼마나 포함하고 있는지 확인하는 문제입니다. 이때 소수는 0을 포함하지 않습니다. 그래서 0을 기준으로 숫자를 나누어 확인하면 됩니다. 그에 따라 다음과 같은 것들이 필요하다고 생각했습니다.
구현이 까다로운 문제였습니다. 문제조건을 읽어보면 id별 신고당한 횟수를 알아야하는데 한사람이 같은사람을 여러번 신고하는건 신고로 치지 않는다고 합니다. 즉 set 자료형을 이용하면 되겠다는 느낌이 듭니다. 그러나 정답으로 출력해야 하는 건, 각 신고자의 신고가 성공(k번 이상 신...
1*1 정사각형으로 이루어진 직사각형의 길이와 높이, w, h가 주어집니다. 대각선으로 서로 이었을때 대각선을 포함하는 정사각형들은 제외된다고 했을때, 나머지 정사각형의 개수를 구하는 문제입니다.
투포인터 알고리즘을 응용하여 풀이했습니다. 1 ≤ l ≤ m, m+1 ≤ r ≤ N 의 조건을 살펴보면, l의 끝은 m이고, r의 시작은 m+1 이므로 두 배열은 연속해야만 하는 것을 알 수 있습니다. 따라서 l, m, r 세가지 포인터를 가지고, 첫번째 배열, 두번째 배열의 합계...
N*N 형태의 2차원 배열로 블럭의 높이가 주어집니다. 각 블럭을 제거하거나 쌓아올려 높이를 평평하게 만들어주는데, 제거와 추가의 가중치가 테스트케이스마다 다릅니다. 몇시간 도전하고 고민하다 결국 다른분의 해설을 듣고 DP형태로 풀이했습니다.
프로그래머스에서 제공하는 과제입니다. 검색어를 입력하면, 해당 키워드에 맞는 검색단어를 서버에서 받아오고 목록을 렌더링 하면 됩니다. 단, 시간은 3시간이 주어지고 다른 라이브러리 사용없이 순수 자바스크립트만으로 완성시켜야하므로 탄탄한 기본기가 요구되는 과제입니다.
동적계획법 문제입니다. 다만 문제조건상 양옆의 인덱스를 참조해야하는데, 원형의 구조이기때문에 예외처리가 까다로운 부분이 있습니다. 그래서 1시간 정도 걸린 것 같습니다.
상대팀인 A를 오름차순으로 정렬하고 아군팀인 B를 최소힙 자료구조에 담습니다. 그 후 A의 각 원소를 탐색하면서, B의 가장 작은 원소와 비교하며 정답을 카운팅합니다. 만약 B의 원소가 더 작다면 pop한 그대로 버리면 됩니다. A는 오름차순으로 정렬되있기때문에, 작아서 버린 B의...
반복문을 끝까지 돌게된다면, 조건을 만족하는 스킬트리란 이야기이므로 정답에 카운팅 해준다. for-else문을 이용해 flag를 사용하지 않았다. break로 탈출하게 되면 else문은 실행하지 않아 정답에 카운팅되지 않는다.
각 거리를 (2w)+1로 나누어주면 기지국을 얼마나 설치해야하는지 알 수 있다. (2w)+1 이 나오는 이유는, 범위가 양옆이므로 2*w, 그리고 기지국 설치된 위치까지 포함하기때문에 +1 이다. 이때 소수점이 나오면, 거리는 정수단위이므로 올림해줘야한다.
최소로 주던, 최대로 주던 상관없이 최대한 많은 부서에 나눠 주는게 중요하다. 즉 정렬해서 차례대로 주면 된다.
역시 문자열을 다루는 문제에서 Python이 빛을 발하는 것 같다.
더할 숫자는 3개로 고정되어있다. 배열내 원소의 개수는 50개 이하이다. 즉 3중 for문 혹은 조합 라이브러리를 사용해서 완전탐색을 통해 모든 경우의 수를 구해도 되겠다.
1번 노드에서 모든 노드까지의 최단거리. 즉, 다익스트라 알고리즘을 통해 구할 수 있다.
heroku에 어플리케이션을 배포하고, AWS S3에 이미지와 비디오들을 업로드하도록 설정합니다.
댓글 기능을 구현합니다.
express-flash를 통해 토스트 메시지를 구현합니다.
유저가 브라우저에서 영상 녹화를 할 수 있도록 구현합니다.
비디오에 영상 조회수 기록 이벤트를 추가합니다.
비디오 플레이어를 직접 구현해봅니다.
Webpack 설정을 통해 js와 css를 브라우저가 읽을 수 있도록 변환시켜줍니다.
생성한 계정의 프로필을 관리할 수 있도록, 정보 변경, 이미지 업로드, 비디오 정보 받아오기 등을 구현합니다.
회원가입 및 로그인 그리고 Oauth를 이용한 깃허브 로그인을 구현합니다.
MongoDB를 연결하고, CRUD 기능을 연습합니다.
Pug의 기능을 배우며, 마크업 구성을 위한 준비를 합니다.
라우터 설계에 관한 내용입니다.
초기 개발환경, express 서버 세팅에 관한 내용입니다.
웹 시작페이지로 사용할 수 있는 할일 목록을 만들려고 했습니다. 구현한 기능으로는 다음과 같습니다.
heroku에 어플리케이션을 배포하고, AWS S3에 이미지와 비디오들을 업로드하도록 설정합니다.
댓글 기능을 구현합니다.
express-flash를 통해 토스트 메시지를 구현합니다.
유저가 브라우저에서 영상 녹화를 할 수 있도록 구현합니다.
비디오에 영상 조회수 기록 이벤트를 추가합니다.
비디오 플레이어를 직접 구현해봅니다.
Webpack 설정을 통해 js와 css를 브라우저가 읽을 수 있도록 변환시켜줍니다.
생성한 계정의 프로필을 관리할 수 있도록, 정보 변경, 이미지 업로드, 비디오 정보 받아오기 등을 구현합니다.
회원가입 및 로그인 그리고 Oauth를 이용한 깃허브 로그인을 구현합니다.
MongoDB를 연결하고, CRUD 기능을 연습합니다.
Pug의 기능을 배우며, 마크업 구성을 위한 준비를 합니다.
라우터 설계에 관한 내용입니다.
초기 개발환경, express 서버 세팅에 관한 내용입니다.
음수간선이 포함된 최단거리문제에 효과적이다. 단순히 음수간선이 포함된 경우라면, 다익스트라를 사용해도 괜찮을때도 있다. 그러나 음수 사이클이 발생한다면 벨만포드 알고리즘을 사용해야한다.
1보다 큰 자연수 중, 1과 자기자신으로 밖에 나눌 수 없는 자연수.
공통된 원소를 가지지 않은 두 집합. 합집합(Union), 찾기(Find) 메서드를 통해 알고리즘 풀이에 도움을 줌. 고로 합치기 찾기 (Union Find) 자료구조라고 불리기도 함.
특정 노드에서 다른 모든 노드까지의 최단 경로를 계산하는 알고리즘.
동적계획법이라고 부르기도 한다. 한번 계산된 결과값을 이용하여 다음 계산에 활용하는 기법.
정렬된 배열에 적용할 수 있는 탐색 알고리즘.
주어진 데이터나 문제 유형에 따라 공식처럼 정렬 방식을 선택하여 풀이한다.
탐색이란 원하는 데이터를 찾는 과정. DFS, BFS가 대표적인 그래프 탐색 알고리즘.
일반적인 경우, 최적의 해를 구하긴 어렵고 쉽게 최적의 해와 근사한 값을 구할 수 있으나, 알고리즘 테스트의 경우에는 탐욕법을 통해 최적의 해를 구할 수 있도록 설계되어 있다.
대기업 출제경향은, 구현, BFS/DFS, 그리드가 자주 나온다.
입출력을 리스트 자료구조로 강제 받는 문제입니다. 문제에서 제공하는 메서드를 활용해서, 두 정렬된 리스트를 하나의 정렬된 리스트로 병합하면 됩니다.
같은 타입의 괄호로 닫을 수 있는 것은 물론이고, 순서도 지켜야한다고 명시되있습니다. 가령 ({)} 같은 형태로 주어진다면 false를 리턴해야할겁니다. 그래서 단순히 삽입할 원소와 배열 맨뒤의 원소만 비교하면 되기 때문에 스택 자료를 이용하여 풀이할 수 있는 문제입니다.
언뜻 배열로 착각하고 reverse같은 메서드들을 시도해볼 수 있지만, List의 형태로 주어지기때문에 배열에서 사용하는 메서드들을 사용할 수 없습니다.문제 설명에서, 각 List가 어떻게 구성되는지 알수있는 함수가 주어집니다.
문자열로 이루어진 배열이 주어집니다. 이 때 각 문자의 공통 접두사를 출력하면 되는 문제입니다.
연속된 두개의 문자의종류에 따라 값이 변경될 수 있습니다. 따라서 그 둘이 예외 케이스인지 확인해보고 그에 따라 적절한 값을 더해줍니다.
배열내 두 숫자를 더했을때, target을 만들 수 있는 두 숫자를 출력하는 문제입니다. 첫문제니까 가볍게 완전탐색으로 풀이했습니다.
최소로 주던, 최대로 주던 상관없이 최대한 많은 부서에 나눠 주는게 중요하다. 즉 정렬해서 차례대로 주면 된다.
더할 숫자는 3개로 고정되어있다. 배열내 원소의 개수는 50개 이하이다. 즉 3중 for문 혹은 조합 라이브러리를 사용해서 완전탐색을 통해 모든 경우의 수를 구해도 되겠다.
나는 큐브의길이가 조건에 맞다면, 한번에 여러개를 집어넣으려고 해서 고생하고 실패했다. 재귀를 줄이려는 선택이였지만, 여러개를 집어넣는다면 남은 공간의 모양이 천차만별이기 때문에 3개의 재귀함수만으로 표현할 수 없었다.
에라토스테네스의 채를 이용해 N까지의 소수를 찾는 과정 중, 소수가 아닌 숫자들을 지울 때 k번째 지우는 숫자가 무엇인지 출력하는 문제.
이코테를 공부하던 중, 메인언어는 파이썬이지만 C++도 겸사겸사 할까 생각하여 코드를 살펴봤다. 그런데 처음보는 include문이 있었다.
marked.js, github-markdown-css를 이용해서 마크다운 문법을 지원하는게 목적입니다.
현재 프로젝트에서 스타일링을 할때, 클래스명을 가져와 CSS를 적용하고 있습니다. 그런데 각자 작성한 클래스명이 카멜케이스, 하이픈케이스 등 다양하고 통일이 되있지 않아 유지보수에 어려움을 겪고 있었는데요. 이번기회에 BEM(Block Element Modifier) 방식으로 통일...
순수 자바스크립트로 프로젝트를 진행했었기에, html을 생성할때 innerHTML 메서드를 이용해 string 형태로 넘겨주곤 했습니다.
기존 팀프로젝트로 만들었던 propro를 유지보수하고 있습니다. 이번에는 각 컴포넌트의 생성자인 코어 컴포넌트의 생명주기, 메서드를 변경하였고, 그에 따라 영향받는 컴포넌트들을 리팩토링하게 되었습니다.
엘리스 SW 엔지니어 트랙 1기 과정 중 진행했던 1차 프로젝트 Pro-Pro입니다. 진행했을 당시에는 엘리스 측에서 서버를 제공해주었는데 트랙이 끝난 이후에도 프로젝트를 살려두고 싶은 마음이 있어서 팀원들과 함께 다시 배포하게 됬습니다. 마침 제가 AWS 프리티어 기간이 남아, ...
해당 게시글은 Sukhjinder Arora의 “Hoisting in Modern JavaScript - let, const, and var” 를 읽고 번역 및 요약한 글입니다.
해당 게시글은 Eric Elliott의 “Master the JavaScript Interview: What is a Closure?” 를 번역하고 요약한 글입니다.
공학적인 지식뿐만 아니라, 좋은 교육이란 무엇인가 엿볼 수 있는 뛰어난 강의입니다.
컴퓨터는 모든 과정을 이진법으로 이해한다.
번외. forEach, map, filter, reduce method 작동 원리
이코테를 공부하던 중, 메인언어는 파이썬이지만 C++도 겸사겸사 할까 생각하여 코드를 살펴봤다. 그런데 처음보는 include문이 있었다.
이코테를 공부하던 중, 메인언어는 파이썬이지만 C++도 겸사겸사 할까 생각하여 코드를 살펴봤다. 그런데 처음보는 include문이 있었다.
개방형 시스템 상호 연결 모델의 표준
최근 블로그를 꾸미고 있습니다. Jekyll을 잘 알지못해 시행착오를 겪고 있습니다만, 생각나는 기능을 하나하나씩 추가해보려 합니다. 이번에 시도한 건 다크모드 입니다.
엘리스 SW 엔지니어 트랙 1기 과정 중 진행했던 1차 프로젝트 Pro-Pro입니다. 진행했을 당시에는 엘리스 측에서 서버를 제공해주었는데 트랙이 끝난 이후에도 프로젝트를 살려두고 싶은 마음이 있어서 팀원들과 함께 다시 배포하게 됬습니다. 마침 제가 AWS 프리티어 기간이 남아, ...
현재 프로젝트에서 스타일링을 할때, 클래스명을 가져와 CSS를 적용하고 있습니다. 그런데 각자 작성한 클래스명이 카멜케이스, 하이픈케이스 등 다양하고 통일이 되있지 않아 유지보수에 어려움을 겪고 있었는데요. 이번기회에 BEM(Block Element Modifier) 방식으로 통일...
지난 일요일에 시험을 치뤘던 우아한테크캠프 1차 코딩테스트에 합격했다고 안내 받았습니다. 2차 과제 테스트, 서류, 면접 등 많은 과정이 남았지만 그동안 중점적으로 공부하던 코딩테스트를 합격해서 기쁜 마음입니다.
이분검색을 통해 O(logN)의 복잡도로 탐색하는 방법을 배웁니다.
marked.js, github-markdown-css를 이용해서 마크다운 문법을 지원하는게 목적입니다.
컴퓨터는 모든 과정을 이진법으로 이해한다.
컴퓨터는 모든 과정을 이진법으로 이해한다.
타입스크립트만을 사용하여 어플리케이션을 만들었습니다. 타입스크립트의 사용법과 웹팩세팅에 익숙해지려는 목적입니다.
타입스크립트만을 사용하여 어플리케이션을 만들었습니다. 타입스크립트의 사용법과 웹팩세팅에 익숙해지려는 목적입니다.