본문 바로가기

전체 글

 (38)
Output units - Sigmoid Unit & Softmax Unit ※ Ian Goodfellow의 Deep Learning, Chapter 6의 일부를 정리한 내용입니다. ※ Logistic 함수는 sigmoid 함수의 한 종류이지만 이하의 서술에서 혼용되어 사용될 수 있습니다. 1. Output Units output units이란 다층 신경망에서 output layer를 구성하는 unit을 말한다. 2. Bernoulli 분포에 대한 Sigmoid Units $0$ 또는 $1$을 갖는 이진 변수 $y$가 있다고 하자. 다층 신경망 구조에서 $\boldsymbol {x}$가 입력으로 주어졌을 때, 이를 구분하여 $y={0, 1}$을 출력하도록 모델을 설계하는 것은 Bernoulli 분포 하에서 전형적인 classification 문제이다. 본 절은 이때 사용되는 ou.. 2022. 6. 22. 04:51
[방학의 PS] 다이나믹 프로그래밍 2 - BOJ_1003 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 피보나치 함수가 문제로 나왔습니다. 저는 아무 생각 없이 문제를 풀다가 시간 초과 크리가 뜨고 말았습니다😭. 아무래도 피보나치 함수를 냅다 문제로 냈을 리는 없을 텐데 말입니다. 제가 너무 순진하게 생각했죠ㅎㅎ. 다시 시간 제한을 보니 주어진 시간이 고작 0.25초 밖에 되질 않습니다. 보통 1-2초로 주어진다는 것을 생각하면 매우 짧은 시간이죠. 어떤 방식으로 풀어야 할 것 같으신가요? 피보나치 함수에 시간을 단축한다면? 네, 맞습니다. 다이내믹 프로그래밍을 응용한 문제입니다. 우리는 다이나.. 2022. 6. 16. 04:33
[방학의 PS] DFS와 BFS - BOJ_2606 어제 살짝 예고 드렸듯이 오늘은 DFS와 BFS의 구현에 대해 심층적으로 분석해보고자 합니다. 이 글은 자료구조와 알고리즘을 개략적으로나마 훑어보신 분들을 대상으로 한 글이기 때문에 DFS가 뭐고 BFS가 무엇인지에 대한 설명은 생략하도록 하겠습니다. 그럼 이제부터 본격적으로 다음과 같은 단계에 따라 DFS와 BFS를 구현해보도록 하겠습니다. 1단계 그래프 생성 2단계 DFS와 BFS의 공통점에 대해서 생각 3단계 DFS와 BFS를 각각 구현 1. 그래프 생성 당연하지만 그래프부터 생성해야 합니다. 당연하지만 그래프는 문제에서 주어지는 방식, 프로그램이 요구하는 방식에 따라 생성하는 방법이 천차만별이긴 합니다. 저는 아래와 같은 방식으로 구현했습니다만 사실 별로 중요한 코드는 아니라고 봅니다. # n은 .. 2022. 6. 15. 06:51
[방학의 PS] set, deque, 리스트의 참조 복사 오늘은 원래 DFS와 BFS를 공부하고자 하였으나, 몇 가지 추가적인 공부가 필요하여 이를 보충하도록 하겠습니다. 1. set set은 파이썬의 데이터 타입입니다. 딕셔너리나 리스트와 같이 말입니다. 이는 수학에서 집합과 매우 유사한 특징을 지니는데, 우선 다음과 같이 선언 및 정의하게 됩니다. s1 = set([1, 2, 3, 3]) # [1, 2, 3, 3]이라는 리스트를 set 자료형으로 바꿔 s1에 저장한다는 의미입니다. s1 >> {1, 2, 3} set의 중요한 특징은 다음과 같습니다. 중복을 허용하지 않는다. 순서가 존재하지 않는다. 위의 코드에서 보신 것처럼 set은 중복을 허용하지 않습니다. 또한 순서가 존재하지 않는데, 이는 인덱스로 접근할 수 없다는 것을 의미합니다. 예를 들면 s1 .. 2022. 6. 15. 06:35
[방학의 PS] 다이나믹 프로그래밍(DP) - BOJ_1463 오늘은 새로운 알고리즘에 대해서 이야기해 보겠습니다. 바로 다이나믹 프로그래밍이라고 불리는 알고리즘입니다. 혹시 처음 들어 보신 분이 계시다면, 이름이 생소하고 고급져서 왠지 어렵게 느껴지실 수도 있을 것 같습니다. 그러나 걱정할 것 없습니다. 사실 다이나믹 프로그래밍(이하 dp)이라는 이름은 알고리즘의 개발자가 펀딩을 따내기 위해 일부러 있어 보이게 작명한 네이밍이거든요ㅎㅎ. 실상은 아주 단순한 알고리즘을 의미합니다. dp의 핵심은 문제를 반복되는 단계로 쪼개어 앞선 단계의 값을 뒤의 단계에서 활용한다는 것입니다. 이 말의 의미를 피보나치 수열을 예로 들어 자세히 알아보겠습니다. 우리가 코딩을 통해 피보나치 수열의 n번째 수를 구하는 경우, 다음과 같이 재귀를 주로 활용합니다. def fib(n): i.. 2022. 6. 15. 06:17
[방학의 PS] 균형잡힌 세상 - BOJ_4949 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 오늘의 문제는 자료구조 알고리즘 시간에도 한 번 다루었던 스택에 관한 문제입니다. 대표 유형인 괄호 문제이죠. 스택의 핵심은 모두 아시다시피 FILO(First In, Last Out)입니다. 그 부분을 집중해서 읽어보시면 여태까지 제가 올린 문제 중에서는 가장 수월하게 해결하실 수 있으실 것 같습니다. 정답 코드는 다음과 같습니다. brackets = ['(', ')', '.. 2022. 6. 15. 06:08
[방학의 PS] 프린터 큐 - BOJ_1966 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 큐 문제인 듯 큐 문제 같지 않은 문제입니다. 저는 처음에 우선순위 큐 문제로 내용을 착각하고 이를 통해 구현해보려다 삽을 좀 푼 뒤, 근본적인 구현으로 다시 돌아갔습니다. 덕분에 시간을 너무 많이 허비했네요ㅠㅠ 큐의 핵심은 FIFO(First In, First Out)입니다만, 이것만으로는 풀기 어려운 문제였습니다. 문제에서 주어지는 논리를 만족하는 자료구조를 생각한 뒤, 어떻게 하면 중복되는 요소.. 2022. 6. 15. 06:04
[방학의 PS] 이분 탐색과 매개 변수 탐색 - BOJ_2805, BOJ_1654 자료구조 및 알고리즘을 간략하게나마 공부했던 학생들을 대상으로 한 review 및 관련 문제 풀이 형식의 글입니다.😊 1. Binary Search 이분 탐색 또는 이진 탐색은 이미 정렬된 배열에서만 사용할 수 있는 탐색 알고리즘입니다. 우리가 찾으려는 원소를 target이라고 합시다. 그리고 탐색 대상이 되는 배열의 시작을 start, 끝을 end, 가운데에 위치한 원소를 mid라고 합시다. target mid 일 경우, 탐색 대상이 되는 배열을 mid부터 end까지 축소합니다. 즉 start = mid가 됩니다. 이렇게 절반씩 뚝뚝 끊어서 탐색하기 때문에 시간 복잡도는 .. 2022. 6. 15. 05:52

티스토리툴바