컴퓨터공학 아주 살짝 맛보기
필자는 현재 화공생명공학을 전공중이지만
전적대학에서 유사컴공을 전공한 전적이 있음
4학년까지 다녔지만 어차피 자퇴할 생각을 가지고 있었어서
아주 심화된 내용까지 공부하지는 않았지만
대충 큰 흐름은 안다고 생각함!
컴퓨터공학을 이루는 분야는 정말 많지만
자료구조와 알고리즘은 이들 중 가장 핵심적인 분야로
이걸 안가르치는 컴퓨터공학과는 세상에 존재하지 않음
자료구조는 쉽게 설명하자면
컴퓨터는 주어진 프로그램의 절차에 따라 데이터를 처리하는 장치인데
이 데이터들을 효율적으로 처리할 수 있도록 어떤 틀에 맞춰 규칙에 따라 행동하도록 설계하는데
이 데이터들의 틀과 규칙이 자료구조라고 보면 됨
예를 들어서
음식점 입장대기 프로그램이 있다고 하자.
여기서 다루는 데이터는 예약 손님들의 정보인데
먼저 예약한 손님이 가장 먼저 줄을 빠져나가 입장 알림을 받아야하는 상황임
즉, 선입선출(First in First out)의 특성을 갖는 자료구조를 이용해야하는데 대표적으로 Queue를 이용할 수 있음.
Queue 자료구조는 데이터를 순서대로 저장하는데, 데이터를 뽑아내는 연산을 수행하면 가장 먼저 저장된 데이터가 반환되도록 설계된 자료구조라서 이 상황에 딱 맞음.
(참고로 이 큐라는게 롤 대기 큐할 때 그 큐랑 같은 말임)
이게 메인은 아니고 이번 글에서는 알고리즘에 대해 혀끝으로 아주 살짝 맛볼 것임
알고리즘은 '어떤 일을 처리해가는 절차' 라고 생각하면 됨
예를 들어 라면을 끓이는 알고리즘이라고 하면
1. 냄비에 물을 550ml 넣는다
2. 스프와 후레이크를 넣고 끓을 때까지 가열한다.
3. 면을 넣고 약 3분간 휘저으며 풀어준다
이렇게 적을 수 있음
한 반에 30명의 학생이 있는데, 키 오름차순으로 줄 세우는 알고리즘이라고 하면 여러 방법이 있겠지만 이렇게 시도해볼 수 있을 것임.
1. 줄서있지 않은 학생 중 한 명을 뽑는다.
2. 이 학생을 줄의 맨 앞학생부터 비교하여 비교대상 학생의 키가 더 작으면 계속 진행, 비교대상 학생의 키가 더 크다면 그 학생 앞에 끼워넣는다.
3. 1로 돌아가 줄서있지 않은 학생이 0명이 될 때까지 반복한다
이렇게 시도해볼 수 있음.
뭔가 비효율적인것 같고 대충 눈대중으로 끼워넣으면 안되나싶을 수 있는데
컴퓨터공학에서 알고리즘은 주어진 일을 예외없이 명확하게 처리할 수 있는게 중요하고
컴퓨터에겐 "대충 눈대중" 이런 개념이 없음.
서론이 길었는데
오늘 다뤄볼 내용은 이분탐색 (binary search) 라는 알고리즘인데, 간단하면서도 매우 효율적인 알고리즘이라
알고리즘이 왜 필요한지, 알고리즘 성능은 어떻게 측정할 수 있는지 설명하기 딱 좋아서 택해봄.
이분탐색은 대소비교가 가능한 원소들(주로 숫자)이
오름차순(또는 내림차순)으로 정렬된 리스트형 자료구조에서 찾고자 하는 원소의 위치를 빠르게 찾아내는 알고리즘임
(리스트 자료구조는 그냥 일렬로 자료를 이어붙인 단순한 자료구조임)
작동방식은 다음과 같음.
1️⃣ 주어진 리스트의 중앙에 위치한 원소a 를 뽑아낸다.
2️⃣ 이 원소가 찾고자 하는 원소인지 비교해본다.
3️⃣ a가 바로 그 찾고자 하는 원소였다면 a의 위치를 반환하고 종료.
만약 a가 더 크다면 a 왼쪽에 위치한 절반 크기의 리스트에 대해서 1번부터 다시 수행하고
a가 더 작다면 a 오른쪽에 위치한 절반 크기의 리스트에 대해서 1번부터 다시 수행
예를 들어서
리스트가 다음과 같이 10개의 원소가 나열되어있다고 하자
[-5, -2, 0, 3, 4, 6, 7, 8, 10, 20]
여기서 8이라는 숫자가 몇 번째에 위치하는지 이 알고리즘으로 찾으려고 해보자.
1. 전체 갯수가 10개니 절반으로 나누면 5.
5번째에 위치한 4라는 숫자를 뽑아내자
2. 4랑 8이랑 비교하자
3. 8>4 이므로 4이후의 값들로 구성된 리스트
[6, 7, 8, 10, 20] 이걸 들고 1번으로 복귀
1. 갯수가 5개니 절반으로 나누면 몫은 2.
2번째에 위치한 숫자인 7을 뽑아내자
2. 7이랑 8이랑 비교하자.
3. 8>7 이므로 7 이후의 값들로 구성된 리스트
[8, 10, 20] 을 들고 1번으로 복귀
1. 갯수가 3개니 2로 나누면 몫이 1.
1번째에 위치한 8을 뽑아내자.
2. 8이랑 8을 비교
3. 8=8이므로 이 8이 위치했던 자리를 출력하고 종료
(여기선 복잡해져서 언급 안했지만 실제 코드로 짤 때는 리스트를 분할할때마다 그 위치도 같이 넘어가서 이 단계에서 위치값 정보가 존재함)
이 알고리즘으로 10개 크기를 갖는 리스트에서
단 3번의 비교만으로 8의 위치를 찾아냈음.
8이 만약 한가운데 위치했다면 1번 비교만에 찾아낼 수도 있겠지만, 최악의 상황을 가정했을 때가 성능이라고 볼 수 있지 않겠음?
최악의 상황은 리스트를 n번쪼개서 결국 1개밖에 안남았을 때가 될 것임.
그리고 한 번 쪼갤 때마다 리스트 크기가 1/2배가 되니
리스트의 크기가 N이라고 할 때
대충 다음과 같이 식으로 쓸 수 있고
양변에 N을 나누고 역수를 취하면
n에 대해 정리하면
따라서 이분탐색을 이용하면
크기가 N인 정렬된 데이터에서
어떤 값의 위치를 찾아내는데는 아무리 느려도
log_2 N 회만에 해결이 가능하다는 것
근데 이게 무슨 의미가 있냐고?
만약 이분탐색을 안쓰고
앞에서부터 차례대로 비교하는 방식으로 위치를 찾는다고 해보셈. N 크기의 데이터에 대해서 최악의 경우 N회 모조리 다 비교해야하는데
N = 10억이라면?
아무리 컴퓨터라고 해도 10억회 연산은 '순식간'에 처리되지 않고 초단위로 넘어가게 됨.
반면 이분탐색으로 찾게되면 10억이 대략 2^30정도 되니 최악의 경우라도 단 30번의 비교만에 결과를 찾아냄.
컴퓨터 입장에선 30회 비교연산은 0.0000001초만에 처리가능하니까 어마어마한 차이라고 볼 수 있음
아까 학생들 줄세우는 알고리즘에 대해 얘기했었는데
과정속에 한 학생을 골라 이미 오름차순으로 세워진 줄 앞에서부터 비교해가며 위치 찾아 끼워넣는다고 했잖음?
이 비교 과정에 이분탐색을 적용시킨다면
위에서 언급한 줄세우기 알고리즘 속도도 훨씬 개선 시킬 수 있을 것임.
참고로 줄세우기 알고리즘을 보통 정렬 알고리즘이라고 부르는데, 이거도 종류가 되게 많고 성능도 제각각임.
이상으로 컴퓨터공학과에서 어떤 공부를 하게 될지
아주아주아주아주아주 살짝 맛보기 글을 마침
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
팔굽혀펴기 아직 ㅈ밥이라 5개 3세트 2-3일 째인데 ㄹㅇ 근육통 때문에 공부에...
-
1. 미역과 다시마는 캄브리아기에 최초 출현하였다. 2. 해령에서 압력감소로...
-
사문 모고 오답하던 중 아까 오르비에 글 올라온거 보고 쓰는건데 강의는 아직...
-
지금와서 엔제는 좀 그렇고 에스컬레이드+토탈리콜 하다가 실모+기출 들어갈 예정인데...
-
시원해지는척 진짜 에바임
-
평가원이랑 비교했을때요
-
풀이 스포 주의 드디어 풀었습니다. 못 풀었으면 잠 못 잘 뻔
-
어쩜 이렇게 맛있게 쓸 수가 있지 진짜
-
신택스 독학 0
신택스 강의듣는중인데 신택스 강의를 꼭 들어야 할까요? 예습때 한 내용 다시보는...
-
아주대 인천대 명지대 면접이 다 11월 23일이야.. 내일 하나 접수하고 나머지...
-
온라인으로 파이널 실모 중에서 이감 상상 둘 중 하나 사려고 하는데 어떤게 좋을까요...
-
추일서정 마지막 구절 호올로 황량(荒凉)한 생각 버릴 곳 없어 허공에 띄우는 돌팔매...
-
수능 빨리 보고 싶다..... 그냥 빨리 끝났으면... 얼른 끝나고 푹 쉬면서 대학...
-
공대 대학 인식 11
국민대 광운대 서울과기대 고민인데 셋 중에 국민대가 확실히 더 낫겠죠..? 광운대...
-
oz개념 너무 무거워서 문제 따로모으고 개념+step2만 자를까하는데
-
가격이 만만치 않는데 보신분들 어떤가요???
-
조만간 일을 크게 하나 시작해야겠군요,,ㅎ
-
범준쌤 대기 풀려서 9/21부터 가려는데 몇회부터 합류하게 되는걸까요? 지금...
-
선배는 남자아이 유사 하렘 뭐보지 추천좀..
-
흐흐흐흐흐흐흐흐 7
♥︎
-
----------‐------------------------------------...
-
둘중 하나를 님들한테 선택할수 있는 기회를 준다고 하면 뭐할거임?
-
알거 같아요 오늘 국영탐 5시간 풀로 공부하니깐 눈앞이 빙글빙글거림 문자로만 봐서 그런가..
-
신비로운수학의세계 22
흔히 세상에서 가장 아름다운 식이라고 알려져 있는 이는 오일러 공식으로 알려져 있는...
-
키스로직s3 0
풀어보신 분들 난이도 어떤가요? 9평이랑 비교했을 때
-
자연계에서 미적분, 기하 선택 할 수 있는 걸로 아는데 왜 모집요강에는 그런 말이 없죠..??
-
어휘력은 국어사전이 아니다(ft. 법학 제재 목록) 3
안녕하세요 독서력 강화플랜을 연재하는 타르코프스키입니다. 최근에 오르비에서 정석민...
-
이대 사범대 삼수해서 간게 객관적으로 그리 대단한건가..물론 전체 아이돌 중에는...
-
수능원서처럼 교복사진제외한 여권사진만 취급인가요?
-
피가 줄줄 나네
-
공통 11번 부터 맵네
-
영어 4등급 16
영어 목표 2~3인데 신택스 괜찮을까요?
-
국숭세단아래로 절대 안가고싶은데 현시점에서 수시로 안정써서 가야하나요 (ㅅㅂ 원세대...
-
국어 공부를 해도 너무 성적의 변화가 없어서 작년 수능 이후로 국어 공부를 하나도...
-
경영 넣고 싶은데 각각 장단점이 뭔가요.. 그리구 최종적으로 어디가 더 나음? 충남 살긴 함
-
자사고 3점대입니다.. 1학년 1학기때 기술가정이 한번 9등급 뜬적이 있는데,......
-
가능?? 일단검더텅사옴요...
-
저 사전 예약 걸어둘지말지 갈등되네요
-
실모 하나 풀고 서바 8회 하나 더 푸는데 머리가 깨질거같음 12번까지 빠르게 치고...
-
시급 3에서 3.5까지 생각합니다... 서울입니다... ㅈ같습니다... 국어 때문에...
-
30번 이정도면 어렵지 않나... 저거 하나 틀리긴 했는데
-
미적 노베 질문 1
미적분 처음하는데 김기현T 아이디어 + 쎈 으로 시작해도 되나요??
-
수시로 인천대 쓰시나요...? 쓰면 정시 잘 봤을 경우 무조건 납치고 안 쓰고 학종...
-
[지구과학1] 230920 - 왜 우주 초기에 우리은하를 향해 발사된 빛은 우리은하로부터 멀어지다가 다시 가까워질까? 2
23년도 9월 20번 자료에 대한 의문 - 왜 우주 초기에 우리은하를 향해 발사된...
-
메가스터디 공모전 입상 16
이게 됐네요 다른 곳에서 이미 계약해버렸지만 칼럼이 드디어 책으로 나오게 되었습니다...
-
6,9평 둘다 1인데 점수 처참하게 뜨네요; 원래 이럼?
-
그게나야 둠빠 둠빠 두비둠빠
-
[단독] 응급실 근무 '의사 블랙리스트'…경찰 스토킹법 적용 검토 1
경찰이 온라인에서 유포되는 의사 블랙리스트인 ‘감사한 의사 명단’ 관련해...
-
월급 300준다고 하면 갈 사람잇슴?
컴공가면 캘투사슬쐐기 잘 맞출 수 있나요
20렙까지 어둠 30스택 못찍을 수는 있습니다
우웩.ㅡ
시간복잡도로그n
FILO 스택