이제 본격적인 알고리즘의 출발점을 지나봅시다. 지금까지 우리는 프로그램의 표준 입출력 처리 방법과 데이터 타입(자료형), 조건과 반복, 데이터 구조(선형, 비선형)를 배웠습니다. 이것을 토대로 어떤 문제를 해결하기 위한 정형화된 작업 절차, 알고리즘을 다룰 수 있습니다. 가장 먼저 해볼 것은 구조화된 데이터에서 원하는 값을 찾는 "탐색(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 게임 류

직사각형의 위치를 다음과 같이 두 점의 좌표로 표현하자.두 직사각형 (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)

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 이상의 정수에만 사용하게 냅둘리가 있나. 모듈러는 음수에도 적용할 수 있다. 음수로 확장된 모..