매일 꾸준히

백준 골드 4를 달성했다. ! 정렬이나 ,최근에는 그리디, 투포인터문제를 많이 풀어봤는데 아직 많이 부족한걸 느끼고있다. 자료구조를 덱까지 공부하고 트리부터는 공부를 느슨하다시피(사실 안함..ㅏ) 했는데 진짜진짜진짜 *1000000 공부해야겠다.. 종만북을 하고있긴 하지만 굉장히 낯설다. C++ STL을 공부안하고 C만 공부한 상태로 보다보니깐 더욱 어려운 것 같다. 이분탐색도 뭔가 느낌은 알겠는데 Left,Right 초기 설정하는 법을 잘 모르겠다. 부족한 점이 많지만 올해 1년동안 최선을 다해서 알고리즘+자료구조를 공부해 나가야겠당..! (그리고 수강신청 개망함.ㅏ)

https://accurate-agustinia-56a.notion.site/055162e5505446d7b762607ad1b2e7a2

분할정복이란? 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다. 첫번째 그림은 항상 문제를 한 조각과 나머지로 쪼갠다. (재귀호출) 두번째 그림은 항상 문제를 절반씩 나눈다. (분할정복) 분할정복을 사용하는 알고리즘의 구성 요소 1)문제를 더 작은 문제로 분할하는 과정(Divide) 2)문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(Merge) 3)더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(Base case) 분할정복의 장점??? 문제를 나눔으로써 어려운 문제를 해결 할 수 있다.병렬적으로 문제를 해결하는 데 장점이 있다. 분할정복의 단점??? 일반적으로 재귀 함수를 ..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 입력의 최대 크기가 100000(10만)이고 종만북에서 본 것을 써보자면(주먹구구의 법칙) 서론) '입력의 최대 크기'를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해 ,1초당 반복문 수행 횟수가 1억을 넘어가면 시간 초과가 날 수 있다.! N->입력의 최대 크기가 10만이니깐 O(N^2) ->시간초과가 날 수 있다. O(N) -> 시간초과가 안 날 것이다.. DP로 풀면 O(N)의 시간복잡도로 풀 ..

10월 한달 동안 주말 해커스 강남 오전종합반을 듣고 11월 한달동안은 혼자서 문제 풀고 리뷰하는 식으로 공부했다/ 딱 850점이 나와서 신기했다. 이제부턴 다시 열심히 백준 문제를 다시 풀어봐야지

https://www.acmicpc.net/problem/2693 2693번: N번째 큰 수 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,000 www.acmicpc.net 문제 배열 A가 주어졌을 때, N번째 큰 값을 출력하는 프로그램을 작성하시오. 배열 A의 크기는 항상 10이고, 자연수만 가지고 있다. N은 항상 3이다. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,00..

어제부터 쭉 고민했던 문제인데 드디어 풀었다..! https://www.acmicpc.net/problem/17952 17952번: 과제는 끝나지 않아! 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이 www.acmicpc.net 문제 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이다. 다행히 과제 제출 기한은 학기가 끝날 때까지이다. 너무나도 많은 과제를 하다가 미쳐버린 성애는 아래와 같은 규칙으로 과제를 해 나가고 있다. 과제..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4,..

https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알..

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 문제 옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다. 길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자. S = A[0]×B[0] + ... + A[N-1]×B[N-1] S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다. S의 최솟값을 출력하..