Python
인공신경망 직접구현
이번에는 인공신경망을 low레벨에서 직접구현 해보았다. 만약에 AND게이트를 구현한다고 생각해보자. 우리는 퍼셉트론이라는 개념을 알아야 한다. class perceptron_for_GATE: #GATE만들기위한 퍼셉트론 def __init__(self,w): self.w = w def output(self,x): tmp = np.dot(self.w,np.append(1,x)) result = 1.0*(tmp>0) return result 퍼셉트론은 위와같은 구조로 만들 수 있다. w_and = np.array([-1.2,1,1]) #AND GATE and_gate = perceptron_for_GATE(w_and) w_or = np.array([-0.8,1,1]) # OR GATE or_gate = pe..
2482_색상환
https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net dp를 2차원배열로 설정해서 풀 수 있다. dp[i][j]라면 i개의 색중에서 j개의 색을 선택하는 것이다. dp를 채워나간다고 생각해보자. 만약 dp[i][j]를 채운다고 생각해보자. i번째 색이 새로 추가되었다면 그 색을 칠하는 경우와 안 칠하는 경우 2가지가 나올 것이다. 만약 색이 추가되었다면 i-1번째색은 칠할 수 없고, 이때 색을 칠한다면 j-1개를 구해야 하므로 i-2 개의 색으로 j-1개의 색을 칠하는 경..
11478_서로다른부분문자열의 개수
https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net set을 통해서 중복이 들어갈 수 없게 한 후, 이어지는 문자열들을 집어넣으면 된다. s = input() result = set() for i in range(len(s)): for j in range(i,len(s)): result.add(s[i:j+1]) print(len(result))
14425_문자열 집합
https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 단순하게 풀 수 있는 문제인데 리스트로 풀면 시간초과가 나는 문제였다... 새롭게 알게된 사실인데 list자료형의 삽입,탐색등의 시간복잡도는 O(n)이며 딕셔너리 set의 자료형은 O(1)이라서 많은 차이가 난다고 한다. 이를 잘 생각하고 풀어보는것도 괜찮은 것 같다. import sys input = sys.stdin.readline n,m = map(int,in..
17404_RGB거리2
https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net RGB거리 문제와 동일하지만 첫번째 집과 마지막집이 연결된 형태이다. 첫집과 마지막집의 색이 같아야 하지 않으므로 세 경우를 집어서 생각할 수 있다. 첫집을 R로 칠하고 dp를 채워나가 cost를 만든 것중 마지막집을 G,B로 칠한것중 최소비용 첫집을 G로 칠하고 dp를 채워나가 cost를 만든 것중 마지막집을 R,B로 칠한것중 최소비용 첫집을 B로 칠하고 dp를 채워..
2098_외판원순회 1
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 해당문제를 풀기 위해선 비트마스크, dp , dfs 총 3가지의 알고리즘을 활용해서 풀 수 있다. 처음에 비트마스크와 dp만 가지고 풀어보려다가 많이 헤맸던 문제이다.. 먼저 dp는 2차원 dp로 선언을 한 후 dp[i][j]라면 i는 현재 도시의 위치, j는 현재까지 방문한 도시들을 기록한다. 이때 j를 비트마스크를 이용해서 기록한다. 즉, 현재 도시가 3이..