31828: MR.DR 문자열 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한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)일 것 같다는 ..
[동적계획법] NIM게임, 돌게임, 배스킨라빈스 31 게임 류의 풀이
·
PS/Algorithm
이전 숫자에서 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..
25419: 정수를 끝까지 외치자 (백준, python3)
·
PS/BOJ
시간 제한메모리 제한1초512MB문제두 명의 학생이 1이상 n이하의 정수를 외치는 게임을 하고 있다. 첫 번째 학생이 먼저 정수를 외친 후 두 명의 학생이 교대로 정수를 외친다. 이전 학생이 외친 정수가 a이면 현재 학생은 (a + 1)이상 (a + k)이하의 정수를 외쳐야 한다. 맨 처음 첫 번째 학생은 1이상 k이하의 정수를 외쳐야 한다. 추가로, 두 명의 학생이 외칠 수 없는 정수 목록이 주어지고, 두 명의 학생은 목록에 있는 정수를 외칠 수 없다. 마지막에 정수를 못 외치는 학생이 게임을 진다. 현재 학생이 외칠 수 있는 정수가 여러 개이면, 외칠 수 있는 정수 중 하나를 외친다. 두 명의 학생이 규칙에 맞게 플레이했을 때, 첫 번째 학생이 이기면 1을 출력하고 두 번째 학생이 이기면 0을 출력한..
5주차: 탐색 알고리즘(선형 탐색, 이분 탐색, 투 포인터)
·
🐨coalla 스터디 자료
이제 본격적인 알고리즘의 출발점을 지나봅시다. 지금까지 우리는 프로그램의 표준 입출력 처리 방법과 데이터 타입(자료형), 조건과 반복, 데이터 구조(선형, 비선형)를 배웠습니다. 이것을 토대로 어떤 문제를 해결하기 위한 정형화된 작업 절차, 알고리즘을 다룰 수 있습니다. 가장 먼저 해볼 것은 구조화된 데이터에서 원하는 값을 찾는 "탐색(search)"입니다.1. 선형 탐색(linear search)  선형 탐색은 가장 기본적이고 직관적인 탐색 방법입니다. 이 알고리즘을 좀 더 쉽게 풀어 쓴다면 "하나씩 다 꺼내보기"라고 할 수 있습니다. 정말 말 그대로 원하는 정보가 나타날 때까지 모든 데이터를 확인해보는 것이기 때문입니다. 그래서 작업 자체가 "비교"와 "반복"의 두 단계로 매우 단순하게 구성되어 있습..
4주차: 비선형 자료구조(집합, 맵, 트리, 그래프)
·
🐨coalla 스터디 자료
0. 비선형 자료구조 자료를 한 줄로 나열하는 리스트(배열), 스택, 큐, 덱 등의 자료 구조는 자료의 순차적 처리에 매우 유리합니다. 그런데 어떤 자료들은 선형적으로 관리하기 어렵습니다. 예를 들어, 2020 도쿄 올림픽 양궁 혼성 대진표를 데이터로 정리한다고 해봅시다. 선형적 자료 구조로 표현하려면 어떻게 해야 할까요? 어디부터 자료를 정리해야 할지 좀 난감합니다. 이렇게 선형적으로 관리하기 어려운 자료들은 "비선형 자료구조"로 관리할 수 있습니다. 이 대진표의 경우는 "트리"로 관리하면 아주 쉽게 표현할 수 있습니다. 비선형 자료구조에는 어떤 것들이 있는지 알아봅시다! 1. 집합(set) 집합하면 떠오르는 이미지가 있습니다. 이 집합(set)도 set이 맞지만, 컴퓨터 과학에서 말하는 set은 보통..
딕셔너리의 get() 활용법
·
python
get 메소드를 사용하면 딕셔너리 내에 키가 있는지 없는지 바로 확인 가능하다. 예외처리도 필요없고 조건 따로 달 필요도 없음. 한 짤 정리
1주차: 기본 입출력, 산술 연산자, 기본 자료형
·
🐨coalla 스터디 자료
coalla 스터디의 모든 과정은 python 환경에서 이루어집니다.일부 개념에 대한 설명이 다른 개발 환경과 차이가 있을 수 있습니다.백준 채점서버 파이썬 버전: python 3.11.5 (2024.08.04. 기준) 1. 기본 입출력  PS(problem solving)는 주어진 조건에 맞춰 작업을 수행하는 프로그램을 만들어 프로그램이 입력을 받고, 처리하고, 출력을 해내는지를 두고 경쟁하는 분야입니다. 프로그램이 할 일은 순서대로 "입력-처리-출력"입니다. 본격적인 알고리즘의 영역인 "처리"단계를 다루기 전에 전처리인 "입력"과 결과를 뱉어내는 "출력"을 올바르게 수행하는 연습을 해봅시다.    백준 온라인 저지의 입출력은 표준 입출력(standard input/output)에서 이루어집니다. 그러..
코딩 콘테스트를 위한 자기복제 도서관
·
PS/Algorithm
[정렬][탐색][기하]- 두 직사각형의 겹치는 영역 넓이 구하기 [동적계획법]- 님게임, 돌게임, 배스킨라빈스 31 게임 류
[기하] 두 직사각형의 겹치는 영역 확인하기
·
PS/Algorithm
직사각형의 위치를 다음과 같이 두 점의 좌표로 표현하자.두 직사각형 (x1, y1), (x2, y2)와 (x3, y3), (x4, y4)가 있다.(x1 두 직사각형이 겹치는 영역은 다음과 같이 표현할 수 있다. [cpp]int area = max(min(x2, x4) - max(x1, x3), 0) * max(min(y2, y4) - max(y1, y3), 0); [python]area = max(min(x2, x4) - max(x1, x3), 0) * max(min(y2, y4) - max(y1, y3), 0)
AtCoder Beginner Contest 361 F - x = a^b
·
PS/AtCoder
ABC361의 모든 문제 중 가장 짧고 가장 이해하기 쉬운 문제였으나 간단한 설명과 달리 꽤나 치밀한 아이디어가 필요했고 그걸 떠올리는 과정이 재밌어서 정리를 남겨본다.시간 제한메모리 제한2초1024MB문제1이상 N이하의 정수 x에 대하여 어떤 정수 a와 2이상의 정수 b로 x = ab로 표현 가능한 것은 얼마나 있는가? 입력입력은 아래 형식의 표준입력으로 주어진다.N 조건입력은 전부 정수이다.1 ≤ N ≤1018출력답을 정수로 출력하시오. 입력예199 출력예112문제의 조건을 만족하는 정수는 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81으로 12개다. 입력예21000000000000000000 출력예21001003332 풀이조건에 맞는 정수인 a의 b거듭제곱 꼴로 나타내어..
모듈러 연산의 역원(분수의 모듈러 연산)
·
기타
1.  모듈러 기본 연산모듈러 연산은 나머지를 구한다. 파이썬에서는 산술 연산자 %와 같다. 10 mod 3 = 10 % 3 = 1. 두 수 a, b에 대해 어떤 수로 모듈러 연산을 했을 때 결과가 같다면 a, b는 모듈러 합동이라고 한다. 합동 기호를 똑같이 사용하고 예를 들어 이런 식으로 표기한다.13 mod 4 = 1 (13을 4로 나눈 나머지는 1이고)9 mod 4 = 1 (9를 4로 나눈 나머지도 1이다.)13 ≡ 9 mod 4 ()보통 0 이상의 정수에만 모듈러를 사용하는 경우가 많다. 실제로 나머지가 있는 나눗셈은 초등학교 수준의 수학에서만 다루고 있다. 하지만 괴물같은 수학자들이 이런 연산을 0 이상의 정수에만 사용하게 냅둘리가 있나. 모듈러는 음수에도 적용할 수 있다. 음수로 확장된 모듈..
2642: 전개도 (깊이우선탐색)
·
PS/BOJ
시간 제한메모리 제한1초128MB문제아래에 주어진 전개도의 점선 부분을 접어서 주사위 모양의 정육면체를 만들 수 있는지를 생각해 보자. 전개도의 각 면은 1에서 6까지 서로 다른 정수로 표시되어 있다.전개도 (1)은 정육면체로 접을 수 있지만, 전개도 (2)는 정육면체로 접을 수 없다. 입력으로 주어진 전개도를 정육면체로 접을 수 있는지를 알아보는 프로그램을 작성하시오. 입력입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지의 정수들이 여섯 개 있고, 숫자 사이에는 빈칸이 하나씩 있다. 1에서 6까지의 숫자는 전개도의 면을 나타내고, 0은 전개도의 바깥 부분을 나타낸다. 출력입력된 전개도를 정육면체로 접을 수 있으면, 정육면체에서 1번으로 표시된 면의 맞은 편 면의 번호를 출력하고, 정육면체로 접을 ..
전라남도교육지원청
맞았습니다!!
상단으로

티스토리툴바