본문 바로가기

전체 글

[c++][백준 13023][DFS] ABCDE - 컴도리돌이 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 과정 - 모든 노드들은 ABCDE 친구 관계가 성립하는지 그래프 탐색을 한다. - 방문한적이 없는 노드는 해당 DFS로 탐색하고 깊이를 1 증가 시킨다. 깊이가 총 5번이면 관계가 성립 되었기에 ans 값을 true로 설정하고 return 해준다. - dfs로 탐색이 끝났는데 ans 값이 false 면 해당 탐색했던 노드는 다시 방문 표시를 false로 설정한다. #include #include #include using namespace std; int n,m; map friends; vector visited; bool ans = false; void dfs(.. 더보기
[c++][백준 9663][BFS] N-Queen - 컴도리돌이 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 과정 - 퀸은 가로, 세로, 대각선으로 나아갈 수 있는 말이다. 즉, 퀸 하나를 놓으면, 그 퀸과 같은 가로, 세로, 대각선에는 또 다른 퀸을 놓을 수 없다. - 해당 문제는 dfs의 재귀 호출로 해결하였으며, 2차원 배열과 1차원 배열 두 가지로 해결을 하였다. 1차원 배열을 사용하는 게 미숙하여 다른 블로거님들의 풀이를 보면서 이해하면 문제를 풀었고 혼자 풀 때는 1차원 배열을 풀어야겠다는 생각을 못하여 2차원 배열로 해결하였다. - 0번째 행부터 각 행에 대해 각각 .. 더보기
[c++][백준 15686][prev_permutaion] 치킨 배달 - 컴도리돌이 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net * 풀이 과정 1. 치킨 집 수에서 최대 M개를 선택해야 하기 때문에 본 문제는 순열 문제로 인식. prev_permutaion으로 문제를 해결하였다. 2. 초기 치킨집의 개수로 순열을 돌려서 시간 초과가 발생하였다. ->해결 방안) combination이라는 치킨 집의 개수정도의 크기로 할당한 배열을 생성하여 인덱스가 0부터 m까지 true로 설정하였다. 치킨집을 순열로 돌리지 않고 combination 배열을 순열로 돌려 해당 값이 fal.. 더보기
[c++][백준 2146][BFS] 다리 만들기 - 컴도리돌이 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net * 풀이 과정 1. 육지와 육지 사이의 구분이 필요하기 때문에 육지마다 번호를 표시하였다.(처음 육지를 1로 입력받는 것을 -1로 입력받았다.) 2. 육지와 육지 사이의 다리를 놓는다. 1) 번호에 따른 육지의 x, y 값들을 queue에 넣고 방문 표시를 한다. 2) 다른 육지 번호가 나오면 다리의 값을 return 한다. 3) 바다가 나오면 queue에 넣고 다리가 설치했다고 가정을 하고 bridge 값도 +1을 시켜서 queue에 넣는다. 해당 좌표는 방문 표시.. 더보기
[딥러닝] CNN(Convolutional Neural Networks) - 컴도리돌이 outline motivation convolution operator(2 - dimention) convolution operator(3 - dimention) max/mean pooling operator convolutional neural networks structure of convolutional neural network motivation DNN은 기본적으로 1차원 형태의 데이터를 사용한다. 그렇기 때문에 이미지가 입력 값이 되는 경우, 이것을 flatten 시켜서 one hat-encoding으로 데이터로 만들어야 하는데 이 과정에서 이미지의 공간적/ 지역적 정보가 손실되게 된다. 추가로 추상화 과정 없이 바로 연산 과정으로 넘어가 버리기 때문에 학습시간과 능률의 효율성이 저하된다. 물.. 더보기
[딥러닝] Neural Network : FashoinMNIST Classifier - 컴도리돌이 텐서플로우로 시작하는 딥러닝 기초 부스트코스 무료 강의 www.boostcourse.org Package Load import os import time import numpy as np import matplotlib.pyplot as plt %matplotlib inline import tensorflow as tf from tensorflow.keras import layers numpy: Scientific computing과 관련된 여러 편리한 기능들을 제공해주는 라이브러리. matplotlib.pyplot: 데이터 시각화 tensorflow: Tensor Flow를 로드. tensorflow.keras.layers: 모델의 각 Layer들을 만들기 위해 사용. 하이퍼파라미터 세팅 학습에 필요한.. 더보기
[딥러닝] NN(Neural Network) - Activation function - Sigmoid - Perceptron - Single Layer Perceptron - Multiple Layer Perceptron - 컴도리돌이 outline Feedforward Neural network Feedforward Backpropagation 순방향 신경망(Feedforward Neural network) FFNN(Feed Forward Neural Network)는 입력에 대한 출력 값을 가장 잘 예측하는 가중치(weights)를 찾는 것이다. 그렇게 하기 위해서는 학습 데이터를 이용하여 출력을 구하고, 출력에 대한 에러를 구한 후 에러가 줄어드는 방향을 찾아 업데이트 해주는 과정을 반복하여 가중치를 찾는다. 위에 그림을 보면 입력 값(x1,x2,...xn)은 가중치(weight)에 의해 가중되고 더해진 뒤 bais가 더해진 후 활성화 함수(activation function)를 거쳐 출력된다. 이후 출력되는 출력 값과 실제 값을.. 더보기
[프로그래머스][level2][C++][BFS] 찾아라 프로그래밍 마에스터 - 게임 맵 최단거리 - 컴도리돌이 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr N * M 행렬에서 최단 거리를 보장해주는 탐색 알고리즘인 BFS를 사용하였다. 단순히 N*M의 범위를 넘지 않고 벽이 아닌 곧이 있을 경우 해당 값을 큐에 삽입 후 좌표의 값을 1 증가시켰다. 최종적으로 반환 값은 N*M 좌표의 값을 반환시켰다. 하지만 해당 값이 1인 경우 모든 벽에 둘러 쌓여서 탐색을 하지 못한 경우이기에 -1 값을 반환하도록 설정하였다. #include #include using na.. 더보기
728x90

티스토리툴바