시간 제한메모리 제한1초1024MB문제 길이가 4 이상인 영어 대문자로만 이루어질 수 있는 서로 다른 모든 문자열에 대해, 0개 이상의 문자를 제거하였을 때 문자열 MRDR이 되는 문자열을 MR.DR 문자열이라고 한다. 정수 N이 주어질 때, 길이가 N인 MR.DR 문자열의 개수를 구하는 프로그램을 작성하라. 입력첫 번째 줄에 정수 N이 주어진다. ( 4 ≤ N ≤ 100,000) 출력길이가 N인 MR.DR 문자열의 개수를 출력하라. 이때 정답이 매우 커질 수 있으므로 정답을 1,000,000,007 (=109 + 7)로 나눈 나머지를 출력하라.풀이 시간 제한이 1초, N의 범위가 100,000까지인 것으로 보아 최소한 O(NlogN)으로 끝내야 한다. 근데 이분탐색 요소는 없으니 O(N)일 것 같다는 ..

이전 숫자에서 k개의 연속된 숫자를 외칠 수 있고 n을 외치면 승리하는 조건에서,n+1 길이의 dp를 생성하고, 필승패를 1로 표기, 나머지는 0으로 표기한다. [cpp]// 최선의 수를 둘 때 선공이 승리할 수 있으면 True#include using namespace std;bool NIM(int n, int k) { vector dp(n + 1, 0); for (int i = n; i > 0; i--) { for (int j = i + 1; j  [python]# 최선의 수를 둘 때 선공이 승리할 수 있으면 Truedef NIM(n, k): dp = [0] * (n + 1) for i in range(n, 0, -1): for j in range..

시간 제한메모리 제한1초512MB문제두 명의 학생이 1이상 n이하의 정수를 외치는 게임을 하고 있다. 첫 번째 학생이 먼저 정수를 외친 후 두 명의 학생이 교대로 정수를 외친다. 이전 학생이 외친 정수가 a이면 현재 학생은 (a + 1)이상 (a + k)이하의 정수를 외쳐야 한다. 맨 처음 첫 번째 학생은 1이상 k이하의 정수를 외쳐야 한다. 추가로, 두 명의 학생이 외칠 수 없는 정수 목록이 주어지고, 두 명의 학생은 목록에 있는 정수를 외칠 수 없다. 마지막에 정수를 못 외치는 학생이 게임을 진다. 현재 학생이 외칠 수 있는 정수가 여러 개이면, 외칠 수 있는 정수 중 하나를 외친다. 두 명의 학생이 규칙에 맞게 플레이했을 때, 첫 번째 학생이 이기면 1을 출력하고 두 번째 학생이 이기면 0을 출력한..

이제 본격적인 알고리즘의 출발점을 지나봅시다. 지금까지 우리는 프로그램의 표준 입출력 처리 방법과 데이터 타입(자료형), 조건과 반복, 데이터 구조(선형, 비선형)를 배웠습니다. 이것을 토대로 어떤 문제를 해결하기 위한 정형화된 작업 절차, 알고리즘을 다룰 수 있습니다. 가장 먼저 해볼 것은 구조화된 데이터에서 원하는 값을 찾는 "탐색(search)"입니다.1. 선형 탐색(linear search)  선형 탐색은 가장 기본적이고 직관적인 탐색 방법입니다. 이 알고리즘을 좀 더 쉽게 풀어 쓴다면 "하나씩 다 꺼내보기"라고 할 수 있습니다. 정말 말 그대로 원하는 정보가 나타날 때까지 모든 데이터를 확인해보는 것이기 때문입니다. 그래서 작업 자체가 "비교"와 "반복"의 두 단계로 매우 단순하게 구성되어 있습..

0. 비선형 자료구조 자료를 한 줄로 나열하는 리스트(배열), 스택, 큐, 덱 등의 자료 구조는 자료의 순차적 처리에 매우 유리합니다. 그런데 어떤 자료들은 선형적으로 관리하기 어렵습니다. 예를 들어, 2020 도쿄 올림픽 양궁 혼성 대진표를 데이터로 정리한다고 해봅시다. 선형적 자료 구조로 표현하려면 어떻게 해야 할까요? 어디부터 자료를 정리해야 할지 좀 난감합니다. 이렇게 선형적으로 관리하기 어려운 자료들은 "비선형 자료구조"로 관리할 수 있습니다. 이 대진표의 경우는 "트리"로 관리하면 아주 쉽게 표현할 수 있습니다. 비선형 자료구조에는 어떤 것들이 있는지 알아봅시다! 1. 집합(set) 집합하면 떠오르는 이미지가 있습니다. 이 집합(set)도 set이 맞지만, 컴퓨터 과학에서 말하는 set은 보통..

get 메소드를 사용하면 딕셔너리 내에 키가 있는지 없는지 바로 확인 가능하다. 예외처리도 필요없고 조건 따로 달 필요도 없음. 한 짤 정리

coalla 스터디의 모든 과정은 python 환경에서 이루어집니다.일부 개념에 대한 설명이 다른 개발 환경과 차이가 있을 수 있습니다.백준 채점서버 파이썬 버전: python 3.11.5 (2024.08.04. 기준) 1. 기본 입출력  PS(problem solving)는 주어진 조건에 맞춰 작업을 수행하는 프로그램을 만들어 프로그램이 입력을 받고, 처리하고, 출력을 해내는지를 두고 경쟁하는 분야입니다. 프로그램이 할 일은 순서대로 "입력-처리-출력"입니다. 본격적인 알고리즘의 영역인 "처리"단계를 다루기 전에 전처리인 "입력"과 결과를 뱉어내는 "출력"을 올바르게 수행하는 연습을 해봅시다.    백준 온라인 저지의 입출력은 표준 입출력(standard input/output)에서 이루어집니다. 그러..

[정렬][탐색][기하]- 두 직사각형의 겹치는 영역 넓이 구하기 [동적계획법]- 님게임, 돌게임, 배스킨라빈스 31 게임 류