Dev:P

문제 이번에 다뤄볼 문제는 17103번 문제 '골드바흐 파티션'입니다. 골드바흐의 추측(Goldbach's conjecture)이란 문제에서 설명하듯, 2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것입니다. 이 문제를 풀기위해 우리는 "에라토스테네스의 체"를 사용할건데요. 이전에 올려뒀던 소수찾기 문제를 참고하셔도 좋습니다. 에라토스테네스의 체에 대해 아직 낯설거나 정확한 이해를 못하셨다면 위키백과에 잘 설명되어있으니 한번 정리하고 오시길 바랍니다. 이 문제에서 주의해야 할 점은 소수를 나타내는 Set을 미리 메모리에 올려놓고 재사용을 해야 타임아웃에 걸리지 않습니다. 입력이 6이 주어진다면 {2,4} {3,3}의 소수 조합이 있고 입력이 10이 주어진다면 {..

문제 이번에 다뤄볼 문제는 16968번 문제 '차량 번호판'입니다. 문제에서 연습해야 하는key-point는 경우의 수 입니다. 주어진 조건들을 보면 조금 복잡해 보일 수 있습니다. 하지만 결국 우리가 수학시간에 종종 풀던 모든 경우의 수의 개수를 구하는 문제라고 생각하면 아주 쉽게 문제를 해결할 수 있습니다. 우선 입력으로는 c,d 로 구성된 문자열이 주어집니다. 이때 c는 문자가 위치하는 자리임을 뜻하고 d는 숫자가 위치하는 자리임을 뜻합니다. 즉, c = 알파벳 26가지 / d = 숫자 9가지의 경우의 수를 갖게 됩니다. 예를들어 cd가 입력되었다면 문제의 해답인 모든 경우의 수는 26*9가 되겠죠. 이제 다 풀었습니다. 마지막으로 "같은 문자 또는 숫자가 연속해서 2번 나타나면 안된다" 라는 조건..

문제 이번에 다뤄볼 문제는 10845번 문제 '큐'입니다. 지난 게시물에 이어 이번엔 기본적인 자료구조인 큐에 대해 알아보는 시간을 가져보겠습니다. 이미 앞선 문제들에서 큐를 활용하여 문제를 해결한 경우들도 많이 있지만 잘 모르시는 분들을 위해 정확히 짚고 넘어가겠습니다. 큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말합니다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 일상생활에서 흔히 사용하는 선착순 구조라고 생각하면 됩니다. 문제에서는 큐를 활용하여 6가지 기능(메서드)를 입력받고 그에 맞는 행동을 하길 바라고 있습니다. 구현해야하는 메서드..

문제 이번에 다뤄볼 문제는 10828번 문제 '스택'입니다. 오늘은 가장 기본적인 자료구조인 스택에 대해 알아보는 시간을 가져보겠습니다. 이미 앞선 문제들에서 스택을 활용하여 문제를 해결한 경우들도 많이 있지만 잘 모르시는 분들을 위해 정확히 짚고 넘어가겠습니다. 스택은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)로 되어 있습니다. 자료를 넣는 것을 '밀어 넣는다' 하여 푸시(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸시한 자료부터 나오게 됩니다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 합니다. 쉬운 예로 헬스장에서 원하는 무게의 원판을 꺼내기 위해서는 그 ..

문제 이번에 다뤄볼 문제는 2529번 문제 '부등호'입니다. 문제에서 연습해야 하는 key-point는 백트래킹입니다. 백트래킹(backtracking)이란, 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 모든 경우의 수를 전부 고려하는 알고리즘으로써 상태 공간을 트리로 나타낼 수 있을 때 적합한 방식입니다. 일종의 트리 탐색 알고리즘이라고 봐도 무방한데요. 방식에 따라서 깊이 우선 탐색(Depth First Search, DFS)과 너비 우선 탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있습니다. 이번 문제에서처럼 모든 경우의 수를 고려하되 트리의 깊이가 정해져 있는 경우..

문제 이번에 다뤄볼 문제는 14225번 문제 '부분수열의 합'입니다. 문제에서 연습해야 하는key-point는 비트마스크입니다. 우선 비트마스크가 무엇인지 알아보겠습니다. 비트마스크는 알고리즘 기법을 뜻하는건 아닙니다. 컴퓨터 과학에서 마스크(mask) 또는 비트마스크(bitmask)로 불리우는 개념은 특히 비트 필드에서 비트 연산에 사용되는 데이터를 뜻합니다. 즉, 2진수 형태의 비트에서 각 포지션별로 true(1), false(0)가 마스킹 된 데이터를 비트마스크라고 생각하면 됩니다. 비트 연산으로는 기본적으로 AND연산(&), OR연산(|), XOR(^)연산, NOT연산(~), 쉬프트연산(>)이 존재하며 우리는 오늘 비트마스크 그리고 AND연산과 쉬프트연산을 활용하여 문제를 해결해보겠습니다. 문제에..

문제 이번에 다뤄볼 문제는 10815번 문제 '숫자 카드'입니다. 문제에서 연습해야 하는key-point는 분할정복 입니다. 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘을 뜻합니다. 빠른 정렬이나 합병 정렬로 대표되는 정렬 알고리즘 문제와 고속 푸리에 변환(FFT) 문제가 대표적인 케이스 입니다. 이 문제는 분할정복 유형의 기초적인 예제 문제이며 다양한 구현 방식 중 이진탐색을 활용하여 해결해보겠습니다. 이진탐색(binary search)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘 입니다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작..

문제 이번에 다뤄볼 문제는 2138번 문제 ' 전구와 스위치'입니다. 문제에서 연습해야 하는key-point는 그리디 알고리즘 입니다. 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법입니다. 예를들어 'A도시에서 B도시까지 이동 할 때, 총 5개의 지점을 꼭 거쳐서 가야하며 이때의 최소 이동거리를 구하시오.' 라는 요구사항이 있다면 그리디 알고리즘을 사용할 경우 현재의 지점에서 가장 가까운 지점으로 이동을 하며 최종 결과를 도출해내는 알고리즘이라 생각하면 됩니다. 단, 여기서 주의해야 할 부분은 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 ..

문제 이번에 다뤄볼 문제는 1021번 문제 '회전하는 큐'입니다. 문제에서 연습해야 하는key-point는 Deque(덱)입니다. Deque이란 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태입니다. 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있고 큐와 스택을 합친 형태로 생각할 수 있습니다. 흔히 우리가 카드게임을 할 때 카드덱 이라고 부르는 그 덱과 유사한 개념이라고 생각할 수 있습니다. 우선 문제를 천천히 분석해 보겠습니다. 문제에서 결과로 원하는 값은 주어진 숫자를 순서대로 뽑기 위한 큐(카드덱)의 움직임 최솟값 입니다. 예제 입력 2를 통해 문제에서 원하는 값을 가져오는 과정에 대해 살펴보겠습니다. 주어진 연산과 상황은 아래와 같습니다. [연산 3가지] 1. 맨..

문제 이번에 다뤄볼 문제는 1654번 문제 '랜선 자르기'입니다. 이 문제는 이분탐색을 활용하여 해결 할 수 있습니다. 이분탐색(Binary Search)이란 이미 정렬되어 있는 배열에서 탐색 범위를 반씩 줄여 가며 찾고자 하는 값을 찾는 탐색 방법인데요. 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘입니다. 검색 범위에 해당하는 하한값, 상한값을 기준으로 중간값부터 탐색을 시작하는 방식이고 이에 대하여 1부터 100까지의 범위에서 77이란 숫자를 찾는 과정을 통해 예를 들어보겠습니다. 첫 시작은 하한값(1)과 상한값(100)의 중간값인 50부터 시작을 합니다. 찾고자 하는 77의 경우 중간값보다 큰 값이기 때문에 하한값(1)을 중간값(50)으로 상향 조정하여 재정의 합니다. 이렇게 될 경..