Patrick's Devlog

1. 문제 개요 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 1-1. 설명 괄호 문자열은 두 개의 괄호 기호인 '('와 ')' 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(VPS)이라 한다. 한 쌍의 괄호 기호로 된 "()" 문자열은 기본 VPS라 부른다. x가 VPS라고 가정할 때 이것을 하나의 괄호에 넣은 새로운 문자열 "(x)"도 VPS가 된다. 그..

1. 문제 개요 https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B > B >> V; int day = ..

1. 문제 개요 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 1-1. 설명 N개의 정수 A[1], A[2], ..., A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 첫줄에 자연수 N이 주어지고 다음 줄에 N개의 정수가 주어진다. 다음 줄에는 M이 주어지고, 그 다음줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 1-..

개요 공부를 진행하다 오랜만에 이진 탐색을 꺼내려니 기억이 잘 나지 않아서 정리를 해두었다. 단순한 알고리즘이라, 정리해두고 기억이 나지 않을때 가끔씩 살펴보려 한다. 이진 탐색 알고리즘(Binary Search Algorithm) 정렬과 함께 가장 기초인 알고리즘으로 꼽힌다. 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 정확히 설명하면 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단해 맨 앞부터 검색하거나 중간부터 검색한다. 이진 탐색의 원리는 사전을 찾을 때 사전을 펴서 찾는 단어가 없으면 ..

1. 문제 개요 https://www.acmicpc.net/problem/10769 10769번: 행복한지 슬픈지 승엽이는 자신의 감정을 표현하기 위해서 종종 문자 메시지에 이모티콘을 넣어 보내곤 한다. 승엽이가 보내는 이모티콘은 세 개의 문자가 붙어있는 구조로 이루어져 있으며, 행복한 얼굴을 나 www.acmicpc.net 1-1. 설명 승엽이는 이모티콘을 좋아해서 메시지에 종종 이모티콘을 붙인다. 행복할 땐 :-)를, 슬플땐 :-(를 보낸다. 혜성이는 승엽이의 이모티콘을 싫어하므로 승엽이의 문자가 오면 전체적인 분위기만 판단해서 알려주는 프로그램을 작성하고자 한다. 1-2. 제한 사항 - 첫줄에 최소 1개, 최대 255개 문자 입력 - 이모티콘 포함되지 않을 시 none - 행복한 이모티콘과 슬픈 이..

1. 문제 개요 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 1-1. 설명 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지 번호가 붙어있으며, 1번 카드가 제일 위에 있고 N번 카드가 제일 아래인 상태로 카드가 놓여있다. 이제 다음과 같은 동작을 카드가 한장 남을때 까지 반복한다. 우선 제일 위에 있는 카드를 바닥에 버리고, 그 다음 제일 위에 있는 카드를 맨 아래로 보낸다. N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하..

개요 알고리즘 문제를 풀다가 배낭 관련 문제를 풀기 위해 기본적인 이론을 공부하고 코딩을 진행해보려고 한다. 저번처럼 유튜브 채널 코드없는 프로그래밍님의 Knapsack Problem 영상을 통해 공부를 진행할 예정이다. 자세한 내용을 알고싶다면 https://www.youtube.com/watch?v=rhda6lR5kyQ에서 확인하면 된다. Knapsack Problem 배낭 문제는 Dynamic Programming의 아주 대표적인 문제이다. 이는 조합 최적화의 문제이다. 간단하게 설명하자면 한 여행가가 지니고 있는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있으며, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 이해가 잘 안된다면 아..

1. 문제 개요 https://programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 1-1. 설명 선행 스킬은 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻한다. 예를 들면 선행 스킬 순서가 스파크 -> 라이트닝 볼트 -> 썬더 일 때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 한다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개 변수로 주어질 때, 가능한 스킬 트리의 개수를 return 하는 solution 함수를 작성한다. 1-2. 제한 사항 - 스킬은 알파벳 대문자로 표기, 모든 문자열은 대문자로만..