Doby's Lab

https://www.acmicpc.net/problem/13544 13544번: 수열과 쿼리 3 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 쿼리마다 부분 배열을 정렬하여 값을 구하면 정렬 O(nlogn), 탐색 O(n), 쿼리의 수 O(m)으로 >> 시간 복잡도가 O(n^2 * logn * m)으로 시간 초과가 나게 된다. 그렇다고 해서 탐색을 이분 탐색으로 하기에도 이미 O(n * m)에 의해 시간 초과가 난다. 이럴 때 필요한 자료구조가 머지 소트 트리이다. 코드를 보면 아마 [머지 소트 트리 =..

앞선 포스트에서 Merge Sort에 대해 공부했었다. Merge Sort를 바탕으로 만들어진 자료구조 Merge Sort Tree가 있다. 이는 세그먼트 트리처럼 각 노드에 각 구간을 정렬시킨 배열을 저장한다. 즉 머지 소트 하는 과정을 세그먼트 트리에 저장한다고 생각하면 된다. 이를 구현하는 과정에 간편하게 사용할 수 있는 함수들이 있다. merge(v1.begin(), v1.end(), v2.begin(), v2.end(), mergeArr.begin()) 다음과 같이 사용할 수 있으며 v1의 시작부터 끝, v2의 시작부터 끝을 합병 정렬하여 mergeArr에 저장시키겠다는 뜻이다. 헤더 파일에 있다. 하지만, 이 함수를 이용하기 위해서는 mergeArr에 v1, v2를 합병 정렬하여 넣을 수 있는..

(공부한 곳 출처: https://velog.io/@codenmh0822/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B3%91%ED%95%A9-%EC%A0%95%EB%A0%AC) Merge Sort란 분할 정복의 방법을 차용한 방식으로 어떠한 경우에도 시간 복잡도가 O(nlogn)이 나오는 정렬 알고리즘이다. 크기가 1인 배열이 될 때까지 분할한다. 왼쪽 오른쪽으로 분할된 배열을 합치면서(merge) 정렬한다. 시간 복잡도가 O(nlogn)이 나오는 이유는 원소의 개수가 n인 배열을 트리화(?)시키면 무조건 높이는 logn이 된다는 사실을 안다. +병합하는 단계에서 리커시브 콜의 길이를 생각해보면 된다. 분할하는 단계는 시간 복잡도로 치지 ..

https://www.acmicpc.net/problem/1350 1350번: 진짜 공간 첫째 줄에 파일의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 파일의 크기가 공백을 사이에 두고 하나씩 주어진다. 파일의 크기는 1,000,000,000보다 작거나 같은 음이 아닌 www.acmicpc.net (리스트에 관한 참고 자료) https://art-coding3.tistory.com/6 [Python/파이썬] input을 이용해 값을 입력 받아 리스트에 넣기 input 사용자가 입력한 값을 읽어드리는 함수 일반적으로 입력받은 것들을 문자열로 받아들인다. list1이라는 빈 리스트를 생성한다. input을 통해 사용자가 값을 입력하게 하고 이를 s라는 변수 art-coding3...

https://www.acmicpc.net/problem/1264 1264번: 모음의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 영어 대소문자, ',', '.', '!', '?', 공백으로 이루어진 문장이 주어진다. 각 줄은 최대 255글자로 이루어져 있다. 입력의 끝에는 한 줄 www.acmicpc.net 이번 문제에서는 2가지 문법을 배울 수 있었다. if ~ in for 문자 in 문자열 우선 내가 짠 코드(정답)부터 보자 while True: s = input() if s == "#": break #print(s) cnt = 0 for i in range(0, len(s)): if (s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or s[i] ..

https://www.acmicpc.net/problem/5543 5543번: 상근날드 입력은 총 다섯 줄이다. 첫째 줄에는 상덕버거, 둘째 줄에는 중덕버거, 셋째 줄에는 하덕버거의 가격이 주어진다. 넷째 줄에는 콜라의 가격, 다섯째 줄에는 사이다의 가격이 주어진다. 모든 가 www.acmicpc.net C++과 최솟값 함수를 사용하는 법은 같았다. minBurger = 2000 for i in range(0, 3): a = int(input()) minBurger = min(minBurger, a) minDrink = 2000 for i in range(0, 2): a = int(input()) minDrink = min(minDrink, a) print(minBurger + minDrink - 50)

https://www.acmicpc.net/problem/2739 2739번: 구구단 N을 입력받은 뒤, 구구단 N단을 출력하는 프로그램을 작성하시오. 출력 형식에 맞춰서 출력하면 된다. www.acmicpc.net 파이썬으로 for문을 이용해보려다가 정수형 변수 출력하는 법을 알게 되었다. n = int(input()) for i in range(1, 10): print('%d * %d = %d' % (n, i, (n * i))) C언어와 비슷하지만, 어디를 가리키는지를 나타내는 방법은 다른 거 같다. 여러 개다 보니 % 의 오른쪽 기준으로 괄호로 묶어 순서대로 표현해주었다.

C++만 사용하다보니 while이나 for문 조건식을 다는 방식이 특이하단 걸 알았다. (+파이썬은 증감연산자가 없다고 한다.) [1 ~10까지 출력하는 코드 (while)] num = 1 while num