외쳐갓우찬

2021. 2. 7. 14:10 ⏰ 코딩테스트/백준 알고리즘

문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다. 접근법 DP의 대표 유형중 하나인 타일 문제이다. 먼저 벽을 1x2, 2x1 크기의 타일로 채워야 하므로 3xN의 N이 홀수이면 벽을 타일로 채울 수가 없다. 타일은 짝수 개이기 때문이다. 따라서 N이 홀수이면 경우의 수는 0 이다. N이 2인 경우 총 3가지가 존재한다. f(2) = 3 N이 4인 경우 총 11가지가 존재한다. f(4) = f(2)xf(2) + 2 = 11 N이 6인 경우의 수도 마찬가지로 증가한다. N이 2인 경우의 수를 N이 4인 경우의 수만큼 11번 ..

백준 알고리즘 - 4344 - 평균은 넘겠지

2021. 2. 4. 11:10 ⏰ 코딩테스트/백준 알고리즘

문제 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. 입력 첫째 줄에는 테스트 케이스의 개수 C가 주어진다. 둘째 줄부터 각 테스트 케이스마다 학생의 수 N(1 ≤ N ≤ 1000, N은 정수)이 첫 수로 주어지고, 이어서 N명의 점수가 주어진다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 출력 각 케이스마다 한 줄씩 평균을 넘는 학생들의 비율을 반올림하여 소수점 셋째 자리까지 출력한다. 접근법 테스트 케이스의 개수 입력 받기 이중리스트로 학생 수, 점수 입력 받기 평균 점수를 구한다. 평균 점수보다 높은 학생 수를 구한다. 평균 점수보다 높은 학생 수의 비율을 구한다. 소수점 셋째자리 반올림하여 출력한다. 코드 n = ..

백준 알고리즘 - 2792 - 벌집

2021. 2. 3. 10:50 ⏰ 코딩테스트/백준 알고리즘

문제 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다. 입력 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다. 출력 입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다. 접근법 수학 파트인 만큼 수학적으로 어떻게 접근하는지가 중요한 문제이다. 1을 중심으로 층별로 개수가 6, 12, 18, 24 개씩 벌집..

임베딩이란?

2021. 2. 2. 17:50 📌 Paper/Deep learning to identify ORI

컴퓨터가 문자를 해석하는 방법 위와 같이 문자는 컴퓨터가 해석할 때 그냥 기호일 뿐이다. 이렇게 encoding된 상태로 보게 되면 위와 같은 문제점이 발생할 수 있다. 이 글자가 어떤 글자인지를 표시할 수 있고 그에 따른 특성을 갖게 하려면 우선 계산할 수 있게 숫자로 만들어 주어야 할 것이다. 그러한 방법 중 가장 단순한 방법이 One-hot encoding을 통한 것이다. 허나, 이러한 Sparse matrix를 통한 계산은 너무 비효율적이다. 그렇다면 어떻게 dense하게 표현할 수 있을지를 고민하는 것이 바로 Embedding이라는 개념의 본질일 것이다. 임베딩(Embedding)이란? 자연어 처리(Natural Language Processing)분야에서 임베딩(Embedding)은 사람이 쓰..

백준 알고리즘 - 8958 - OX 퀴즈

2021. 2. 2. 09:24 ⏰ 코딩테스트/백준 알고리즘

문제 "OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수는 3이 된다. "OOXXOXXOOO"의 점수는 1+2+0+0+1+0+0+1+2+3 = 10점이다. OX퀴즈의 결과가 주어졌을 때, 점수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 0보다 크고 80보다 작은 문자열이 주어진다. 문자열은 O와 X만으로 이루어져 있다. 출력 각 테스트 케이스마다 점수를 출력한다. 접근법 테스트 케이스 개수 입력 테스트 케이스 한줄씩 입력 한줄씩 OX 검사하기 X 라면 ..

Docker 에서 CentOS7 설치 및 IGV 설치 및 실행

2021. 2. 1. 20:35 📌 Internship/BIG Lab

docker pull centos docker run -it centos /bin/bash yum을 이용한 sudo 설치 yum install -y sudo apt 설치 설치 확인 rpm -qa | grep apt apt-get >> 설치 되지 않음 yum list apt yum repo에도 없음 rpm -qa | grep rpmforge-release yum repolist Mac OS jdk 설치하기 그다음 IGV 더블클릭

IGV (Integrative Genomics Viewer)

2021. 2. 1. 18:42 🧬 Bio/생명정보학

IGV (Integrative Genomics Viewer) IGV는 통합적인 유전체 데이터셋 등을 보여주는 고성능 시각과 도구이다. 어레이데이터나 NGS 데이터 등 다양한 타입의 데이터를 지원한다. IGV ? High-performance genomics data vidualization and exploration. 통합적인 유전체 데이터셋을 시각화해주는 그래픽 기반 프로그램 다양한 유전체 관련 정보를 여러가지 트랙을 통하여 보여줌 다양한 포맷의 데이터 로드할 수 있어 편리함 (array-based, NGS, annotation data) Annotation 결과를 그림과 그래프 형태로 제공해주고 Annotation 정보가 추가된 VCF 파일을 생성해줌 IGV interface IGV 메뉴 설명 IG..

Back-Propagation 의 Chain Rule

2021. 2. 1. 15:26 💡 AI/DL

Back propagation 의 가장 핵심적인 미분 계산을 수식적으로 자세히 뜯어보고 이해해보자. 합성함수로서의 DNN 입력, 함수모델, 정답은 fix되어있다. Activation function, loss function도 이미 정의가 되어있는 상태이다. 변할 수 있는건 Trainable parameter와 손실값(L) 밖에 없다. 그렇기 때문에 n번째 함수 fn은 n-1번째 데이터셋 값을 입력 받아서 Wn, bn 파라미터가 조건부로 들어가게 된다. 다 넣었으면 이제 데이터 셋의 입력과 출력 값은 중요하지 않게 된다. 손실을 최소화하는 파라미터만 찾으면 되기 때문이다. DNN의 Chain Rule Fully Connected Layer의 미분 Sigmoid 함수의 미분 Back Propagation ..

Chain Rule

2021. 2. 1. 15:20 💡 AI/DL

Chain Rule 간단히 개념만 알고 넘어갔던 연쇄 법칙을 수식으로 이해해 보자. 직렬 연결된 두 함수의 미분 Chain Rule의 확장 모두 곱한다. 동적 계획법으로 저장해 놓고 계속 미분하며 곱할 수 있다.

DNN의 수학적 이해

2021. 2. 1. 15:17 💡 AI/DL

뉴런은 여러개의 입력을 받아 가중치를 곱해서 합해주고 non linear activation function을 이용해서 출력을 해주는 가장 기본적인 단위이다. 전결합 계층 (Fully Connected Layer) 모든 뉴런들을 연결한 Layer가 Fully connectecd layer이다. 간단한 matrix의 곱으로 표현할 수 있다. 볼드체(x, b, y)는 벡터이고 W는 벡터이다. DNN 블랙 박스 모델 (Black Box Model) 손실을 최소화 하는 방향으로 학습한다. 어떤 블랙박스 모델이 있고 trainable parameter가 4개라고 해보자. 블랙 박스 모델의 학습 수치적 기울기 (Numerical Gradient) 에타값이 충분히 작다면 수치적 기울기를 미분값으로 사용할 수 있다. ..

Deep Neural Network - Back Propagation

2021. 2. 1. 15:08 💡 AI/DL

Shallow Neural Network 에 이어서 Deep Neural Network에 대해서 배워보자. 뉴런 입력이 들어왔을 때 가중치와 bias를 곱해주고 Summation 한 다음 Activation function을 이용해서 Nonlinear 연산으로 출력을 하는게 뉴런이다. Shallow Neural Network Hidden layer 에서는 dense layer(=fully connected layer)를 통해 계산한다. 보통 SNN의 Hidden layer에서는 Sigmoid를 이용한다. Output layer의 경우에서 사용되는 activation function은 linear 또는 softmax를 이용한다. softmax를 이용하면 확률로 나오면서 classification에 이용된다..

용어 정리

2021. 2. 1. 12:58 📌 WorkOut

API “API(Application Programming Interface, 응용 프로그램 프로그래밍 인터페이스)는 응용 프로그램에서 사용할 수 있도록, 운영 체제나 프로그래밍 언어가 제공하는 기능을 제어할 수 있게 만든 인터페이스를 뜻한다.” API란 간단하게 이해하면 “내가 만든 프로그램이 개인 개발자, 기업, 기관이 제공하는 기능, 프로그램 등을 활용할 수 있게끔 도와주는 중간 매개체” 라는 것이며, 공공API 같은 유용한 무료 API도 존재한다. Keras 케라스(Keras)는 주요 고수준 신경망 API 가운데 하나로, 파이썬(Python)으로 작성됐으며 여러 백엔드 신경망 엔진을 지원한다. 케라스는 엄밀히 말해 텐서 곱(tensor products), 합성곱(convolutions)과 같은 저..

백준 알고리즘 - 1932 - 정수삼각형

2021. 2. 1. 11:18 ⏰ 코딩테스트/백준 알고리즘

문제 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다. 접근법 DP 문제이다. DP 문제의 조건은 1) 작은 문제가 반..

백준 알고리즘 - 11725 - 트리의 부모 찾기

2021. 1. 31. 17:56 ⏰ 코딩테스트/백준 알고리즘

문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 접근법 예제 입력을 보면 첫번째 줄에 전체 노드의 개수와 두번째 줄부터 시작해서 연결된 두개의 노드가 주어진다. 그 두개의 노드 중 하나는 부모노드이고 하나는 자식노드이다. 여러가지 두개의 노드가 주어지지만 둘 중 어느 노드가 부모인지 아는 방법은 주어진 두개의 노드 중에 중복된 노드가 나온다면 그 노드는 부모노드이다. 자식 노드가 두개의 부..

티스토리툴바