채니의 mimimimamimimo 블로그

신청 이유

학교 선배들이 2018 겨울특강을 신청하던 당시에 나는 신청하지 않았다. 

왜냐하면..그때는 나는 악명높은 카카오나 라인의 코딩테스트는 엄두도 못내겠고,

삼성전자의 dfs,bfs만 연습하겠다는 마인드였다. 하지만 문제를 계속 풀다보니 bfs를 풀다가

다익스트라 문제로 넘어가고, dfs를 풀다가 dp로 넘어가는 현상이 일어났다.ㅋㅋㅋ

슬슬 다른 알고리즘이 궁금해지기도 하고, 대부분 기업에서 알고리즘 문제를 꼬아서 내기보단

그 알고리즘의 대표적인 문제 + 구현 문제 요정도로 내는거 같아서 2주만에 빡세게 훑고오자!!라는

생각으로 신청을 했다.

1.접수

구글 플랫폼으로 간단하게 신청한다. (조기마감 될 수도 있으니 미루지 말고 바로 하자!)

몇 주가 지나면 코딩테스트를 치라고 문자,메일이 온다. 

2. 추가 정보, 제출 서류

시험치기 전에 필요한 서류들(병역사항, 재학증명서나 졸업증명서)이 있으니 미리미리 평일에 준비하자.

엘리스에 회원가입도 따로 해야한다. 이걸 하기가 귀찮아서..나는 되게 늦게 시작했다ㅋㅋ(3일차?4일차에??)

3.시험 시작

일주일동안 원하는 때에 시험을 시작하고 끝내면 된다. 권장 풀이시간이 3시간이긴 하지만,

제한은 없기 때문에 여유로워보인다. 그런데...이 6문제가 나는 넘나 어려웠다ㅠㅠㅠ

선배들이 생각보다 오래 걸릴거니까 빨리 시작하라고 해서 시작했는데, 더 늦게 시작했으면 통과 못했을뻔...

시험 문제

공채 테스트처럼 dfs,bfs만 할 줄 알면 되는줄 알았는데 아니었다. 레벨 1단계 문제부터 막혔다.ㅋㅋㅋㅋ

이렇게 총 6문제가 나온다. (총 600점, 각 100점) 

색종이: 투포인터 문제인 것 같고 그나마 젤 쉬운 구현문제였다.

컬러코드: 너무 어려웠다..시간복잡도를 손을 못대겠더라. 백준의 색종이붙이기 풀 때 느꼈던 당혹감과 같았다. 

그래서 꼬박 하루??이틀??붙잡다가 포기..

플라이하이: 최장거리를 구하는 문제라고 느껴졌다. 위상정렬+dp로 풀었다. 

홀수는 싫어: 우선순위큐로 풀었다..

과메기: dp문제인거 같은데 테케 아주 조금 맞고 20점 정도 받았다. 

개미: 수학?기하? 문제인거 같았다. 이건 푼 사람 아무도 없었다ㅋㅋㅋ

내가 못해서 풀이를 못떠올린건지, dfs bfs만으로는 도저히 시간복잡도를 못맞추겠더라..

어디서 주워들은 알고리즘 꾸역꾸역 떠올려서 했었다ㅠ

수료하고 나서 생각해보니 특강에서 저런 류의 문제들을 계속 풀어서

입과테스트 문제 또한 저런걸 낸 것 같다.

참고사항

제출을 하면 해당 문제의 점수가 나온다. 

제출 후 풀이종료 버튼을 따로 누르지 않으면 점수판에 집계되지 않는다. 

풀이종료 버튼을 누르면 집계가 되고, 문제를 다시 풀 수가 없다..

4.입과안내

통과하면 문자와 메일이 온다.  

장소는  잠실 sds 본관의 지하다. (잠실역에서 버스타면 2분, 걸어가면 7분정도 걸림)

첫 날에는 오티때문에 8시까지 와야하고 그 후 2주 동안은 오전9시~ 오후6시까지 수업을 하게 된다. 

5.입과 후

이 교재로 수업을 하게 된다.(비맞아서..꼬질꼬질ㅋㅋㅋ)  작년이랑 똑같다고들 한다.

수업은 개인노트북으로 하기엔 와이파이가 없어서..강의실의 데스크톱을 이용한다 .

밥 맛있다고 소문난 sds 사내식당ㅎㅎㅎ 종류도 어어엄청 다양하고 모두 맛있었다. 

커리랑 돈까스 쪽이 맛있다고들 한다. 커리는 못먹어봤고 돈까스는 확실히 맛있더라..

복날이라 삼계탕도 먹고, 수박국수도 궁금해서 먹어봤다(그냥 냉면 맛이던뎅? 다들 끔찍해했지만 난 맛있었다ㅎㅎㅎ)

중간에 채용설명회도 있으니 입사에 관심있 분들은 물어볼거 많이 준비해가시길!!

6.수업 측면의 후기

작년에는 기본반, 심화반으로 나뉘어서 기본반은 dfs bfs 문제를 좀 다루다가 뒤로 넘어갔다는데 

이번에는 그런거 안나뉘고 심화 알고리즘만 계속 하는 것 같다. 해슁같은 자료구조는 하지 않는다.

(자료구조 생각하고 갔는데 나의 착각이었다..!)

하루에 백준 문제 8개 정도 푼다.

그룹에서 누가 어디까지 풀었는지 순위까지 적나라하게 나와서..현타가 좀 많이 왔었다ㅋㅋㅋ

왜냐면 실력자들이 정말 많았기 때문이다..왜 입과테스트 문제가 권장시간 3시간이었는지 알 것 같았다. 

중급정도의 디피 문제는 30분만에 풀 수 있어야한다.

(그런데 뒤로 갈수록 어려워져서 30분만에는 못풀고 넘어가는 문제도 많아진다)

그리고 이 곳은 모르는 알고리즘을 배우러 오는 곳은...아닌 것 같다. 오기전에 예습 필요하다..

아는 알고리즘도 모르는 알고리즘도 개념 설명이 10분을 넘기지 않기 때문이다ㅠ

기하 듣는 날엔 안가서 어땠을지 모르겠지만.. 그전까진 다 그랬다. 

개념 설명 끝나면 바로 문제 푸는 시간인데, 보통 40분 정도 주고나서 풀이를 한다. 

풀이는 어떤 방향으로 풀면 되는지 알려주는 형식이고 게시판에 정답 코드를 올려준다.

느낌이 딱, 당일 레드블랙트리 개념 알려주고 1시간만에 구현해봐라는 느낌이었다ㅋㅋㅋ

(근데 정말로..인덱스 트리 개념 듣고 바로 문제 1시간만에 풀었어야 했다)

이건 프로님마다 다른 것 같지만, 어떤 분은 이해시키려고 학생들한테 계속 물어보시는 편이고

어떤 분은 질문이 따로 들어오지 않으면 다음 진도를 나가신다. 자신이 준비해온만큼 얻어갈 수 있으니

예습해오고, 와서 반 분위기가 초반에 경직되어 있더라도 질문 많이 해야하는 것 같다.

배우는 내용(배운다기보단..푸는 주제ㅎ)

1일차 - 이진탐색, dp, 투포인터, 슬라이딩윈도우..

2일차 - 재귀함수, 전위중위후위 순회, 인덱스트리(segment tree)..

3,4,5일차 - 그래프...서로소집합(disjoin set), 위상정렬(topological sort), 개선된 다익스트라, 크루스칼,

mst, 벨만포드, 단절점, 최소공통조상(LCA),

6일차 - 유클리드 호제법+확장, 에라토스테네스의 체..

7,8일차 - 조합, 최장증가수열, 온갖 dp문제들...

9,10일차 - 기하(ccw 등등)

이외에도  이진수 변환으로 거듭제곱 빠르게 연산하기, 행렬을 사용해서 피보나치 수열 구하기

등등 신기한거 짚고 넘어가는게 많다. 

나는 따라가기도 힘들었어서..

남은 것이라고 하면, 어떤 문제를 만났을때 무슨 알고리즘으로 풀어야할 문제인지 감은 오겠다는거..?

그 뒤는 내 몫인거 같다ㅎㅎㅎ

7. 수료 시험

10일중에서 8일 이상 출석을 하고 마지막날 시험까지 치면 수료를 할 수 있다. 

작년은 토요일이었다는데 올해부터는 마지막날에 치는걸로 바뀌었나보다. 

그러니 sds b형을 따는게 목적이라면 미리미리 복습을 해둬야할듯..

참고로 sds b형은 입사 프리패스라고 한다. 그래서 특강 두번듣는 사람들도 있는건가싶다.

b형 문제는 한 문제를 4시간동안 풀어야하고

공채나 전자의 상시테스트와 다르게 테스트 케이스 통과 + 코드리뷰로 자격검증을 한다.

그리고 예시 테스트케이스를 안준다!! 자기가 직접 만들어서 넣어보거나 어느정도 꼼수를 써서 체크해야한다. 

b형 난이도는..예상대로 어려웠다.ㅎ 갈피를 아예 잡지 못할 수준은 아니었지만

아이디어가 두 가지 정도가 필요했는데 두 가지 중에서 하나밖에 안떠오르더라...아깝..

차수마다 다르겠지만, 통과하는 사람이 꽤 적은 것 같다. 

알고리즘 틈틈히 공부하다가 겨울특강 뜨면 (그때도 취준중이라면..ㅋㅋ)

또 신청해서 b형 한번 노려봐야겠다. 

What? 알고리즘의 예상되는 실행 시간을 표현한 것

타이머로 실제 시간을 측정하는게 아니라, 알고리즘이 실행될 때 동작하는 모든 연산의 횟수가 몇 번인지를 

n(입력데이터 크기)에 관한 식으로 나타낸다. O(n)

How?

ex) 삽입정렬 알고리즘 : 정렬된 부분집합 A와 정렬되지 않은 부분집합 B로 나누어, B의 한 요소를 꺼내 A에 들어갈 위치를 찾아서 끼워넣는 방법. 반복하여 B가 공집합이 되면 정렬이 완성된다. 

시간복잡도를 구할 때는 비교연산(<,>,<=,>=), 교환연산(=)을 중심으로 구하면 된다.

void Insertion(int n) {
	int key;
	for (int i = 1; i <= n - 1; i++) {  //(1)외부루프는 n-1회 
		key = a[i];    //(2)외부루프에 의해 교환연산이 n-1회 일어남
		int j;
		for (j = i - 1; j >= 0; j--) {  //(3)내부루프는 최대 i회 
			if (a[j] >key){       //(4)외부르프x내부루프에 의해 비교연산 최대 (n-1)+(n-2)...1=n(n-1)/2회 일어남.<-등차수열의 합
				a[j + 1] = a[j]; //(4-1)조건에 의해 교환연산이 최대 n(n-1)/2회 
            }  
			else{
				break;  
            }
		}
		a[j + 1] = key;    //(5)외부루프에 의해 교환연산이 n-1회 일어남
	}
}

• 최악의 경우(역순으로 정렬되있음) =

      1*(n-1) + 2*(n(n-1)/2) + 1*(n-1) = n^2+n-2 =   O(n^2) 

         (2)           (4,4-1)          (5)

• 최선의 경우(이미 정렬되있음) =  

      1*(n-1) + (n-1) + 1*(n-1) = 3n-3 = O(n)

         (2)        (4)        (5)  

!!보통 못해도 이 정도의 성능을 보장한다는 의미로, 최악의 시간복잡도를 많이 사용한다!!

!!시간복잡도는 n의 최고 차수만 나타낸다!! 

                                Try! 실제로 횟수를 확인해보았다.(각 비교,교환 실행문마다 카운트 함..(n=5))

+추가 예제 

#include<iostream>
using namespace std;
int main() {
	int n = 5;
	int cnt = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cnt++;
		}
	}

	cout << cnt << endl;   //output: 25
    
    //앞서 말했듯이, 반복문을 중심으로 계산하면 되므로 시간복잡도는 n*n= n^2이 된다.

	cnt = 0;

	int i = 0,j=0;
	for (; i < n; i++) {
		for (; j < n; j++) {
			cnt++;
		}
	}
	cout << cnt << endl;   //output: 5
    //하지만, 반복문이 중첩되어 있더라도 언제나 두 반복문 범위의 곱은 아니라는 것에 유의하자.
    //위의 경우, 범위가 따로 놀기 때문에 cnt++가 포함된 루프만 생각해서 시간복잡도는 최대 n이다
	
    return 0;
}

다양한 시간복잡도

                                                        !! 전산학에서 log의 밑은 2이다 !!

그래프를 보면, 지수승으로 커지면 데이터의 양이 조금만 많아져도 그 연산량이 기하급수적으로 증가하는 것을 확인할 수 있다.  여기서 우리가 알고리즘을 짤 때, 시간복잡도를 고려해야 하는 이유가 드러난다. 

시간복잡도를 고려하는 이유

ex) 우리나라 인구 5000만명중에서 한 사람을 조회하는 알고리즘 2개가 있다. 

A알고리즘: O(log n)

B알고리즘: O(n^2)

->A알고리즘은 25번, B알고리즘은 2500000000000000번의 연산을 수행한다. 

...더보기

                       Try! 재미로 내 컴퓨터에서 1억번의 연산을 수행하고 시간을 측정해보았다. ㅎㅎ

 

 

 

즉 1억번에 0.2초 정도 걸렸다. 실행할 때마다 0.2~0.4초까지 나오더라..

참고로 실행환경은 인텔® 코어™ i5-7200U 프로세서(최고 3.10 GHz) 기준이다.

1Ghz는 1초에 10^9(10억)개의 단계를 처리할 수 있다고 한다.

그럼에도 저 정도의 시간이 나온건..다른 변수가 확실히 많다는 뜻..?

 

->A알고리즘은 1초도 안되는 시간이 걸린다. 

->B알고리즘은 120일 정도 걸린다..

하드웨어를 발전 속도가 매우 빠르기 때문에(무어의 법칙: 1년만에 반도체 집적률이 2배씩..)

소프트웨어의 발전 속도가 상대적으로 느리게 느껴지긴 하지만...

그럼에도 우리는 시간이란 소중한 자원을 낭비하지 않기 위해서 언제나 시간복잡도를 낮추기 위한 노력을 한다.

이러한 노력을 최적화라고 부른다.

Tip

추가로 알고리즘 문제를 풀 때 시간복잡도를 대략적으로 맞추는 방법을 소개하려 한다.

(백준,swea를 이제 막 풀기 시작한 분들을 위해서 쓴 글입니다! 참고해주세요ㅎㅎ)

여기서 시간제한 1초가 의미하는 것은, 내 코드를 실행했을 때 실행시간이 1초 내여야한다는 것을 뜻한다.

대부분의 환경에서 1억번 연산이 1초 정도 걸리기 때문에,

내 코드에 제일 큰 테스트케이스를 돌려도 연산이 1억번 내여야만 통과가 된다는 것이다.

그러므로, 문제를 풀기 전에 시간 제한과 입력 데이터의 수를 확인하고 나서

어느정도의 시간복잡도로 코드를 짜야겠다고 계획을 하고 코딩을 하는 것이 좋다. 

1. 시간 제한, 최대 입력 데이터의 크기를 확인하고 내가 짜야하는 코드의 시간복잡도를 생각한다.

-> 데이터의 크기가 10^8개일 떄, 시간복잡도가 n, log n 이어야지 1억번의 연산 내로 실행된다.

-> 데이터의 크기가 10^6개일 때, 시간복잡도가 nlog n이어야지 1억번의 연산 내로 실행된다.

.....

2.그에 맞춰서 코딩을 한다

3.가장 큰 테스트 케이스를 넣어본다.

4.출력 시간을 체감해본다 or 프로파일링 기능을 사용해서 측정해본다 or <time.h>를 추가해서 시간을 출력해본다

프로그램을 실행했을 때, 바로 출력값을 확인할 수 있다면 대부분 1초 내에 실행되는 코드이다.

하지만 조금 몇 초 기다려야지 값이 나온다면?? 코드 제출을 하면 '시간초과'를 볼 확률이 높다ㅎ

물론 콘솔에 뜨는 시간으로 추측하기엔 꽤나 부정확하지만.. 알고리즘을 잘못 짰을 때 가장 먼저 드러나는 부분

아닌가 싶다. 만약 이런 경우, 자신의 코드를 한번 되돌아보자!!!

+난 정말 제대로 짰는데 시간초과가 뜨거나 좀 느린 것 같다?싶으면 다음 경우를 확인해보자. 

1)디버깅 / 릴리즈 모드:

디버깅모드는 추적할 수 있는 정보가 실행파일 안에 들어가는 모드이다. 반면에 릴리즈모드는 프로그램을

배포하기 위해 컴파일하는 모드이다. 자질구레한 정보는 제외하기 때문에 컴파일 속도가 빠르다.

2) cin, cout으로 입출력을 반복:

cin, cout 보단 scanf,printf가 훨씬 빠르다. 

나는 집합의 표현 문제에서 이걸 경험했다..cin을 쓰면 시간초과가 뜬다.

3)그 외의 모든 반복문들..

초기화가 필요하면 memset을 사용하는 경우가 많지만, 만약 직접 이중포문으로 초기화를 한다면 이 부분이 시간을 많이 잡아먹을 수도 있다. 주요 알고리즘이 아니라고 대충 넘어간다면 안된다! 또한, 범위의 끝까지 갈 필요가 없는 반복문인데 끝까지 가게 만든 경우도 시간초과가 발생한다. 이런 경우 적절히 break를 걸어줘야 한다. 

나는 벽돌깨기와 보호필름에서 이런 문제를 경험했다. 

처음 시간복잡도에 대해 생각해보기에는 로마 숫자 만들기가 좋은 것 같다.

아직 많이 부족하기 때문에 틀린 부분이 있을수도 있어요..

댓글로 알려주시면 정말 감사할 것 같습니다ㅎㅎ

학교에서 이산수학 책으로만 시간복잡도 몇 번 계산해보고,

코딩하면서 써먹으려니 뜬구름 잡는 것 같은 기분을 느낀 적이 있습니다. 

조금 야매스럽기도 하지만! 저같은 초보자 분들에게 조금이나마 도움이 되었으면ㅎㅎㅎ