Ama_gramer

📖문제IPv6❓구상이 문제는 축약된 IPv6 주소를 원본으로 되돌리는 함수를 구현하는 문제이다.IPv6 주소는 32 자리의 16진수를 4자리씩 끊어 내기 때문에 입력값을 축약 전으로 돌리면 :(세미콜론) 은 7개가 존재해야하고,16진수 4자리 숫자는 총 8개가 존재해야한다.먼저 축약 조건을 확인해보면 아래와 같다.1. 각 그룹의 앞자리의 0의 전체 또는 일부를 생략 할 수 있다. 2. 만약 0으로만 이루어져 있는 그룹이 있을 경우 그 중 한 개 이상 연속된 그룹을 하나 골라 콜론 2개(::)로 바꿀 수 있다.3. 2번째 규칙은 모호함을 방지하기 위해서 오직 한 번만 사용할 수 있다. 예제 입력 2의 경우 주어진 입력이 "::1" 으로 축약되지 않은 형태로 출력하면 다음과 같은 결과가 나온다.→ 0000..

📖문제1, 2, 3 더하기 7❓구상이 문제는 "1, 2, 3 더하기" 문제 시리즈중 7번째 문제다. 앞서 풀어본 "1, 2, 3 더하기" 문제는 모두 Dynamic Programming 알고리즘 유형이였기 때문에 비슷하게 접근을 해보려했다. 하지만, 여태 풀어본 DP 문제는 피보나치수열처럼 단순히 N번째의 DP 값을 구하면 되는 문제였는데 이 문제 같은 경우는 T개의 테스트 케이스개수가 주어지고, 그 아래로 T개의 n, m 의 쌍이 있다. 즉, 여태 풀어본 DP 문제는 n 과 m 이 주어지는게 아닌 n 이 주어져서 n번째 DP 값을 구하면 되는 문제였는데, 이번에는 1, 2 ,3 을 이용해 만들 수 있는 n의 갯수 + 1, 2, 3 숫자 m 개를 사용해서 n이 되도록 하는 문제인것이다. 어떻게 접근하면..

버블정렬(Bubble sort)버블정렬은 정렬 알고리즘 종류 중 한 기법으로 길이가 N 인 배열을 정리할때 index 가 0 인 값과 1인 값을 비교한 후 조건에 맞는 값을 왼쪽으로 정렬후 기존 0, 1 인덱스에 각각 1을 더한 값을 반복적으로 비교하여 결과적으로 값의 변화가 아무것도 없을 때 까지 정렬을 반복하는 비교 기반 알고리즘이다.버블정렬, Bubble sort 패러다임 및 동작버블정렬 패러다임반복(iterative) : 버블정렬은 반복적인 방식으로 배열의 인접한 요소들을 비교하여 정렬한다.비교 기반(comparison based) : 요소 간의 대소 비교를 통해 정렬 순서를 정한다.제자리 (in place) : 추가 메모리 공간을 거의 사용하지 않으며, 기존 배열 내에서만 정렬 작업이 이루어..

📖문제걷다보니 신천역 삼❓구상N자리수의 숫자에서 0, 1, 2 만 가지고 만들 수 있는 3의 배수의 갯수를 출력해야 하는데 일정 패턴이 있는지 파악을 하면 동적 프로그래밍을 활용하면 문제를 풀 수 있을 것으로 생각된다. 우선, 입력값 N 에 따른 출력 갯수를 파악하기 위해 백트래킹으로 출력값을 파악해보기로 했다. 패턴파악을 위한 백트래킹을 사용한 코드.const result = [];const N = 10;const backTracking = (arr, line) => { if (line.length !== N) { const len = arr.length; for (let i = 0; i !(e % 3)).length % 1000000009);  출력위의 코드로 N이 2, 4, 5, ..

📖문제01타일  ❓구상패턴의 개수를 파악하는 문제는 작은 규모의 패턴을 파악해서 해결하기 좋은 동적 프로그래밍(Dynamic Programming)계획법으로 풀기 적합한 문제이다.일반적인 이진법이라면 N이 1일때 0과 1을 만들 수 있기 때문에 2가 나와야하지만, 이 문제의 조건을 살펴보면 아래와 같다.1. 이진법을 구성할 때 1과 00의 조합으로만 구성을 해야한다.2. 0은 01 혹은 10 처럼 사용할 수 없고 0이 2개가 붙어있어야한다.주어진 N에 따라 표현될 수 있는 이진법의 종류를 알아보면 패턴을 파악할 수 있을것으로 기대된다. 🎲 패턴N이 1일때 부터 7일때 까지의 패턴을 파악한 결과 피보나치 수열처럼 dp[i] = dp[i-1] + dp[i-2] 의 패턴을 가지고 있음을 알 수 있다.이 것..

📖문제1003 피보나치 함수  ❓구상피보나치 함수는 대표적인 동적 프로그래밍(Dynamic Programming) 계획법으로 풀 수 있는 문제이다.우선 문제를 보니 N번째 피보나치 수를 구하는 C++ 함수의 예제가 나와있다.일단 간단하게 생각하고 fibonacci(n) 에서 n이 0과 1인 경우를 카운팅하면 문제에서 요구하는 출력을 볼 수 있을 것으로 기대 된다.한번 코드를 살펴보자. 시도한 코드.const [T, ...arr] = require("fs").readFileSync("/dev/stdin", "utf-8").trim().split("\n").map(Number);const result = new Array(T);let line = [0, 0];const fibo = (n) => { if ..

백트래킹(Backtracking)백트래킹은 문제를 단계적으로 해결하는 알고리즘 기법으로, 가능한 해답을 하나씩 만들어가면서 조건에 맞지 않으면 되돌아가 다른 경로를 시도하는 방식이다. 백트래킹은 가능한 모든 해답을 탐색하면서, 어떤 선택이 조건을 만족하지 않거나 막다른 길에 다다르면 "되돌아가(backtrack)" 다시 다른 선택지를 시도하는 방식을 취한다.백트래킹, Backtracking 패러다임 조건 및 구조백트래킹의 조건 백트래킹을 효과적으로 사용하려면 다음의 조건을 만족해야 한다.부분 해의 유효성 검사(Constraint Checking)백트래킹은 매 단계에서 현재까지 만든 부분 해(partial solution)가 유효한지를 확인한다.이 과정에서 문제가 되는 경로는 빨리 포기(Pruning)하여..

동적계획법, DP(Dynamic Programming)동적계획법은 한번 처리한 데이터에 다시 접근할 때마다 다시 계산하는 것이 아닌, 저장해둠으로 다음 처리에서 다시 활용 할 수 있게 해주는 알고리즘 패러다임이다.최적화 이론의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.- MDN 동적계획법이라고 하면 어떤 패러다임인지 바로 알아차리기 어려운데, 이는 쉽게 생각하자면 "기억하며 풀기" 라고 하면 조금 더 이해하기 쉬울 것 같다.동적계획법, DP(Dynamic Programming) 패러다임 조건 및 구조동적 계획법 조건동적계획법을 적용하기 위해 필요한 조건에는 크게 4가지가 있다.중복되는 하위 문제하위의 문제가 재..

완전 검색, 무차별 대입 검색(Brute Force Search)완전 검색은 전체 데이터의 모든 요소를 주어진 조건과 비교하여 원하는 값을 찾아내는알고리즘 패러다임이다.   컴퓨터 과학(CS)에서 생성 및 테스트라고도 불린다. 완전 검색 알고리즘은 코드의 처리 속도보다는 단순 구현이 더 중요한 경우에 사용된다. 즉, 구현하기 간단하며 솔루션이 존재하는 경우에는 항상 솔루션을 찾을 수 있지만, 솔루션의 수가 많을 수록 처리 속도는 길어진다. 완전 검색, 무차별 대입 검색 알고리즘 조건이 알고리즘은 3가지의 경우에 적절한 알고리즘이다. 1. 문제의 크기가 제한되어 있는 경우.너무 큰 데이터를 다루는 문제는 조건3의 경우가 아닌 이상 비효율적인 프로그램이 될 수 있다. 완전 검색 알고리즘은 데이터의 모든 el..

유클리드 호제법2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.여기서 호제법이란? 호제법은 2개의 숫자가 상대방의 수로 나누어서 원하는 수를 얻는 알고리즘을 뜻한다. a가 b보다 클때 a를 b나눈 것의 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.  (a > b)r = a % b(a, b) = (b, r) 만약 여기서 b를 r로 나눈 값의 나머지가 0 이면 a와 b의 최대공약수는 r인 것이고, 0이 아닌 경우b를 r 로 나눈것의 나머지(r') 를 b 자리에 두고 a자리에는 b를 두고 다시 계산한다.(b, r) = (r, r') ...이 과정을 N 회 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다. [백준 2609번] 최대공약수와..