분류 전체보기
-
[백준] 1707번 이분 그래프 (by Python)Programming/Algorithm 2021. 2. 6. 00:39
문제 처음에 이분 그래프의 정확한 의미를 모르겠어서 조금 헤맸지만 결국 핵심은 각 노드가 인접한 노드들과 다른 색깔을 가지고 있으면서, 총 2가지 색깔로 다 표현할 수 있는 그래프 라고 생각하면 될 것 같다. 이전의 연결 요소의 개수를 찾는 문제에서 BFS 방법보다 DFS 방법이 더 시간이 낮게 나오는 것을 확인하고 DFS로 들이댔지만 풀고 나니 BFS로 푸는 것이 더 나은 문제였다는 생각이 들어 BFS로도 풀어봤다. 그리고 DFS로 풀려면 sys.setrecursionlimit()을 일단 크게 줘야겠다는 교훈을 얻게 된 문제! 첫 번째 풀이 (by DFS) import sys input = sys.stdin.readline sys.setrecursionlimit(100000) k = int(input(..
-
[백준] 10971번 외판원 문제 2 (by Python)Programming/Algorithm 2021. 1. 31. 16:13
문제 문제의 구성이 기본적인 측면이 있어 사전지식 없이 아이디어를 떠올려 풀 수 있었으나 더 나은 해법을 찾던 중 해당 문제가 TSP(Traveling Salesperson Problem)라는 유명한 문제라는 것을 알았고, 관련된 알고리즘을 체계적으로 공부해보는 계기가 되었다. 덕분에 비트 연산 및 Dynamic Programming 방법에 대해 생각해볼 수 있어서 좋았다. 풀이 def isIn(i, A): return (A & (1
-
[백준] 9019번 DSLR (by Python)Programming/Algorithm 2021. 1. 29. 17:29
문제 다른 것을 하다가 싫증이 나서 가볍게 머리도 풀 겸 고른 BFS 문제인데, 나에게 또다른 시련을 안겨줄 줄은 몰랐다. 논리적으로 풀기 어려운 문제는 아니었으나, 구현하는 내가 자잘한 실수를 발견하지 못한 탓에 성공까지 시간이 좀 걸렸다. PS는 논리력만큼이나 꼼꼼함도 중요하다는 것을 되새기게 된 문제이다. 풀이 from collections import deque import sys def check(x, char): global parents global q global b global a global temp if parents[x][0] == -1: parents[x][0] = temp parents[x][1] = char q.append(x) if b == x: answer = '' whil..
-
[백준] 10972번 다음 순열 (by Python)Programming/Algorithm 2021. 1. 27. 16:54
문제 언뜻 보면 단순한 문제이지만, 내게는 그리 단순하지 않았다. 순열이 나열되는 순서를 논리적으로 표현하는 것에서 어려움을 겪었기 때문이다. 그렇기 때문에 처음에는 permutations 라이브러리를 사용해서 단순하게 해결하려고 시도를 했다. 첫 번째 풀이 from itertools import permutations n = int(input()) target = list(map(int, input().split())) array = list(map(list, permutations(range(1, n + 1)))) answer = array.index(target) if answer == len(array) - 1: print(-1) else: for i in array[answer + 1]: pri..
-
[백준] 14500번 테트로미노 (by Python)Programming/Algorithm 2021. 1. 26. 12:07
문제 문제를 읽으면 바로 모든 경우의 수를 시도해보는 브루트 포스 방식으로 풀어야 함을 알 수 있다. 그렇지만 고민이 되는 부분은 어떻게? 인 것 같다. 어떻게 회전도, 뒤집기도 가능한 테트로미노의 모양을 모두 테스트해볼 수 있을까? 더 나은 방법이 있을 거란 생각이 들었지만 일단 내가 시도해본 방법은 다음과 같다. 첫 번째 풀이 n, m = map(int, input().split()) array = [] answer = 0 shapes = [[(0, 0), (0, 1), (1, 0), (1, 1)], [(0, 0), (0, 1), (0, 2), (0, 3)], [(0, 0), (1, 0), (2, 0), (3, 0)], [(0, 0), (1, 0), (1, 1), (2, 1)], [(0, 0), (1..
-
[Deep Learning] 딥러닝이란? - 인공지능, 머신러닝과의 구분 및 기초 신경망Artificial Intelligence/Basic 2020. 9. 20. 20:01
인공지능, 머신러닝, 딥러닝? 인공지능, 머신러닝, 딥러닝은 최근 핫하게 떠오르고 있는 키워드들입니다. 그러나 이 단어들이 미디어에서 종종 비슷한 의미를 가지고 있는 듯 쓰여 정확한 상관관계가 헷갈릴 수 있겠다는 생각이 드는데요, 그래서 먼저 세 단어의 상관관계를 정리하고 넘어가도록 하겠습니다. 인공지능은 쉽게 말하자면 사람이 할 수 있는 일을 기계가 할 수 있도록 만드는 기술입니다. 예를 들어 알고리즘을 이용해 게임을 플레이하는 프로그램을 만들었다면, 이는 인공지능이라고 할 수 있습니다. 인공지능 중에서도 이렇게 논리, 검색 등을 사용해 우리가 이해할 수 있는 구조로 문제를 해결하는 인공지능을 Symbolic AI라고 합니다. 머신러닝은 수많은 데이터를 통해 그 안의 규칙을 학습해나가는 기술입니다. 사..
-
[논문리뷰] SATRN: On Recognizing Text of Arbitrary Shapes with 2D Self-AttentionArtificial Intelligence/Computer Vision 2020. 9. 13. 22:28
최근에 OCR (Optical Character Recognition)을 공부하며 관련 논문들을 읽고 있는데요, Clova AI에서 최근에 관련 논문을 내주셨다고 해서 읽어보게 되었습니다. 감사하게도 코드를 오픈소스로 공개해주시고 자료가 잘 정리되어 있어서 공부에 많은 도움이 되었습니다. 이 글의 내용은 상기 논문의 내용 및 이미지를 참고했음을 밝힙니다. 기존 방식의 문제점 Scene Text Recognition (STR)은 자연 상태의 이미지에서 주어진 텍스트의 내용을 알아내는 기술입니다. 이 과정에서 이미지의 특징을 추출하는 데에 CNN을 사용하고, Seq2Seq 구조의 RNN을 사용하여 순차적인 의존성을 파악하고, 그에 따른 문자열을 생성해내는 것이 기본 골자입니다. 기존의 방법은 입력 텍스트가 ..
-
[TypeScript] TypeScript 튜토리얼(1) - 컴파일하기Programming/Language 2020. 9. 6. 17:49
TypeScript란? TypeScript는 Microsoft에서 개발한 오픈소스 프로그래밍 언어입니다. Javascript의 상위 집합(superset)으로 ECMAScript의 최신 표준을 모두 지원하며 트랜스파일링되어 JavaScript 파일을 생성합니다. 느슨한 문법을 가지고 있는 JavaScript와 달리 정적 타입을 지원함으로써 개발자 간의 협업을 보다 용이하게 해주며, 디버깅에도 도움이 됩니다. 컴파일? ts 파일들은 그 자체로 구동되는 것이 아니라 해당 파일들로부터 트랜스파일링된 js 파일들이 구동되는 방식을 취하는데요, 바로 이 과정에서 엄격한 타입 검사를 거쳐 사전에 에러를 내주는 것이 TypeScript의 존재 의의라고 해도 과언이 아닐 것입니다. 그렇다면 이제 어떻게 ts 파일들을 ..