1. 문제 출처 https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 2. 풀이 문자열을 이용한 단순 구현 문제이다.. # 크로아티아 문자 리스트 3글자인 것을 빼었다. cro_list =\ ["c=", "c-", "d-", "lj", "nj", "s=", "z="] # 입력 string = input() length = len(string) total_count = length idx = 0 # index가 l..
1. 문제 출처 https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 풀이 내림차순으로 정렬되어 있는 부분 최장 길이의 부분 수열을 구하는 문제이다..이는 LIS를 구하는 알고리즘과 매우 유사하다..이제 코드를 보자.. n = int(input()) soldier_list = list(map(int,input().split())) # LIS (최장 증가 부분 수열) 처럼 사용하기 위해 오름차순으로 변환 해준다. soldier_list..
1. 문제 출처 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 2. 풀이 모든 위치에서의 최대값을 구한다.. 이를 매번 처음부터 구하면 매우 오래 걸리므로 Dynamic Programming (동적 프로그래밍)을 사용한다..아래는 Botton_Top 형식으로 구현하였다. # 입력 n = int(input()) # 정수 삼각형 입력 tri = [[0]*idx for idx in range(1,n+1)] for idx in range(n): tri[idx] = list(map(int,input().split())) #..
1. 문제 출처 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2. 풀이 모든 지점에서 다른 모든 지점까지의 최단경로를 계산하는 문제이다.. 딱 플로이드 워셜(이름부터 플로이드 이다...)을 위한 문제이다. 플로이드 워셜의 점화식을 이용하였다. Dab = min(Dab , Dak +Dka) 이를 코드로 표현하면 다음과 같다. for k in range(n): for a in range(n): for b in range(n): D[a][b] =..
1. 문제 출처 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 풀이 가장 작은 두 카드 묶음 값을 더하는 것이 최적의 해이다. 일단은 다음과 같이 구현하였다. 하지만 시간 초과이다... 그래서 heap자료구조를 사용하여 시간을 줄였다... #입력 n = int(input()) cards = [] for _ in range(n): cards.append(int(input())) # 정렬 cards.sort() total_co..
1. 문제 출처 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 2. 풀이 연구소 문제와 비슷한 점이 있다. 연합하고 인구를 이동 시켜주는 작업을 BFS를 사용하여 구현하고 연합체의 개수가 전체 데이터의 수와 같으면 반복 했던 횟수를 반환한다... from collections import deque # 입력 N,L,R = map(int, input().split()) A = [] for _ in range(N): A.append..
1. 문제 출처 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 2. 풀이 일단 문제 대로 eval을 사용하여 구현해 보았다.. 특정 부분에서 잘못 계산되는 것 같다...반례를 찾을 수 없어서 DFS로 다시 구현하였다.(반례 찾으시면 말해주시면 감사하겠습니다.) from itertools import permutations # 입력 N = int(input()) num_list = list..
머신러닝의 학습 방법 3가지를 알아보자!! 1. 비지도 학습(Unsupervised Learning) 답(Label 또는 Target)이 주어지지 않은 데이터셋 만으로 학습시키는 방법 Clustering(군집화), Dimension Reduction(차원 축소)등이 존재한다. 2. 지도 학습 (Supervised Learning) 답(Label 또는 Target)이 주어진 데이터 셋을 이용하여 학습시키는 방법 Classification(분류), Regression(회귀)등이 존재한다. 3. 강화 학습 ( Rainforced Learning) 답이 따로 정해지지 않았지만 한 행동에 대한 보상(reward) 과 손실(penalty) 을 받으며 학습시키는 방법 보상을 최대화 하는 방향으로 학습을 한다.
