[sw정글 3주차] 째깍 째깍 째깍 Time-Complexity 째깍 째깍 회고록 째깍 째깍 째깍

📚SW정글 3.1주차

평상시처럼 매일매일 알고리즘 문제를 주구장창 풀어나가며, 우연히 알게 된 사실을 기반으로 서치한 내용을 정리 해 보고자 한다.

🚀[알게된 내용 1]Time-complexity에 대하여

최근 파이썬의 Time-complexity에 대하여 알게 되었다. 충격을 받았다. 나를 제외한 모두가 이미 알고 있었다. 하지만 이를 제대로 활용하는 사람을 찾을 수 없어 풀었던 문제들을 회고하며 정리 해 보았다.

⏰[알게된 내용 2]시간제한에 관하여

1억연산이 1초라는 말도 있고, CPU가 좋아져서 10억연산이 1초라는 말도 있다. 한편으로, 파이썬은 연산속도가 느려 2000만 연산이 1초라는 말도 있다. 여러가지 서로 다른 정보를 통해 혼란스러웠지만, 결론을 내릴 수 있었다.

파이썬에서, 1억연산을 1초로 생각하고 풀면 된다.

따라서, 1 < N < 100,000, 즉 N이 10만까지의 값을 가질 수 있다면, O(N)은 1/1000초가 걸린다. 그렇다면, N=10만일 때, for문을 두번 쓰게 된다면, O(n²)의 시간이 걸린다. 100억이므로… 100초가 걸린다!! 따라서, N = 10만일 때, N² 의 연산을 할 생각을 하면 안된다.

O(logⁿ) 에 대하여 생각 해 보았따. 2의 30승은 약 10억이다. 즉, log(10억) = 30연산이다. log의 값에 대하여, 어? 왜 상용로그를 쓰는데 저 값이 나오지? 싶었는데, CS에서의 log는 10의 밑을 가지는 상용로그가 아닌, 2의 밑을 가진 로그로 생각하면 된다고 하다. 그렇게 표기를 한다.

한편, 2의 16.xxx승은 10만, 즉 log(10만)은 16.xxx이다.

🚀[알게된 내용 3]알고리즘에 관하여

알고리즘을 사용하여 문제를 푼다. 왜 알고리즘을 공부해야 할까? 주먹구구식으로 풀어 낼 수 있는 문제들에 관하여, 조금 더 효율적인 솔루션을 도출 해 내기 위함이다. 그렇다면 "왜 이 솔루션이 더 효율적인지"에 대한 근본적인 궁금증을 가져야”만” 한다.

A라는 알고리즘이 무엇인지, 이것을 어떻게 적용하는지에 대한, What 과 How가 아닌, Why가 선행되어야 한다.

이 알고리즘을 왜??? 왜? 사용하는 것일까?

Heap 구조를 왜 사용할까? Heap 자료구조를 사용하면 O(log N) 의 Time-complexity를 보장하며, 새로운 자료들을 삽입하고, 그 와중 최소값과 최대값을 항상 유지시킬 수 있기 때문이다.

왜 스택과 큐를 사용할까? 배열에 넣고 해당 인덱스로 값을 찾으려면 O(N)의 시간이 걸린다. 스택으로 쌓은 배열의 array[0]에 접근하려면 O(N)의 시간이 걸린다. 따라서 어떠한 데이터들의 맨 앞, 맨 뒤의 값을 쉽게 참조하기 위해 사용하는 것이다.

왜 BFS를 사용할까? source로부터의 거리가 k+1인 곳을 방문하기 전, source로부터의 거리가 k인 모든 지점을 방문할 수 있기 때문에 사용한다. edge간의 경계를 명확히 나누어 줄 수 있기 때문이다.

왜 분할정복을 사용할까? 한번에 눈에 들어오지 않는 문제를, 작은문제로 나누어서 해결할 수 있기 때문이다. 분할정복이 더 빠를까? 빠름을 보장하는 알고리즘이 아니다. 목표가 명확한 문제에 대해서 문제를 쉽게 이해할 수 있도록 도와주는것이 근본인 것이다. 그리고 그 와중 Optimal한 solution을 찾을 수 있도록 도와주는 방법인 것이다.

참조: 분할정복에 대한 자세한 이전 포스트(링크)

그렇다. 왜 사용하는지에 대해 알아야 한다. 내가 적은 단순 몇줄로는 부족하다. 해당 알고리즘들을 적용가능하면 좋을 무수한 많은 경우가 있을 테고, 그에 대한 논리적인 판단기준과 육감(?)을 길러 나가는것도 중요하다. 그것이 SW정글 운영진들이 원하는 바 이고, 컴퓨터적 사고를 기르는 본질이 아닐까라는 생각이 든다.

🚀[알게된 내용 4] 2주차에 풀었던 문제 회고

백준문제번호	문제명	문제분류	설명
1920번 문제	수 찾기	이분탐색	숫자가 10,0000 까지 주어져 있다. 이분탐색있로 있는지 없는지 찾으면 되는 것이다. 이분탐색으로 풀면 O(logn) = log(10만) = 16연산, set으로 풀면 O(n) + O(1) = 10만연산
2805번 문제	나무 자르기	이분탐색	딱 원하는만큼 가져갈 수 있을까? 톱날이 5일때는 얼마나? 톱날이 10일때는 얼마나? 톱날이 7일때는 얼마나 가져갈 수 있을까? 10억미만의 길이가 필요하다. 나무의 길이는 20억까지도? 나무의 길이에 대해서는 무조건 n을 씌워야 한다. 길이에 대해서 이분탐색하면 log(10억)
2110번 문제	공유기 설치	이분탐색	집의 개수는 N이다. 공유기 기준이 되든, 집의 좌표가 기준이 되든, 어쨋든 모든 집에 대하여 검사를 해야한다. 그렇다면 집의 개수 N=20만에 대하여, (제한시간이 2초이므로)20억연산 미만으로 끝내야 한다. 그렇다면, 20만 x (?) ≤ 20억 이므로, 10000연산 미만으로 각 집들 사이에 공유기를 설치해야 한다. nC2와 같은 combination은 사용할 수 없다. N개의 공유기도 별다른 힌트를 주진 못한다. 좌표를 이용해서 어쨋든 거리를 측정해야 한다. 그렇다면 log(n)으로 할 수 있는 방법중… 이분탐색이 가장 적당 해 보인다. 그렇다면 집의개수 N=20만에 대하여, 집의 좌표(거리)를 이분탐색하여 풀 수 있는 어떠한 방법을 떠올려 볼 수 있었을 것이다.
2470번 문제	두 용액	이분탐색	N이 10만까지 주어진다. N-combination을 이용해 서로다른 용액들을 뽑아내면 된다. 하지만 그러면 N^2으로 폭발 해 버린다. 그렇다면 nlogn 이하로 만들어야한다. 포인터가 서로 엇갈려 start 인덱스가 edn 인덱스를 넘어서면 반복문이 멈추게 되어있으므로 시간 복잡도는 O(N)이다. 두개의 용액을 보고, 투포인터를 떠올려 볼법 하다. 투포인터 개념이 생소해, 떠올릴 수 없었다.
16564번 문제	히오스 프로게이머	이분탐색	(10만개의 N에 대해서) X (log10억) = 10만 X 30 = > 300만 연산 이다.
8983번 문제	사냥꾼	이분탐색	동물의 수 10만, 사대의 수 10만 ⇒ 동물X사대 ⇒ 100초 ㅠㅠ 그럼 How???? ⇒ (10만동물)X(log 10억) ⇒ 300만 컷!!
10830번 문제	행렬 제곱	분할정복	100억번 곱한다? 말이안됨 ⇒ 바로 싹을 잘라버려야 함 ⇒ log로 만들 수 있는법!!! ⇒ 나눗셈법칙
10828번 문제	스택	스택	0.5초, 하지만 N = 10000, N^2하면 10억이니까 1초 나와버린다… 그렇다면!! 각 명령을 1/2N 이하로 처리해야 한다.
1655번 문제	가운데를 말해요	우선순위 큐	0.5초, 하지만 N = 10000, N^2하면 10억이니까 1초 나와버린다… 그렇다면!! 각 명령을 1/2N 이하로 처리해야 한다.
1715번 문제	카드 정렬하기	우선순위 큐	합친 카드를 내려놓고 그중 가장 작은 값들끼리 섞어주어야 한다. 단순 sort를 하게 된다면 매번 모조리 sort를 시켜야 한다. 아무리 빠른 nlogn의 sort라도, n번 full-sort를 쓸 순 없다. 우선순위 큐를 떠올릴 수 있는 단서가 된다.

🤔느낀 점

이미 푼 문제거나, 틀리고 답안지를 본 문제이다. 이미 솔루션을 본 상태에서 다시 보아도 뭔가 감회가 새롭다. 잘 보면 문제속에 힌트들이 꽤나 많이 들어있다. 3,4주차에 여유가 된다면 내가 문제를 몇개 출제 해 보면 어떨까라는 생각이 든다. 내가 3문제 이상 출제해낼 능력이 된다면, 문제를 만드는 와중, N의 범위라든지 알고리즘 적용 방법에 대한 단서들을 어떻게 흘릴지에 대한 고민이 자연스럽게 이루어질 터이고, 문제를 바라보는 시각이 한번 더 변할 수 있지 않을까 싶다.

글을 정리하다보니, 문제를 직접 만들어 보는것은 좋은 방법일 것 같다. 실력이 부족하더라도 2문제 이상은 꼭 만들어 보겠다고 다짐한다.

---

😵배우면서 깨달은 내용을 정리해 보았습니다. 틀린 것 같은 개념을 아래 댓글에 달아주시면 감사합니다😵

🌜 Thank you for reading it. Please leave your comments below😄

맨 위로 이동하기

swjungle survive 카테고리 내 다른 글 보러가기