전체 글

[Algorithm] C++ DFS & BFS 이해 및 구현

DFS : Depth First Search (깊이 우선 탐색) 이동할 수 있는 모든 노드를 이동하다가 더이상 이동할 수 없으면 뒤로 다시 돌아와 탐색 스택이나 재귀함수로 구현가능 노드 방문 시, 해당 노드의 방문 여부를 체크해야만 한다. (isVisited) DFS로 구현한 경로가 최단 경로인지 확인은 불가능하다. DFS의 시간복잡도 DFS(idx)는 해당되는 idx에 방문하는 함수이다. 그렇기에 해당 트리의 차수만큼 함수가 호출된다. 즉 DFS는 시간복잡도 * 차수가 DFS 알고리즘의 시간복잡도이다. 하지만 구현 방법에 따라 시간복잡도가 달라지며, 재귀함수로 구현하였을 경우 별도의 자료구조를 필요로 하지않기에 메모리를 아낄 수가 있다. 아래는 DFS의 진행되는 이미지이다. Code ( C++ ) - ..

[백준 / BOJ] C++ 1003 피보나치 함수

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 아~~ 주 쉽게 생각했다가 짜증만 엄청 냈던 문제.. 시간초과를 생각못하고 어떻게 풀던 시간초과가 나오고, 계속 '이렇게해서 안되면 어쩌란거야 ?'를 반복하다가 찾아보니 점화식을 이용하는 문제였다. 이럴거면 피보나치 위에 그 함수코드는 왜있었는지 이해불가.. 아무튼 피보나치 함수의 점화식은 아래와 같다. N이 0일때, return값이 0인경우 = 1, 1인경우 = 0 N이 1일때, return값이 0인경우 = 0, 1인경우 = 1 N이 2일때, return값이 0인경우 = 1, 1인..

[백준 / BOJ] C++ 2448 별찍기 - 11

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 풀이 이것저것 해보다가 결국 끼워맞추기를 시작한 문제.. 반복되는 문양을 vector 배열에 넣어준다. 이후에는 코드에서 알 수 있듯.. 끼워맞춰서 출력만 되도록하였다. 이해를 돕기위해 아래 이미지를 참조하자. 반복되기 이전 공백이 3개씩 들어가며, 그 공백의 갯수는 2^n개로 알 수가 있다. 입력값이 3 * 2^k 이기 때문에 유추할 수 있다. 앞에 공백 " "을 채워주고 별 그린 이후 이후 공백 " "을 채워준다. 아래 코드를 참조하자. Code..

[백준 / BOJ] C++ 2407 조합

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 풀이 조합 공식을 이용 - (nCm = n-1Cm-1 + n-1Cm)을 이용하여 값을 구한다. long long을 사용해도 자료형 허용 범위를 넘어가는 미친 문제이다. 조합 공식쓰고 그냥 했다가 왜 안되지? 하며 꽤나 헤매었던 문제... Visual studio 2022 C++ 17 개발환경으로 long long으로 빌드하거나 디버깅하면 문제없이 다 출력이 된다. 그래서 오히려 헤메었다.. python에서는 자바의 Biginteger가 백그라운드에서 자동 지원이라서 string으로 구현하지않아도 문제없이 실행이 ..

[Tensorflow / Deep learning] 은닉층 (Hidden Layers)

은닉층 (Hidden Layer) 이란? 은닉층은 입력층과 출력층 사이의 모든 층을 말한다. 은닉층은 모든 입력노드들로부터 입력값을 받아 가중합을 계산하고, 이 값을 전이함수에 적용하여 출력층에 전달하도록 되어있다. 모든 입력노드와 은닉노드들은 가중치를 가지고 있는 망으로 연결되어있고, 은닉노드와 출력노드 역시 마찬가지이다. 아래이미지를 확인해보자. 위의 그림을 기준으로 표현할때는 3개의 층을 그리지만, 실제로 인경신경망의 총 개수를 셀 때는 입력층을 생략한다. 따라서 위 구조에서는 2개의 층이 존재한다고 부른다. 퍼셉트론을 기본 빌딩 블록으로 하여, 이런 패턴에 따라 2차원적으로 연결되어 구성되는 인공신경망의 일종을 특별히 다층 퍼셉트론(MLP: multi-layer perceptron)이라고 한다. ..

[Machine learning] One-hot encoding와 Softmax Regression, Cross-entropy란?

소프트맥스 회귀 (Softmax Regrssion) 란? 소프트맥스 회귀는 다중 분류에 대한 회귀이다. 사실상 일반적으로 회귀는 bool문과 같이 0 또는 1, true 또는 false 식으로 상반되는 값을 분류하는데 사용된다. 하지만 소프트맥스 회귀를 하게 될경우 분류할때 이중적 분류가 아닌 2개 이상의 분류를 하는데 사용될 수 있다. 대표적인 예로 아이리스 품종 분류가 있다. 위의 이미지에서 종속변수의 총 갯수는 3가지이다. ('setosa', 'versicolor', 'virginica') 하지만 예를 들어 첫번째 행의 독립변수로 미뤄 보았을때, 확률이 아래와 같다면? Setosa 0.6 virginica 0.5 versicolor 0.4 이 경우 3가지의 결과 값의 합이 1을 초과하게된다. 간단하..

[Tensorflow / Deep learning] 아이리스 품종 분류

아이리스 품종 분류 예제를 풀어보기 전 머신러닝에 대해 간단하게 알아보자. 머신러닝은 크게 3가지로 분류가 된다. 강화학습 지도학습 비지도학습 우선 우리가 예제를 풀었던 보스턴 집값 예측이나, 레모네이드 값 예측과 같이 딥러닝 및 AI라고 불리는 것들은 전부 지도학습에 속한다. 여기서 지도학습의 분류와 회귀의 개념에 대해 정말 간단하게 알아보자. 회귀와 분류를 간단하게 설명을 하자면, 회귀( regression )는 종속변수가 숫자인 경우를 뜻하고, 분류( classification )는 종속변수가 숫자가 아닌 경우를 뜻한다. 보스턴 집값 예측과 레모네이드 값 예측은 종속변수가 숫자라서 회귀 알고리즘을 사용하였고, 아이리스 품종 예측은 종속변수가 글자라서 분류 알고리즘을 사용할 예정이다. 자 그럼 과거의..

[Tensorflow / Deep learning] 보스턴 집값 예측

전 포스팅은 간단한 하나의 독립변수로 모델을 만드는 예제를 해보았다. 이번엔 독립변수가 여러개일 경우 모델을 만들어 예측을 하는 방법을 알아보겠다. 아래 이미지는 1978년도 보스턴주의 506개 동네의 집값을 보여주는 표이다. 해당 표에서의 첫번째 행에서 1 ~ 13번 열 까지는 도시를 나타내는 독립변수이다. 마지막 14번째 열은 집값을 해당 도시의 집값의 중앙값을 보여준다. 그럼 왼쪽의 공식은? 이 독립변수들이 어떻게 종속변수에 영향을 미치는지를 보여준다. 위의 공식을 적용하여 여러 행들 중, 하나를 선택하여 적용해보자. 그 예시가 아래 이미지와 같다. 이와 같이 각각의 독립변수들은 모두 종속변수에 영향을 준다. 그렇다면 딥러닝의 조건 4가지를 위의 데이터를 대입하여 정리해보자. 독립변수는 1 ~ 13..