Learn algorithm

서론 네트워크 플로우(Network Flow) 알고리즘은 네트워크 내에서 한 지점에서 다른 지점으로 가능한 최대의 ‘유량(flow)’을 찾는 문제를 해결하기 위해 사용됩니다. 여기서 말하는 ‘네트워크’는 간선(edge)들이 정점(vertex)들을 연결하는 그래프로, 각 간선에는 그 간선을 통해 흘러갈 수 있는 최대 흐름의 양(capacity)이 할당되어 있습니다. 네트워크 플로우 문제는 다양한 형태로 나타날 수 있으나, 가장 기본적인 형태는 소스(source)에서 싱크(sink)로의 최대 유량을 찾는 문제입니다. 정의 유량 네트워크(flow network)란 각 간선에 용량(capacity)이라는 속성이 존재한는... Read More

운영체제란? 운영체제(Operating System)는 컴퓨터 시스템의 핵심 소프트웨어로서, 하드웨어와 응용 프로그램 간의 인터페이스 역할을 한다. 운영체제는 다양한 기능과 서비스를 제공하여 사용자 및 응용 프로그램이 시스템 자원을 효율적으로 활용할 수 있도록 지원한다. 운영체제의 역할과 기능 운영체제의 주요 역할과 기능은 다음과 같다: 자원 관리(Resource management): CPU, 메모리, 입출력 장치 등의 시스템 자원을 효율적으로 관리하고 할당 메모리 관리(Memory management): 물리적 메모리를 관리하고 가상 메모리 기술을 통해 메모리의 효율적인 사용을 지원 입출력 관... Read More

준비물 Arduino uno OLED SSD1306 breadboard MP3-TF-16P V3.0 1. 개요 지금부터 만들것은 스펙트럼 분석기(Spectrum Analyzer)이다. 작동 방식은 마이크에 소리가 닿으면 아두이노에서 푸리에 변환을 하여, oled로 변환한 그래프를 보는 것이다. 2. OLED 초기 세팅 선 연결 GND -> GND VCC -> 5V SCL -> A5 SDA -> A4 그림으로 보면 이렇다. hello world 출력 println을 사용하여 hello world를 출력해보자 #include <SPI.h> #includ... Read More

1. 에니그마 에니그마는 여기서 어떻게 제작하는지 알려줬다. 키트 없이 직접 한땀한땀 만들었다.. 중3때 졸업작품으로 만들었는데 버튼에 저항값이 달라서 힘들었던 기억이 생각난다. 2. 미세먼지 측정기 미세먼지는 키트가 있었는데 따로 좋음,보통,나쁨을 간단하게 확인할 수 있게 따로 LED를 넣어서 코드를 직접 짜서 넣었다. 이건 고1때 만들었다. 3. MP3 플레이어 마지막으로 MP3 플레이어를 만들었다. 이건 고1 겨울방학때 만들었다. 볼륨조절기능이랑 이전곡,다음곡,멈추기 같은 기능을 만들었다. 이거 만드느라 라이브러리를 뜯어봤던 기억이 난다.. Read More

준비물 python3, Django, PowerShell 1단계 PowerShell을 켜서 다음 명령어를 실행시킨다. cd \ mkdir venvs cd .\venvs\ python -m venv mysite cd .\mysite\ cd .\Scripts\ .\activate 성공한 화면 2단계 cd \ mkdir projects cd .\projects\ mkdir mysite cd .\mysite\ 여기서 장고를 설치하지 않았다면 python -m pip install --upgrade pip pip install django django-admin startproject config . pyth... Read More

문제 BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다. 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오. 해설 단순하게 생각해보면 그래프 안에 깊이가 4이상인 트리가 존재하는지 판별하는 문제로 바꿀 수 있다. 접근방식 1 (dfs) #include <bits/stdc++.h> using namespa... Read More

서론 정렬은 데이터의 열을 특정 순서에 따라 줄을 세우는 과정이다. 정렬은 분할정복,힙 등의 다양한 알고리즘 기법을 배울 수 있는 주제이다. 다양한 정렬 알고리즘   평균 시간복잡도 최악 시간복잡도 공간복잡도 안정정렬 비고 삽입정렬 $O(N^2)$ $O(N^2)$ $O(1)$ O 간단한 정렬법 병합정렬 $O(n \log_2 n)$ $O(n \log_2 n)$ $O(N)$ ... Read More

문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다. 해설 단순히 특정 구간의 최솟값과 최댓값을 각각 배열에 저장한다면 메모리... Read More

문제 아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나... Read More

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 해설 문제의 규칙을 점화식으로 표현하자면 다음과 같다. $ \mathrm{D}(i) = \begin{cases} D[i-1]+1 \ min(D[i],D[i/2]) & i\pmod2 = 0 \ min(D[i],D[i/3]) & i\pmod3 = 0 \end{case... Read More

서론 A라는 문제에 대해서 B라는 결과값을 나타내는 알고리즘 R이 가능한 모든 입력에 대해 정확하게 동작할까요? 그렇다면 그 사실을 증명할 수 있을까요? 수학적 귀납법(Mathematical Induction) 수학적 귀납법은 알고리즘이 문제를 해결하는 과정 안에 있는가를 증명하는 방법입니다. 먼저 알고리즘이 일부 입력에서 올바른 결과를 출력하는 것을 보이고, 그 다음으로 입력이 올바르다면 알고리즘이 올바른 결과를 출력하는 것을 증명합니다. 문제 예를 들어, 악수를 하는 방법에 대해 우리는 다음과 같은 사실을 안다고 가정한다. 모든 사람은 직사각형 탁자 하나의 한 면에 앉아있다. 각 사람들은 자신의 왼... Read More

자료구조란? 자료구조는 자료의 표현과 그것과 관련된 연산을 의미합니다. 알고리즘 문제를 풀다보면, 특정 값을 자료구조 형태로 저장하고 필요에 따라 원하는 값을 꺼내는 작업이 매우 많이 일어납니다. 이렇게 자료구조에 값을 넣거나, 원하는 값을 꺼내거나, 원하는 값이 존재하는지 판정하는 요구를 쿼리(query)라고 부릅니다. 자료구조 1 첫번째로는 배열과 연결리스트, 해시테이블을 배웁니다. 각 자료구조의 쿼리 복잡도는 다음과 같습니다.   배열 연결리스트 해시테이블 c++ 라이브러리 vector ... Read More

문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 “백설 공주와 일곱 난쟁이”의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 접근방식 1 (조합전체탐색,brute_force) #include <stdio.h> #include <algorithm> #include ... Read More

문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 접근방식 1 (빠른 모듈로 거듭제곱법) a^b * a^b = a^2b a^b == a^b-1 * a^1 if a%2==0 –> a^(b/2) % c * a^(b/2) % c else a^b-1 == a^(b-1) * a % c #include <iostr... Read More

1 .다음 계산시간(t)을 Big O표기법으로 나타내라.(입력크기는 n) t(n) = $2023^n+n!$ -> $O(n!)$ t(n) = $n^{2023} + {2023}^n$ -> $O({2023}^n)$ t(n) = $1000000$ -> $O(1)$ Read More

서론 좋은 알고리즘이란 무엇일까? 시간이 적게 걸리는 알고리즘일까?, 아니면 리소스를 적게 사용하는 알고리즘일까? A 라는 알고리즘과 B 라는 알고리즘을 비교하는 방법은 어떤 방법이 있을까? 리소스는 뒤로하고, 좀더 빠른 알고리즘이 무엇인지 가장 간단하게 비교를 하는 방법은 같은 입력에 대해서 두 알고리즘의 수행시간을 측정하는 것 입니다. 하지만 위와 같은 측정방법은 컴파일러, cpu등의 하드웨어, 운영체제, 프로그래밍 언어 등과 같이 수많은 요인에 의해서 바뀔 수 있기 때문입니다. 그렇다면 어떤 측정방법이 있을까요? 시간복잡도 시간복잡도는 알고리즘의 수행 시간을 분석하는 방법 중 하나입니다. 알고리즘의 수행 시... Read More

알고리즘 강의글을 쓰는 이유 고2 시절 3개월 정도 대충 공부하다 KOI 1차 37퍼 나와서 떨어졌다. 그래도 좋은 취미가 될것같아서 이렇게 글을 써 보려 한다. 알고리즘 강의 목록 강의 목록은 ‘알고리즘 문제 해결 전략(구종만)’,’바킹독의 실전 알고리즘’,’문제 해결력을 높이는 알고리즘과 자료 구조(오츠키 켄스케)’를 보고 나에게 맞는 커리큘럼을 다음과 같이 계획하였다. 1. 알고리즘의 복잡도 분석 시간복잡도와 공간복잡도의 개념 설명 2. 자료구조 배열, 연결리스트, 스택, 큐, 덱 등의 자료구조의 복잡도와 쿼리 설명 3. 알고리즘의 정당성과 증명 알고리즘을 증명하는 방법 4. 정렬(Sort) 5. 이진 탐... Read More

문제 다음과 같이 정의된 수열이 있다. D[1] = A D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합 예를 들어 A=57, P=2일 때, 수열 D는 [57, 74(=52+72=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다. 이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 [57, 74, 65, 61]의 네 개의 수가 남게... Read More

문제 수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자. 접근방식 1 (구조체) 구조체배열에 value와 index를 저장한 후, value값만 비교해서 정렬을 한다. 그 다음엔 앞의 수와 비교해서 정렬한 index 값을 value에 넣는다. 마지막으로 배열의 index값만 비교해서 처음과 같은 상태로 만든 후, index에 맞게 출력한다. #include &... Read More

선행지식 그래프 탐색 (플로이드-워셜 알고리즘) 문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 접근방식 1 (bfs) m 에서 시작해서 갈 수 있는 모든 경로를 g배열에 기록한다. #include <bits/stdc++.h> using namespace std; int a[101][101]={},g[101][101]={},n,m=0; bool v[101]={}; queue<int> bfsq; void search(int x){ if(v[x]){ g[m][x]=1; ... Read More

총평 문제는 무난했다. 실수나 긴장만 하지 않는다면 sfpc문제들을 대부분 풀 수 있을것 같다. 준비하기 문항 주차 공간1 어떤 주차장에 n개의 주차 공간이 있고, 각 주차 공간의 바닥에는 1부터 n까지의 번호가 쓰여있다. 다음은 주차 공간이 22개인 주차장의 모습이다. 다음 그림은 첫째 날 9시의 주차 공간 상태이다. 다음 그림은 둘째 날 9시의 주차 공간 상태이다. 주차 공간이 n개인 주차장에 대하여 이틀간의 주차 상태를 입력 받아, 이틀 동안 모두 사용되지 않은 주차 공간의 개수와 이틀 동안 모두 사용된 주차 공간의 개수를 출력해보자. 풀이 (implementation) bool 배열을 사용해서 주... Read More

준비물 USB, 노트북, x32 주의사항 일단 x32의 펌웨어 업데이트를 해야된다. 펌웨어 업데이트를 할 때 USB는 FAT32로 포멧을 진행해야된다. 노트북에 소프트 웨어 설치 베링거 사이트로 들어가서 여기서 X32 Edit(PC)를 선택하고 설치한다. x32 설정 x32를 키면 이렇게 나오는데 여기서 setup을 눌러준다. 여기서 page select를 눌러서 network로 가면된다. 위에서 부터 ip address, subnet mask, gateway 가 있는데 만약 세팅이 잘 못 되어있다면 직접 세팅을 바꾸어야 한다. ip address는 공유기에 맞게 성정하면 되고 세팅한 후에는 꼭... Read More

소감 대회에서 1등을 했지만… 아쉽게도 마지막 문제에서 접근을 잘못해서 부분점수만 맞고 끝났다. 문제 7. 카이사르 암호 암호는 민감한 정보를 보호하기 위하여 오래전부터 사용되었는데, 카이사르 암호(또는 시저 암호, Caesar cipher) 는 암호학에서 다루는 간단한 치환 암호의 일종이에요. 3글자씩 밀어내는 카이사르 암호로 “절대 브루투스를 믿지 마라”는 뜻의 문장을 암호화하면 NEVER TRUST BRUTUS MDUDQ SQTRS AQTSTR 이렇게 돼요. 카이사르 암호는 약 기원전 100년 경에 만들어져 로마의 장군인 카이사르가 동맹군들과 소통하기 위해 만든 암호에요. 단순하고 간단하여 일반인도 ... Read More

선행지식 유클리드 호제법 문제 효성이는 길이가 $N$인 수열 $A$에서 $X$와 서로소인 수들을 골라 평균을 구해보려고 한다. 효성이를 도와 이를 계산해주자. 접근방식 1 (유클리드 호제법) 쉬운 문제다. 최소공배수가 1이면 서로소이다. 그리고 그것을 기호로 표현 하면 gcd(A,X)==1 이 된다. gcd(A,X)는 유클리드 호제법으로 구할 수 있는데 유클리드 호제법은 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여... Read More

소감 대회에서 우승하기에는 아직 멀었다. 그래도 하나라도 풀어서 좋았다. 문제 A 눈 치우기 지난 밤 겨울 숲에는 눈이 많이 내렸다. 당신은 숲의 주민들을 위해 눈이 오지 않는 동안 모든 집 앞의 눈을 치우고자 한다. 당신은 1분에 한 번씩 두 집을 선택해서 두 집 앞의 눈을 각각 1만큼 치우거나, 한 집을 선택해서 그 집 앞의 눈을 1만큼 치울 수 있다. 모든 집 앞의 눈을 전부 치울 때까지 걸리는 최소 시간은 얼마일까? 접근방식 1 (greedy) 단순하게 생각했다. 두 집앞의 눈을 각각 1만큼 치우는 게 가장 효율적인 방법이여서 내림차순 정렬을 하면서 배열의 0번과 1번을 각각 -1을 0이 되기 전까지... Read More

선행지식 map 문제 국민대학교에서는 매 학기 시작 전 종합정보시스템에서 수강신청을 한다. 매 수강신청마다 아주 많은 학생들이 몰려 서버에 많은 부하가 가기 때문에, 국민대학교에서는 수강신청 부하 관리 시스템을 도입하기로 결정하였다. 새로운 관리 시스템은 다음과 같은 방식으로 동작한다. 수강신청 버튼이 활성화 된 후, 수강신청 버튼을 조금이라도 빨리 누른 학생이 대기목록에 먼저 들어간다. 이미 대기열에 들어가 있는 상태에서 다시 수강신청 버튼을 누를 경우 대기목록의 맨 뒤로 밀려난다. 잠시 후 수강신청 버튼이 비활성화 되면, 대기목록에서 가장 앞에 있는 학생부터 자동으로 수강신청이 완료되며, 수강 가... Read More

오늘 해커톤에 같이 나가는 동아리 부원이 나에게 질문을 했다. 엘리스 아카데미에서 코드를 실행하면 정상적으로 작동을 하는데, Visual Studio에서는 실행이 안된다는 것이였다. 실행이 안된 이유는 int main을 쓰지 않았기 때문이다. 왜 main을 쓰면 Visual Studio에서 오류가 생길까? main 함수 main 함수는 C에서 미리 정의된 키워드이자 함수다. 프로그램의 실행시작 및 종료를 담당하는 모든 C프로그램의 첫 번째 함수다. int main 함수와 main 함수의 차이점 int main 함수와 main 함수의 가장 큰 차이점은 리턴값에 있다. int main 함수는 int 형을 반환... Read More

1008 : [기초-출력] 출력하기08 유니코드 찾는데 너무 힘들었다. #include <stdio.h> int main() { printf("\u250C\u252C\u2510\n\u251C\u253C\u2524\n\u2514\u2534\u2518"); return 0; } 1022 : [기초-입출력] 문장 1개 입력받아 그대로 출력하기 EOF를 이용하여 풀었다. #include <stdio.h> int main() { int i=0; char data[2001]=""; while(scanf("%c",&data[i])!=EOF){ i+... Read More