STUDY

가장 긴 증가하는 부분 수열 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다 아무리 생각해도 dp로 풀 수 있는 방법이 생각 나질 않는다... 어떻게 풀어야하는걸까.... 2중 for으로는 뭔가 가능할거 같으면서 힘들고 import sys N = i..

2의 멱수의 합 문제 어떤 자연수 N을 2의 멱수의 합으로 나타내는 경우의 수를 구하는 프로그램을 작성하시오. 2의 멱수라는 것은, 2^k으로 표현되는 자연수를 의미한다. 예를 들어 7을 2의 멱수의 합으로 나타내는 경우의 수는 다음의 여섯 가지가 있다. 1+1+1+1+1+1+1 1+1+1+1+1+2 1+1+1+2+2 1+1+1+4 1+2+2+2 1+2+4 입력 첫째 줄에 N(1≤N≤1,000,000)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. 수학적으로 생각하여 재귀를 통해서 2의 제곱수들로 나누어진 수 만큼 분리를 할 수 있다고 생각하여 코드를 짜보았다. N = int(input()) K = N // 2 - 1 co..

문제 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다. 위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다. 입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단..

2-3-1. [의료 AI] 현미경 영상 분석을 통한 암 진단 ●데이터 살펴보기 정상 세포의 현미경 영상과 암세포의 현미경 영상 정상 조직 사진 : 3,750장 암 조직 사진 : 625장 데이터의 모든 수치는 0 ~ 1 사이의 숫자로 노멀라이즈하여 사용. ●어떤 인공지능 사용? 층수 종류 크기 활성화 함수 1층 CNN 16, (3, 3) ReLu - MaxPool (2, 2) - 2층 CNN 32, (3, 3) ReLu - MaxPool (2, 2) - 3층 CNN 64, (3, 3) ReLu - MaxPool (2, 2) - 4층 CNN 64, (3, 3) ReLu - MaxPool (2, 2) - 5층 CNN 64, (3, 3) ReLu - MaxPool (2, 2) - 6층 Flatten - - 7층..

문제 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라. 입력 첫 줄에 N과 K가 주어진다. (1 ≤ K ≤ N ≤ 106) 둘째 줄에 N개의 인형의 정보가 주어진다. (1 또는 2) 출력 K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 출력한다. 그런 집합이 없다면 -1을 출력한다. N, K = map(int,input().split()) N_list = list(map(int,input().split())) idx_list = [] #인형 위치 확인 for i in range(N): if N_list[i] == 1:..

문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력 첫째 줄에 정답을 출력한다. # - 기준으로 나누고 arr = input().split('-') total = 0 # 처음 숫자와..

문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15..

1260 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면..

2-2-2. AI는 사진을 완벽하게 이해할 수 있을까? - Semantic Segmentation ●Semantic Segmentation Semantic Segmentation은 앞서 배운 것의 한발 더 나아간 것. 이미지 속의 모든 픽셀을 완벽히 분석하여, 각각의 픽셀이 어디에 속하는지 분류하는 과제. 결과적으로 모양이 불규칙적이거나 작은 물체도 경계선을 따라 분리해 낼 수 있으며, 한 장의 사진 속에 포함된 여러 가지 물체를 동시에 분류. ●데이터 살펴보기 사진 데이터는 0 ~ 1 사이의 값을 가진 (128, 128, 3) 사이즈 데이터로 변환. annotation의 경우 배경은 0, 하얀 영역은 1로 노멀라이즈된 (128, 128, 1)사이즈 데이터로 변환하여 사용. ●어떤 인공지능 사용? U-N..

2-2-3. AI는 현실 세계의 사물을 이해할 수 있을까? - Object Detection ●YOLO - You Only Look Once 객체 탐지(object detection) 분야의 혁신적인 해결수단으로 각광받고 있음. ●Object Detection 목표 영상 속의 물체를 인식하는 인공지능을 만드는 것. 자율주행이나 농업 등 시각적 정보에 대한 판단이 필요한 영역에 적용하기 좋음. ●어떤 인공지능을 만들 건가요? YOLO는 입력받은 이미지를 바둑판처럼(grid) 가로세로로 잘게 쪼개고, 각각의 조각이 '어떤 클래스에 속하는지' 분류하는 기계. CNN을 활용한 딥러닝 모델이 적용. 텐서플로 라이트 이용. ●인공지능 학습 결과 데이터가 ImageNet이라는 데이터셋을 대상을 학습된 것이다 보니 정..