전체 글
-
2022 한국 정보 올림피아드 1,2차 후기일상 2022. 8. 1. 16:16
실력이 부족해서 후기라 할 것도 없었다. PS는 작년 1월달 부터 하기 시작했다. 1차 1차를 보는데 필기가 엄청 어려워서 원래 180점 정도를 예상했지만,(거짓말,최대공약수)문제를 틀리고, 확률과 통계 관련 문제를 틀려서 100점 초반대가 나왔다. 실기는 2번 문제는 손도 못 댔고, 1번 피하자 문제를 푸는데, 일단 다 바꿔보는 브루트 포스로 50점을 긁었고, 누적합을 사용해 O(n)만에 풀려고 했고, 로직은 맞았다. 하지만 int 자료형을 넘는 경우가 있어 그것도 모르고 있다가. 동상을 받게 되었다. 2차 1번 먼저 1번 문제의 서브테스크 1번을 풀려고 했다. 근데 계속해서 0점이 나와 당황해 3번 4번 문제의 1번 서브테스크만 긁고 다시 돌아왔는데, 갑자기 등차수열에서 원소가 정수란것을 이용해서 O..
-
Greedy(욕심쟁이)알고리즘/그리디 2022. 7. 31. 10:08
흔히 풀 수 있고, 어려운 것은 어려운 그리디에 대해 말해보겠다. 그리디는 단편적인 큰 코스트를 취하는 방법이다. 1.그리디의 예시 빠르게 본론으로 넘어가겠다. 백문이 불아일견이라 했다. 우리가 1원 5원 10원의 동전들이 무수히 많다고 하자. 자연수인 N이 주어질때 동전들의 합으로 N을 만들어야하는 상황에 사용되는 동전들의 개수를 최소화 시킬려면 어떻게 해야할까? 2.해답 어짜피 1원 5개를 쓰일 상황에선 5원을 하나 쓰는게 이득이고 5원 2개 쓰일빠엔 10원 하나를 쓰는게 이득이다. 고로 10원을 N에서 계속 빼다가 5원을 빼고 1원을 빼는 것. 가장 큰 액수부터 빼는게 이 문제의 답이다. 이러한 것 처럼 그리디는 단순히 그 순간만을 위한 최선의 선택을 하는 알고리즘이다. 정당성에 관한 부분은 그 문..
-
시간복잡도알고리즘/기법,기초 2022. 7. 31. 09:52
시간복잡도는 프로그램의 수행시간을 다항식으로 나타내는 것이다. 시간복잡도는 시간제한이 있는 OJ사이트나 코딩 테스트,대회 등에서 중요한 요소이다. 하지만 대부분의 사람들은 시간복잡도를 그냥 대충 계산하는 경향이 있다.(사실 그래도 된다.) 그러나 필자는 깊이 있는 문제 풀이를 위해 시간복잡도가 굉장히 중요한 요소라 생각하기에 이에 대해 말해 보겠다. 1.시간복잡도 계산 그 프로그램에 있는 반복문의 반복 횟수라 봐도 문제가 없다. arr[1]과 같은 한 번에 접근 가능한 것을 O(1)의 시간복잡도를 가졌다 하고, 이는 그 프로그램의 시간복잡도에서 보통 생략된다. 예를 들어보자. n=int(input()) for i in range(n): print(i) 다음의 코드는 i가 0부터 n까지 1씩 증가하는 코드..