본문 바로가기

분류 전체보기

 (64)
[백준] 9663 "N-Queen" -python 알고리즘 대각선에 퀸이 존재하는지 여부를 체크하는 배열 2개와 같은 행에 퀸이 존재하는지 여부를 따지는 배열 1개를 두고 백트래킹을 실행한다. 종료조건은 행을 1번씩 늘리면서 행번호가 입력 N과 같은 경우이다. 소스코드 import sys N = int(sys.stdin.readline()) result = 0 isused1 = [0] * N isused2 = [0] * (N * 2) isused3 = [0] * (N * 2) def func(k): global result if k == N: result += 1 return for i in range(0, N): if isused1[i] or isused2[k+i] or isused3[k-i+N-1]: continue isused1[i] = 1 isu..
[백준] 15651 "N과 M (3)" -python 알고리즘 백트래킹을 통해 모든 중복가능한 조합을 찾아 출력한다. 소스코드 # N과 M (3) import sys n, m = map(int, sys.stdin.readline().split()) arr = [0] * m def func(k): if k == m: for i in arr: print(i, end=" ") print() return for i in range(1, n+1): arr[k] = i func(k+1) func(0) 참고 : https://blog.encrypted.gg/945
[백준] 15560 "N과 M (2)" -python 알고리즘 백트래킹을 통해 구현한다. 소스 코드 # N과 M 2 import sys n, m = map(int, sys.stdin.readline().split()) arr = [0] * m # 수열 저장 isused = [False] * (n + 1) s = set() def func(k): if k == m: s.add(tuple(sorted(arr))) return for i in range(1, n + 1): if not isused[i]: arr[k] = i isused[i] = True func(k+1) isused[i] = False func(0) for i in sorted(list(s)): print(*i) 참고 : https://blog.encrypted.gg/945
[백준] 1339 "단어 수학" -python https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 알고리즘 입력으로 주어진 모든 단어의 알파벳에 대해 자릿수를 구하고 그 합을 구한다. 예를 들어, 단어 ABCDA에서 A의 자릿수는 10001 ( A 관점에서 각 자리수에 A가 있는 부분에 1 아니면 0 ) 모든 알파벳에 대하여 자릿수를 구한 뒤 더해서 저장해 둔다. 모든 단어에서 하나의 알파벳 관점으로 볼 때 최적해를 구하는 그리디 알고리즘이다. # 단어수학 import sys, colle..
12. Dimensionality Reduction 목표 : feature의 개수를 효율적으로 줄이자 방법 : feature select, feature extraction 1. feature selection ㅁ exhaustive search ( 전수조사 ) 모든 조합 다 고려해서 넣어보고 제일 좋은 특성집합 선택, NP-complite ㅁ Heuristic ( 하면서 찾아내기 ) -forwoad search : 특성 하나씩 그리디하게 추가하면서 찾기 -backward search : 특성 하나씩 그리디하게 빼면서 찾기 -stepwise search : 평가기준에 따라 한개씩 넣고 만족못할시 -> 하나씩 기준에 따라 뺌 -> 반복하다가 추가, 삭제 기준 둘 다 충족 못할 때까지 반복 평가기준 : AIC, BIC ㅁ meta heuristic ( 휴리스..
11. Kerner Method ERM ( Empirical risk min ) SRM (Structural risk minimization) 마진을 둬서 마진 최대가 되게 하자! 해서 두 선형식의 차이가 최대가 되도록 hard margin: 모든 데이터가 위에 식 만족 위 식을 만족하더라 convex에 의해 어차피 a = 0 인경우는 바운더리 결정x, 즉, 결정은 뒤에 식이 Soft Margin SVM 마진은 키우고 앱샐론은 줄이는 방향으로 가야함 하지만 소프트 마진도 여전히 리니어임 차원 낮으면 논리니어인데 차원 높으면 리니어인 경우 생각 -> 높은차원에 매핑함수 파이로 가정 파이 대신 커널함수 사용! SVM for 회귀
10. Deep Neural Network 목표: 최적함수가 있다고하면 그거 모방하는거! 퍼셉트론 여러층 쌓아서 성능, 일반화등을 높일 수 있다. vanishing 문제: 시그모이드 쓰면 편미분 계산하면서 초기 가중치 0이됨 -> relu쓰자 오버피팅 해결법 1. 노드 껏다 켯다 2. 필터를 통해 연결 -> sparse connection으로 parmeter sharing 가능 느린 최적화 해결법 1. 모든 로스 구하기가 아닌 부분 배치 로스 구해서 경사하강 ㄱ(stochastic) 2. 누적벡터로 ㄱ ( 잘 가고있으면 가중 ) 3. 가중치에 관성 (이전값 고려) 깊이 = > 히든레이어 수, 학습= 이상적함수 f에 근사 relu단점 : 0인 지점 존재 CNN ( Convolutional ) 최소 하나의 convolution network포함하면 ..
9. Neural Networks 페셉트론 = 인공뉴런 => 다수의 입력에 weighted sum + bias의 값을 activation function에 입력하여 output을 얻는다. 하지만 그냥 퍼셉트론은 non-linear 해결 x -> MLP ( multilayer perceptron )등장 - universal approximation theory 어떤 non-linear문제도 퍼셉트론 여러개로 가능 feedforward vs backpropagation 히든 노드 or layer 많을 수록 capacity 향상 히든 레이어 af의 역할 : nonliner transformation 분류인 경우 output 레이어의 af의 역할 : 원핫인코딩처럼 확률 나눠서 내줌 or softmax(각 결과 확률로) 회귀인 경우 문제에 따라 ..

티스토리툴바