1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2. 접근 연속합은 동적계획법이나 분할정복 등의 여러 알고리즘으로 구할 수 있는데, 그 중 시간복잡도가 가장 낮은 동적계획법으로 구현했다. * 동적계획법이 아닌 다른 알고리즘은 아래에 참고하면 된다. https://2nnsv.tistory.com/40 [알고리즘] 연속 부분 수열의 합 연속 부분 수열의 합? : 비어 있지 않는 숫자 배열에서 합이 최대가 되는 연속된 부분수열 구간의 합 아래와 같은..
분류 전체보기
연속 부분 수열의 합? : 비어 있지 않는 숫자 배열에서 합이 최대가 되는 연속된 부분수열 구간의 합 아래와 같은 정수 배열이 있을 때, -2 -3 4 -1 -2 1 5 -3 4부터 5까지의 연속된 구간의 합은 7로 다른 부분 배열의 합보다 항상 크다. 이처럼 연속적인 부분 수열의 최대 합을 구하는 것이 이 문제의 목표이다. 1) 완전 탐색(Brute Force) : 가능한 모든 경우의 수를 조사해 찾는 알고리즘 👉 배열의 인덱스를 0부터 시작해 한 단계씩 나아가면서 중간값을 사용해 결과를 낸다. 먼저, 고려해야 할 부분은 크기가 1인 부분 수열의 합 현재까지 구한 답에 현재 배열의 인덱스 값을 더해서 끝내는 경우 현재까지 구한 값을 버리고 현재 인덱스 값으로 다시 시작하는 경우 현재 값과 현재까지 만든..
1. 벨만 포드 : 그래프 상의 한 정점으로부터 다른 모든 정점들까지의 최단 경로를 구하는 알고리즘 - single-source 최단경로 알고리즘 - 가중치가 음수인 경우도 적용 가능 - 가중치가 사이클을 이루는 경우 불가능 - 시간 복잡도 O(nm) (최악의 경우 최대 n개의 정점, n-1개의 간선) - 동작과정 - 가장 가까운 노드를 탐색해 한 단계 거칠 때마다 최단 거리를 확정해 나감. - (n-1)번 반복해 모든 노드 간의 최단 거리를 완화해 나감. s에서 u까지의 최단 경로가 다음과 같다고 가정하자. 처음에는 모두 upper[] 상태 시작노드인 s는 upper[s] = dist [s] = 0 이다. 모든 간선을 탐색해 relaxation 과정을 반복한다. upper[a]
Sliding Window 란? 고정된 크기의 윈도우가 이동하면서 윈도우 내의 데이터를 이용해 문제를 풀어가는 알고리즘 배열, 리스트의 요소의 일정 범위의 값을 비교할 때 유용한 알고리즘이다. def maxSum(arr,k): n = len(arr) # length of arr if n 주어진 arr에서 더해서 최대가 되는 값 찾기 참고 https://www.thecrazyprogrammer.com/2017/05/sliding-window-protocol-program-c.html
1. 관계 데이터 모델 · 관계형 데이터베이스의 모델 · 모든 데이터는 릴레이션(≒테이블)으로 표현 2. 용어 1) 릴레이션 : 릴레이션 스키마 + 릴레이션 인스턴스 2) 릴레이션 스키마 · 속성들의 집합, 릴레이션의 논리적 구조 · 시간에 따라 불변 · 릴레이션 스킴 / 내포 3) 릴레이션 인스턴스 · 일정 시점에서의 투플(tuple)들의 집합 · 시간에 따라 가변 4) 투플(tuple) · 속성에 해당하는 데이터의 모임 5) 속성(attribute) · 단순 속성 : 단일값, 관계형 데이터베이스에 사용 · 복합 속성 : 단순 도메인의 결합, 하나의 속성으로 취급 (ex-DATE : YEAR, MONTH, DAY의 결합) · 속성값은 분해할 수 없는 원자 값 6) 도메인(domain) · 속성이 취할 ..
파이썬 오류 발생 시 f=open("C:\Users\user\Desktop\dict_simplified.txt", "r") 파일 경로를 '\' 로 보통 표시하는데, '\\' 이렇게 두번 작성하면 오류 해결됨. f=open("C:\\Users\\user\\Desktop\\dict_simplified.txt", "r")
1. 문제 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 2. 접근 n과 m을 입력 받고 입력받은 값들을 비교 같은 값이 있다면 cnt++ 주의할 것은 a와 c를 모두 strip()으로 공백을 없애거나 모두 strip()함수를 쓰지 않아야함. 왜냐하면 같은 문자라도 a는 공백이 있고, c이 없으면 일치하지 않기 때문 3. 문제풀이 import sys n, m=map(int, sys.stdin.readline()..
1. input() : 문자열 입력 - input은 문자열을 입력받기 때문에 입력값을 list로 저장할 수 있다. - 정수/실수형일 때는 각각 int, float를 붙여주면 된다. input()은 개행 문자를 삭제 시켜 리턴 리스트처럼 여러 개의 값을 받아야 하는 경우에 split() 함수로 공백을 기준으로 값을 나누는게 좋다. 2. sys.stdin.readline() : 한 줄에 여러개의 입력값을 받음 - strip()으로 문자열의 앞, 뒤의 공백을 제거할 수 있다. * rstrip() : 문자열의 앞 공백 제거 * lstrip() : 문자열의 뒤 공백 제거 3. map() : 한 줄에 여러 개의 변수를 입력받음.
1. 문제 https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 2. 접근 https://2nnsv.tistory.com/31 [Python] 파이썬 입력 함수 1. input() : 문자열 입력 - input은 문자열을 입력받기 때문에 입력값을 list로 저장할 수 있다. - 정수/실수형일 때는 각각 int, float를 붙여주면 된다. inpu.. 2nnsv.tistory.com 3. 문제풀이 import sys n..
이게 뭔데 ㄴ미아ㅓ리마어 마지막에 export default App; 하고서 엔터안쳐서 문제 생긴 거였음. 엔터치면 해결됨
