[JS][백준]16938_캠프 준비

문제 번호 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 알고리즘 분류 수학 브루트포스 알고리즘 조합론 비트마스킹 백트래킹 문제 풀이 주어진 N개의 문제들 중 2개 이상 N개 이하의 문제를 뽑는 경우를 생각해본다. for (let i = 2; i { if (a b) return 1; return 0; }) if (L { if (a b) return 1; return 0; }) if (L

→2022.07.05

Algorithm/BaeKJoon

[JS][백준]16926_배열 돌리기1

문제 번호 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 알고리즘 분류 구현 문제 풀이 구현 문제이다. 언젠가 풀어본 거 같지만 안 풀려있었다. 주어진 배열을 회전해야 하는데 위쪽 부분, 왼쪽 부분, 아래쪽 부분, 오른쪽 부분 이렇게 4 부분으로 나누어서 보기로 했다. 제일 밖에 있는 4개의 영역이 회전하고 크기를 줄여가면서 똑같이 회전하면 된다. 우선 윗부분을 살펴본다. 오른쪽에 있는 숫자를 왼쪽에서 받아야 한다...

→2022.06.21

Algorithm/BaeKJoon

[JS][백준]16719_ZOAC

문제 번호 16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 알고리즘 분류 구현 문자열 재귀 문제 풀이 구현 문제다. 주어진 문자열에서 아직 등장하지 않은 알파벳들을 behind라는 배열에 넣어두었다. 그리고 1개씩 꺼내서 새로운 문자열을 만들어서 dic라는 배열에 넣고 어느 알파벳을 추가했을 때의 단어가 사전 순으로 가장 앞에 오는지 비교했다. => 브루트포스 알고리즘을 사용했다. 우선 원본 문자열(이하 S)를 살펴보아서 어느 알파벳이 어느 자리에 있는지 파악했다. 예를 들어 START라는 문자열이 있..

→2022.06.15

Algorithm/BaeKJoon

[JS][백준]16206_롤케이크

문제 번호 16206번: 롤케이크 오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 www.acmicpc.net 알고리즘 분류 그리디 알고리즘 문제 풀이 그리디 알고리즘을 사용한다. 정렬기준을 생각하는데 매우 오래걸렸다. 주어진 롤케이크들을 오름차순으로 정렬하되, 10의 배수이면 더 앞쪽에 위치하도록 한다. 예를들어 15 20 25 30 35 가 있다고 하자. 그렇다면 20 30 15 25 35 순서로 배치가 되어야한다. 10의 배수들을 따로 빼서 앞쪽에 오름차순으로 배치하고 나머지 숫자들을 오름차순으로 이어서 배치하면된다. cakes.sort((a,..

→2022.06.15

Algorithm/알고리즘 예제코드

Knapsack(배낭알고리즘)

let ting = [{ v:0, w:0, }]; for(let i=1; i

→2022.06.14

Algorithm/BaeKJoon

[JS][백준]1167_트리의 지름

문제 번호 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 트리 깊이 우선 탐색 문제 풀이 DFS를 활용한다. 그전에 트리의 지름에 대해서 찾아보면 많은 자료들이 나온다. 처음에는 그래프 탐색까지만 감을 잡고 생각을 해보았는데 나중에 트리의 지름에 대해서 검색해보니 알고리즘은 쉽게 이해할 수 있었다. 트리의 지름 구하기 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하..

→2022.06.09

Algorithm/BaeKJoon

[JS][백준]14627_파닭파닭

문제 번호 14627번: 파닭파닭 첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1 ≤ S ≤ 1,000,000), 그리고 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S ≤ C) 그 후, S 줄에 www.acmicpc.net 알고리즘 분류 이분 탐색 문제 풀이 문제의 알고리즘은 어렵지 않은 이분 탐색이다. 처음엔 주어진 파들을 무조건 사용해야 하는줄 알고 이분탐색의 최대 범위를 가장 짧은 파의 길이로 두고 했다가 틀렸었다. 그런데 수의 범위가 크기 때문에 BigInt를 사용해야 한다. 이때 BigInt의 연산 시간은 상수 시간이 아니므로 무분별하게 BigInt를 사용한다면 같은 알고리즘 이더라도 시간 초과에 걸리게 된다. 때문에..

→2022.06.09

Algorithm/알고리즘 예제코드

투 포인터

주어진 배열의 크기가 N이고, 찾고자 하는 구간합이 M 일떄. function sol() { let answer = 0; let start = 0; let end = 0; let sum = 0; while(start

→2022.06.09

티스토리툴바