수능 알고리즘 1화
게시글 주소: https://orbi.kr/00039544566
알고리즘을 공부하면서 이 알고리즘을 수능에 적용해보자는 생각이 들었다.
컴퓨터와는 다르게 수능에서 쓸수있는 연산은 훨씬 오래 걸린다.
예를 들어, 컴퓨터는 무언가를 기억하기 위해 메모리에 저장을 하면 되지만 사람은 종이에 글씨를 써야한다.
하지만 글씨를 쓸 종이가 무한하지 않으므로, 최대한 적게 쓰면서 문제를 풀어나간다.
이는 메모리 공간을 적게 차지하는것을 뜻한다.
또한, 수능에서 시간제한이 있는것은 최대한 효율적으로 문제를 풀어나가는 알고리즘만이 해결할 수 있다.
그렇다면 먼저 시간 복잡도를 정의 해보자.
글자 1개를 쓴다 = 330ms/1KB
눈으로 글자 한개를 읽는다 = 80ms/0KB
이정도 정의만해도 국어 문제에 적용 할 수 있다.
국어 문제를 푸는 방법에는 크게 지문을 읽고 문제를 푸는 방법과 문제를 읽고 지문을 푸는 방법이 있다.
이번 화에서는 지문을 읽고 문제를 푸는 방법을 알아보자.
지문의 글자수를 N이라고 할 때, 먼저 지문을 읽는데 걸리는 시간은 80 * N ms로 나타낼 수 있다.
지문을 모두 이해 했다면, 1번 문제로 가서 문제를 읽는다. 이때 이 문제의 내용을 기억할 확률을 p라고 하면
(1-p)의 확률로 지문으로 다시 돌아가야 한다.
이때는 문제에서 요구하는 부분을 찾는데 이분탐색 알고리즘을 사용할 수 있다.
그러나, 이분탐색 알고리즘은 정렬된 데이터에 사용가능하다. 즉, 어떤 부분을 읽고 내가 원하는 부분은 그 앞인지 뒤인지를 알아야 한다. 지문을 먼저 읽었으므로 그정도는 알것이라고 생각한다.
이분탐색의 시간 복잡도는 O(logN). 정확한 시행 횟수로는 log2 N이다.
다시 정리하면, 총 시간은 [N + {(1-p) * (log2 N)}^(3~5)] * 80 ms로 나타낼 수 있다.
따라서 시간 복잡도는 O(N)이다.
다음 화에서는 문제를 읽고 지문을 푸는 방법을 알아볼 것이다,
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
48점 1등급 샤가프 안나와서 그런지 코돈 문제 잘못읽고 3번풀었는데도 시간 안에...
-
ㄷㄷㄷㄷ
-
-
자러감요
-
숏츠에서 내가 너와 상호작용한 모든 내용을 바탕으로 내 사고 패턴과 의사 결정...
-
공부자극좀 8
해주세요.. 방탕해짐
-
서울대가겠네
-
다이어트 할 사람? 13
내가 진짜 커리큘럼 잘 짜줄테니까 할 사람
-
좀 더 찌면 굴러다닐 수 있을것도 같아
-
맨날 쳐자느라 수업 못하고 수업 중간에 화장실가서 30분씩 농땡이피우던...
-
-
수행 GPT 4o 딸깍 후 제출 (or gemini 2.5 pro) 그것도 귀찮으면...
-
금일 6시 기상 목표 12
실패시 만덕 열번째 댓글에게 답글 미포함
-
결아가 ㅠㅠ
-
하는게 엄ㅅ네 0
과외라도 구해볼ㅋ가
-
수학 그래프 7
지수함수나 삼각함수,다항함수 관계없이 그래프 문제들에 좀 힘겨워 하는데 어떻게 해결하면 좋을까요..
-
몇개 깔까
-
현타온다 ㅠㅠ
-
삼각김밥 마려운데 10
먹어라 vs 먹지마라
-
고민 들어줄사람 8
슬프다
-
고2때 내신 할 때는 머리싸매면서 풀다가 고3때는 좀 편하게 풀고 재수땐 하루컷ㅋㅋ
-
걱정하지마 의평은 정백(이)가 지키고 있어요
-
물1, 화1 내신 대비하려는 데 둘 중 뭘 먼저 푸는 게 좋을까요?
-
힘내자 우린 절대 ebs 안 본다 ebs는 사탄의가래다 우린 기출을 통해 연계없이...
-
이신혁t 0
시즌2부터 들어도 좋나요?
-
오늘 깨달은 사실 11
의평은 연막이다 존잘존예 너무 많ㅇ…
-
ㅈ반고 수준 5
수행평가로 80줄 가까이 되는 보고서 같은거 손으로 써서 냈는데 쌤이 다 읽기...
-
현역 n제 1
현역 기준 기출을 언제까지 끝내고 몇 월 부터 N제를 시작하는게 바람직 할지...
-
독학으로 충분한가요? 아니면 기출강의 듣는게 좋나요?
-
으앙으앙
-
이거 템플릿임? 4
나도 받았다 히히
-
220622특 4
식으로 초반작업하면 (나)의 세 근이 등차수열 관계임을 알 수 있음 이후에 그래프...
-
3모 10분컷 3덮 47받았는데 이번 시험지는 시간재다 3페이지 절반쯤 풀었을때...
-
설맞이 샤인미 2
나오자마자 풀어야지
-
멀리 다녀왔다 ㅎㅎㅎ
-
ㅈㄱㄴ 개념 유형서(킥옵) 기출 요정도면 충분??
-
집에 온 기념 질받 13
-
망했다ㅏ 1
3일동안 수학 실모 하나 풀었다 남은 기간 열심히 할게요ㅜ
-
내 문제의 90퍼는 시험장 안에서 발생하는거같은데
-
4월 더프 세지에 가축으로 '낙타'가 나와서 생각난건데 2
사우디아라비아는 낙타의 순 수입국임 실제로 사우디아라비아는 관광용 및 경주에 쓰이는...
-
-
으흐흐..이제 콜플로 채운다
-
외로워요 6
유튜브에서 폭삭 속았수다 짤 몇개 보고 문과 취업 안된다는 뉴스 보니까 갑자기 인생이 외로워짐
-
ㄹㅇㅋㅋ
-
오고곡 오고곡 1
오오 고대 고대 고려대에에 곡고곡 고대 가고 싶어서 울었어
-
-
비가와 오랜만에 1
비가 오지말라했어
-
저는 코사인 법칙 쓰는문제인지도 몰랐슴,,
-
이미 유네스코 갖고 있어서 해설지는 상관 없고 회독용으로 보려는데 실제 시험지...
-
드가자
오
오 오랜만이십니다