전체 글 (147) 썸네일형 리스트형 [Python] 조합 # 10-1. 조합 알아보기조합(Combination)이란?nCr로 표현하며, n개의 숫자 중에서 r개를 뽑는 경우의 수순열은 nPr로 표현되며, n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 이야기 한다. 조합의 핵심 이론순열 공식 nPr = n!/(n-r)!조합 공식 nCr = n!/(n-r)!r!알고리즘에서 조합을 구현할 때는 위 공식을 코드화하지 않고 점화식을 사용해 표현한다.예를 들어, 5개의 데이터 중 3개를 선택하는 경우는 5개의 데이터 중 4개의 데이터의 선택 여부가 결정된 상태로 가정한다.따라서 5번째 데이터의 선택 여부에 따라 이전 4개의 데이터 중 2개 혹은 3개를 선택하는 경우의 수로 나뉜다.위를 점화식으로 표현하면 D[5][3] = D[4][2]+D[4][3]이 된.. 정기 예금 가입 여부 예측 데이터 다루기 Pattern Recognition Course Project 중 데이터 전처리 과정 정리과제는 주어진 데이터를 활용하여 고객의 신용카드 유무를 예측하는 것이다.# 데이터 확인실제 data set가 아닌 과제용 data set기에 약간 다르다. non-null 데이터만 있는 것 처럼 보이지만 아니다.categorical data에 null data, 즉 결측치는 unknown이라는 label로 있다. # numerical data(수치형 데이터) # categorical data(범주형 데이터) 몇몇 unknown 데이터가 존재한다.딱히 이상치를 보거나 할 게없으니 패스 # 데이터 전처리# 상관관계데이터간 상관관계를 확인한다.상관관계가 높으면(독립 변수 간 선형 상관관계가 있으면) 다중공산성이 있다고.. [Python] 트리 문제 풀이 정리 https://www.acmicpc.net/problem/9934완전 이진 트리 + 중위순회 문제중위순회의 결과를 보고 트리를 만들 수 있어야 한다. 손으로는 풀 수 있는데...코드로는 구현을 못하겠다..# 정답 풀이import sysinput = sys.stdin.readlineK = int(input())tree = [[] for _ in range(K)]p = list(map(int, input().split()))def inOrder(p, depth): # 트리의 root index 찾기 mid = (len(p)//2) # 해당 깊이에 해당하는 node 추가 tree[depth].append(p[mid]) if len(p)==1: return inOrd.. [Python] 그래프 문제 풀이 정리(1) https://www.acmicpc.net/problem/10451# 내 풀이import syssys.setrecursionlimit(2000)T = int(input())def find(a): if a==parent[a]: return a else: parent[a]=find(parent[a]) return parent[a] def union(a,b): a = find(a) b = find(b) if a!=b: parent[b]=afor _ in range(T): N = int(input()) n_list = list(map(int, input().split())) ans = set() parent .. [Python] 트리 # 9-1 트리 알아보기트리란?노드와 에지로 연결된 그래프의 특수한 형태순환 구조(cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재한다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.트리의 부분 트리(subtree) 역시 트리의 모든 특징을 따른다.트리의 핵심 이론(구성 요소)노드 : 데이터의 index와 value를 표현하는 요소에지 : 노드와 노드의 연결 관계를 나타내는 선루트 노드 : 트리에서 가장 상위에 존재하는 노드부모 노드 : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드자식 노드 : 두 노드 사이의 관계에서 하위 노드에 해당하는 노드리프 노드 : 트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)서브 트리 : 전체 트리에 속한 작은 트리 https://www.. [Python] 그래프(2) # 8-5. 벨만-포드벨만-포드(bellman-ford-moore) 알고리즘이란?그래프에서 최단 거리를 구하는 알고리즘특정 출발 노드에서 다른 모든 노드까지의 최단 경로까지의 최단 경로 탐색음수 가중치 에지가 있어도 수행할 수 있으며, 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.시간 복잡도 : O(VE)벨만-포드 핵심 이론에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기에지 리스트는 출발 노드, 종료 노드, 가중치 변수로 구성돼 있다.모든 에지를 확인해 정답 리스트 업데이트 하기업데이트 반복 횟수는 노드 개수 -1이다.모든 에지 E = (s,e,w)에서 D[s]!=max값 이며 D[e]>D[s]+w일 때 D[e]=D[s]+w로 리스트 값을 업데이트 한다.음수 사이클이 없을 때 .. [Python] 그래프(1) # 8-1. 그래프의 표현 2차원 리스트python에서 3행 4열 2차원 리스트를 생성할 때는 두가지 방법이 있다.# 리스트에서 객체를 생성하는 방법A = [[0 for col in range(4) for row in range(3)]# 얕은 복사를 일으켜 생성하는 방법# 이 방식은 선언 후 값을 변경하면 다른 원소의 값도 변경될 수 있다.A = [[0]*4]*3 에지 리스트(edge list)에지를 중심으로 그래프를 표현한다. 리스트에 출발 노드, 도착 노드(+가중치)를 저장하여 에지를 표현한다.구현이 쉽지만 특정 노드와 관련되어 있는 에지를 탐색하기는 어렵다.노드 사이의 최단 거리를 구하는 벨만-포드 혹은 최소 신장 트리를 찾는 크루스칼 알고리즘에 사용한다. 인접 행렬(adjacency matrix).. [Python] 그리디 문제 풀이 정리(2) https://www.acmicpc.net/problem/1339# 정답 풀이from collections import dequeN=int(input())A=[]num={}for _ in range(N): A.append(input())for i in A: # 각 문자열에서 for j in range(len(i)): # 문자열 알파벳 조사 k = 10**(len(i)-j-1) # 알파벳 자릿수 if i[j] in num: # dict에 있으면 더하고 num[i[j]]+=k else: # 없으면 추가 num[i[j]]=ksorted_dict = sorted(num.items(), key = lambda item: ite.. 이전 1 2 3 4 5 ··· 19 다음
