Computer Science and Engineering (6) 썸네일형 리스트형 모듈러(%)를 이용한 수의 구간성 알고리즘 문제를 풀다보면 브실 구간에서 만나는 정수론을 응용한 매우 간단한 반법론이다. 개념 자체는 구간의 크기 $n$을 정하고 $+\;\alpha$로 시작점을 정한다는 것이다. 설명은 간단하지만 초심자의 입장에선 "그래서 뭐 어디 쓰는데" 라는 생각이 들 수 있으니, 다양한 예제를 통해 이해해보자. 0. 구간성 아래 예제들을 관통하는 가장 중요한 개념이니 꼭 읽어보자 for문을 이용해 다음과 같은 수를 출력하고자 한다. 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 만약 마지막이 0 1 2 3 4로 끝났다면 단순하게 2중 for문으로 0 1 2 3 4를 4번 출력하면 됐을 것이다. 하지만 안타깝게도 마지막은 0 1 2로 끝나버렸다. 어떻게 하면 될까? 이 때 필요한 개념이 구간성이다... 반법론 모음 PS 글을 쓰다보니 방법론이라 하기엔 애매하고 알고리즘이라 하기엔 너무 사소하고, 그냥 넘어가기엔 조금의 설명이 필요하지만 워낙 쓰이는 곳이 많아 매번 설명하기에 번거로운 것들이 있었다. 필자는 그러한 것들을 모아 Semi-Methodology, 즉, 반법론(반쪽짜리 방법론 ㅎ)이란 글을 쓰려 한다. 그래서 PS 글을 쓰면서 생각나는 반법론들에 대한 글을 이 Semi Methodology 카테고리에 적고 이 글에 목록을 적을 예정이다. 모듈러(%)를 이용한 수의 구간성 알고리즘 문제를 풀다보면 브실 구간에서 만나는 정수론을 응용한 매우 간단한 반법론이다. 개념 자체는 구간의 크기 $n$을 정하고 $+\;\alpha$로 시작점을 정한다는 것이다. 설명은 간단하지만 초 areian0511.tistory.com 시간/공간 복잡도와 Big-O 표기법 "이 알고리즘은 시간복잡도가 $O(n^{2})$ 이라서 너무 비효율적이다." 알고리즘을 조금 공부해본 사람이라면 이런 말을 들어본적이 있을 것이다. 물론 난생 처음 들어봤어도 이제 차근차근 설명할테니 겁먹을 필요 없다. 이러한 말은 앞으로 알고리즘을 공부하며 계속해서 들을 것이고, 그만큼 기초가 되며 중요한 개념이다. 따라서 오늘은 시간/공간 복잡도란 무엇인지와 이를 편하게 표현해주는 Big-O(빅오) 표기법에 대해 알아보고자 한다. 시간/공간 복잡도란 무엇인가? 복잡도란 문제를 해결하기 위해 자원이 사용되는 정도이다. 이 때, 자원은 크게 시간과 공간 이 두가지를 의미한다. 따라서 시간을 자원으로 사용한다면 시간 복잡도 공간을 자원으로 사용한다면 공간 복잡도 라고 부른다. 조금 더 자세히 들여다보자. .. 알고리즘(Algorithm)이란? 단순한 의의 자체만 보면 문제를 해결하는 일련의 과정을 모두 알고리즘이라고 본다. 라면 끓이기를 예로 들어보자. 물 넣고 끓으면 면과 스프를 넣고 면을 익힌다. 이 과정을 알고리즘의 의의에 대입하면 문제 == 라면 끓이기 문제를 해결하는 일련의 과정 == 물 넣고~ 가 되는 것이다. 하지만 알고리즘은 실제로 이렇게 간단하지 않다. 우리가 말로써 하지 않은 너무 당연한 과정들이 컴퓨터에게는 그렇지 않기 때문이다. 지금 당장 라면 끓이기만 봐도 그렇다. 우리는 너무 당연하게 냄비를 꺼내서 물을 넣고, 너무 당연하게 가스불을 켜고, 너무 당연하게 물이 끓는지 눈으로 알 수 있고, 너무 당연하게 라면과 스프봉투를 뜯고, 너무 당연하게 냄비에 라면과 스프를 넣어서, 너무 당연하게 면이 다 익었는지 알 수 있다. .. Areian Project 소개글 1. 프로젝트를 시작하며 이름이 살짝 중2병에 걸린 것 같지만, 어릴적부터 사용하던 활동명 Areian(아리안)에 블로그로 공부글을 작성하는 것도 하나의 프로젝트로 생각하기에 만들어진 이름이다! 각설하고, 필자가 매우 뛰어난 PS 실력을 가진 것은 아니지만 그래도 솔브닥 P3을 달며 느꼈던 점이 있다. 바로 알고리즘 자체가 하나의 선형적인 공부로 이루어진 분야가 아닌 여러가지 분야를 묶어서 알고리즘이라 두루뭉실하게 부른다는 것이다. 미적분, 기하와 벡터, 확률과 통계, 선형대수학처럼 별개의 학문을 수학으로 퉁친다는 것과 비슷하다. 물론, 각각의 학문을 깊게 공부하다보면 선형대수학이 기하고 확통이 미적분이 되는 기적을 맛볼 수 있고, 이것은 알고리즘 또한 마찬가지이다. 하지만 초심자의 눈으로 봤을 때, 각.. Areian Project 커리큘럼 (2024-02-09 수정) Areian Project 소개글 Areian Project 소개글 이름이 살짝 중2병에 걸린 것 같지만, 어릴적부터 사용하던 활동명 Areian(아리안)에 블로그로 공부글을 작성하는 것도 하나의 프로젝트로 생각하기에 만들어진 이름이다! 각설하고, 필자가 매우 areian0511.tistory.com ㆍ알고리즘이란? 무서운 알고리즘들을 배우기 전에 알고리즘의 정의부터 알아봅시다. 알고리즘(Algorithm)이란? 단순한 의의 자체만 보면 문제를 해결하는 일련의 과정을 모두 알고리즘이라고 본다. 라면 끓이기를 예로 들어보자. 물 넣고 끓으면 면과 스프를 넣고 면을 익힌다. 이 과정을 알고리즘의 의의 areian0511.tistory.com ㆍ시간/공간 복잡도와 Big-O 표기법 시간/공간 복잡도와 자원의 .. 이전 1 다음
