분류 전체보기
-
[백준] 17070번 파이프 옮기기 1 (by Python)Programming/Algorithm 2021. 4. 8. 22:52
문제 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 처음에는 직관적으로 생각나는 대로 다음과 같이 BFS로 풀었다. import sys from collections import deque input = sys.stdin.readline n = int(input()) arr = [list(map(int, input().split())) for _ in range(n)] q = deque() q.append([(0, 0), (0..
-
[백준] 2293번 동전 1 (by Python)Programming/Algorithm 2021. 3. 31. 20:15
문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 DP가 늘 그렇듯, 아이디어가 중요한 문제이다. n, k = map(int, input().split()) arr = sorted([int(input()) for _ in range(n)]) ans = [0 for i in range(k + 1)] ans[0] = 1 for i in range(1, k + 1): for j in arr: if i >= j: ans[i] += ans[i -..
-
[논문리뷰] StarGAN: Unified Generative Adversarial Networks for Multi-Domain Image-to-Image TranslationArtificial Intelligence/Computer Vision 2021. 3. 30. 07:27
개요 기존의 GAN 기반 Image-to-Image Translation 모델들은 domain을 바꿀 때마다 해당 translation에 대한 모델을 가지고 있어야 했습니다. 예를 들어 blond hair와 black hair라는 두 domain에 대해 학습할 때, blond에서 black으로 바꾸는 모델과 black에서 blond로 바꾸는 모델이 별개로 존재한단 이야기입니다. 때문에 k개의 도메인을 가지고 있을 때에 k(k - 1)개의 translation model을 가지게 되며, 이는 데이터를 충분히 활용하지 못하는 동시에 parameter 수를 불필요하게 늘리는 결과를 낳았습니다. StarGAN은 이러한 점에 착안해 서로 다른 domain 간의 translation을 단 하나의 모델로도 가능하도록..
-
[백준] 14719번 빗물 (by Python)Programming/Algorithm 2021. 3. 26. 01:32
문제 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 h, w = map(int, input().split()) block = [[False] * w for _ in range(h)] height = list(map(int, input().split())) for i, ht in enumerate(height): for j in range(ht): block[j][i] = True i, count = 0, 0 ans = ..
-
[백준] 1786번 찾기 (by Python)Programming/Algorithm 2021. 3. 24. 17:57
문제 https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 풀이 parent string에 pattern string이 포함되어 있는지 찾을 수 있는 KMP 알고리즘에 대한 문제이다. KMP 알고리즘은 다음과 같다. 먼저, pattern과 같은 길이의 table array를 만들어준다. 이 때 pattern에서 prefix와 같은 내용의 postfix가 있다고 가정할 때, table의 원소는 같은 index를 가진 character가 postf..
-
[백준] 1062번 가르침 (by Python)Programming/Algorithm 2021. 3. 24. 17:13
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 브루트 포스 방식으로 푸는 비트마스킹 문제이다. 처음에는 비트마스킹 방식이 익숙하지 않아서 set으로 시도해봤으나 시간 초과의 벽에 막혀 비트마스킹 방법으로 풀게 되었다. import sys from itertools import combinations input = sys.stdin.readline def convert(x): return ord(x) - ord('a') def..
-
[논문리뷰] CRAFT: Character Region Awareness for Text DetectionArtificial Intelligence/Computer Vision 2021. 3. 21. 06:15
개요 이 논문은 Scene Text Detection Task에서 bounding box가 직사각형 모양이 아닌 경우들에 있어서 기존의 모델들이 가지고 있었던 한계점을 돌파하는 데에 그 주안점을 두고 있습니다. 바로 word level이 아니라 character level로 detect한 후 character들 간의 관계를 찾는 방식인데요, 개인적으로 주어진 데이터셋에 문제해결방식을 맞추는 것이 아니라 문제해결방식에 데이터셋을 맞추는 인상을 받아 놀라웠습니다. 그럼 어떻게 ClovaAI가 풀어나갔는지 간단히 살펴보도록 하겠습니다. 이 포스팅에서 첨부하는 이미지 및 코드는 아래 링크들로부터 가져왔음을 밝힙니다. 코드: https://github.com/clovaai/CRAFT-pytorch 논문: http..