전체 글

[BOJ] - python 경찰차 (빡구현 + dp + dfs)

https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄 www.acmicpc.net 오늘은 그냥 스프란드-그런디 게임이론중에 대표문제인 님게임 시리즈를 둘러보더가, 좀 재밌는 dp문제 없나 싶어서 인터넷을 보다가 KOI 중등 2번을 발견하고 바로 풀게 되었습니다. 예전에는 KOI 초등부 문제에도 벽을 느껴서 잘 풀지 못하는 나였는데, 벌써 중등부 문제를 차근차근 풀고 있다니 너무 대견했다. 문제를 처음 보니, 빡구현 + dfs + dp문제 같았습니다. 전형..

[딥러닝 기초] - ResNET을 이해하기 위한 CNN 개요

이번에는 ResNET을 이해하기 위해 CNN을 기초 개념에 대해 탄탄히 다시 되새기고 넘어가고자 포스팅을 합니다. CNN은 2012년도 이미지 인식 대회에서 주목받게 되었는데요 여기서 토론토대 교수인 제프리 힌튼의 AlexaNet이 다른 머신러닝 모델들을 압도적인 차이로 이겼었습니다. CNN이 나오기 까지 AlexaNet은 컨볼루전 신경망인 CNN입니다. CNN은 이미지를 인식하는 대표적인 딥러닝 모델입니다. CNN도 여느 딥 러닝 모델처럼 사람의 시각 피질을 참고하여 만들어졌습니다. 뇌의 시각피질은 서로 계층적으로 연결되어 있습니다. 낮은 계층에서는 단순한 패턴을 인식하고 상위 계층으로 올라갈 수록 패턴을 인식해서 보다 복잡한 이미지로 추상화 하게 되는 것이죠. 처음의 CNN의 시초는 네오코그니트론이라..

[BOJ] - python 수열과 쿼리 21, 22 ( lazy propagation segment tree, offline query ) + Fenwick Tree

https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 이전에 공부한 느리게 전파되는 세그먼트 트리와 관련된 문제입니다. 사실 이 문제는 lazy propagation을 사용하지 않고도 해결할 수 있다. 바로 펜윅트리인데요 펜윅트리란..? https://www.acmicpc.net/blog/view/21 펜윅 트리 (바이너리 인덱스 트리) 블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를..

[BOJ] - python 열혈강호 (최대유량 + 이분매칭)

https://www.acmicpc.net/problem/11375 11375번: 열혈강호 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 한 개의 일만 할 수 있고, 각각 www.acmicpc.net 그냥 갑자기 에드몬드 카프 알고리즘이 떠올라서,,,? class7 도장깨기 하고 있는데, 이분매칭 간단한 문제가 있길래 풀어봤다. import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) ans = 0 def dfs(n): for i in task[n]: if check[i]: continue check[i] = 1 if not..

[BOJ] - python 스터디 그룹 (정렬 + 그리디 + 투포인터)

https://www.acmicpc.net/problem/14572 14572번: 스터디 그룹 첫 줄에 학생의 수 N, 알고리즘의 수 K, 문제에 설명한 D가 주어진다. (1 ≤ N ≤ 105, 1 ≤ K ≤ 30, 0 ≤ D ≤ 109) 이어 N명의 학생에 대한 정보가 아래와 같이 주어진다. M d (0 ≤ M ≤ K, 0 ≤ d ≤ 109): 해 www.acmicpc.net 문제는 이러하다, 보자마자 오,, 쉽겠는데? 하고 풀었다가 거진 5시간을 버린 문제이기도 해서 정리해본다. 우선 문제를 보자마자 $E$ = (그룹 내의 학생들이 아는 모든 알고리즘의 수 - 그룹 내의 모든 학생들이 아는 알고리즘의 수) * 그룹의 수라고 하길래 그룹의 수를 가장 올리면 그 나머지 항은 자연스럽게 올가갈 것이라 생각..

[딥러닝 논문 리뷰 - PRMI Lab] - Deep Residual Learning for Image Recognition (CVPR 2016) + 실습

본 논문에서는 깊은 네트워크를 학습시키기 위한 방법으로 잔여 학습(residual learning)을 제안했습니다. 원래 층이 깊어지면 깊어질 수록 어떠한 데이터로부터 Feature를 더 많이 추출해 낼 수 있게됩니다. 그로인해 모델이 더 높은 성능을 낼 수 있게 된다는 것이 일반적인 양상입니다. 당연히 레이어가 너무 깊어지게 되면 오히려 과적합 되서 성능이 떨어지게 됩니다. 위 그림처럼 기존의 CNN에서 layer가 더 깊으면 error rate가 더 높아지는 것을 볼 수 있습니다. 하지만 잔여 학습(Deep Residual Learning)을 적용한 CNN에서는 레이어의 깊이가 깊어져도 일반적인 양상인 error rate가 낮아지게 되었다는 것이 이 논문이 contribute한 내용입니다. CNN 모..

[딥러닝 논문 리뷰 - PRMI lab] - 배치 정규화(Batch Normalization) + 보편적 근사 정리(Universal Approximation Theorem)

배치 정규화 (Batch Normalization) 배치 정규화의 잘 알려진 장점은 아래와 같습니다. 학습 속도(training speed)를 빠르게 할 수 있습니다. 가중치 초기화(weight initialization)에 대한 민감도를 감소시킵니다. 모델의 일반화(regularization)효과가 있습니다. 정리하면 뒤에서 자세히 알아보겠지만, 배치 정규화를 사용하면 학습 속도가 빨라지며, 성능이 올라갈 뿐만 아니라 모델을 설계하는 입장에서 하이퍼 파라미터 세팅에 대한 부담이 줄어들기 때문에 사용하지 않을 이유가 없다고 할 수 있습니다. 그래서 실제로 이미지를 처리하는 분야에서 이러한 배치 정규화가 많이 사용되었습니다. 그 결과 모델의 성능을 많이 올릴 수 있었습니다. 배치 정규화는 위 그림에서 볼 ..

[BOJ] - 내 생각에 A번인 단순 dfs문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 극좌표압축 + 스위핑 + 완전탐색 + maximum subarray

https://www.acmicpc.net/problem/18251 18251번: 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) 욱제는 🎄포화이진트리🎄를 종이에 그렸다. 노드에 정수 가중치도 채워 넣었다. 욱제는 적당한 직사각형 영역을 잡아서, 영역 내에 있는 노드들의 가중치 합을 최대로 하고 싶다. 직사각형은 www.acmicpc.net 문제자체가 참 난감하다. 처음 든 생각은, 금광세그처럼 좌표를 압축한 다음에, 완전 탐색을 하는 것이였다. 그리고 잘 생각해보면, 2차원 스위핑을 1차원으로 치환할 수 있는데, dfs를 통해 각 노드에 시퀀스와 깊이를 저장해주면 이가 충분히 가능하다. import sys input = sys.stdin.readline '''..

[BOJ] - 제곱근 분할법 (Square Root Decomposition) + mo's 알고리즘

문제 크기가 N인 정수 배열 A가 있고, 여기서 다음과 같은 연산을 최대 M번 수행해야 하는 문제가 있다고 해 봅시다. 1. 구간 l, r (l a[i]: ans = a[i] 소스 1의 시간복잡도는 O(N)입니다. 2번 연산의 시간복잡도 A[i] = v는 O(1)입니다. 최대 쿼리가 M번 수행해야 하니 연산 하나의 시간 복잡도는 O(N)이 됩니다. 총 시간복잡도는 O(NM)입니다. 제곱근 분할법 제곱근 분할법을 사용하려면 크기가 N개인 배열을 크기가 sqrt(N)인 그룹으로 나누고, 각 그룹의 최솟값을 별도로 저장해야 합니다. 그룹의 크기가 sqrt(N)이니, 그룹의 개수도 sqrt(N)개입니다. N이 제곱수가 아닌 경우에는 그룹의 크기로 sqrt(N) a[i]: d[i//r] = a[i] 여기서 2번 ..

[Kotlin & Spring] - TODO 서비스에 코틀린 도입해서 리팩토링 하기 + Test Double

https://github.com/digimon1740/fastcampus-todo-java GitHub - digimon1740/fastcampus-todo-java Contribute to digimon1740/fastcampus-todo-java development by creating an account on GitHub. github.com 저는 강의에서 제공하는 위 깃허브를 참고해서 코틀린으로 마이그래이션 작업을 시작했습니다. 1. Kotlin DSL을 사용해 빌드 스크립트 마이그레이션 build.gradle.kts import org.jetbrains.kotlin.gradle.tasks.KotlinCompile plugins { id("org.springframework.boot") ver..