알고리즘 코딩테스트 핵심이론 강의 - 시간복잡도 (Java) 1:17 시간 복잡도 개념 1:17 시간 복잡도 유형 실제를 문제를 보면 '시간제한'이 있음, ex. 시간제한 2초 = 2억번 연산 안에 답이 나와야한다, 알고리즘 마다 시간 복잡도를 가지고 있다, ex. 버블 정렬 = O(n2), 병합 정렬 = O(nlogn) 8:25 시간 복잡도 활용하기 1. 알고리즘 선택의 기준으로 사용하기 10:02 - 연산 횟수 계산 방법 최대 데이터 크기를 확인 후, 알고리즘을 판단 2. 시간 복잡도를 바탕으로 코드 로직 개선하기(성능) 13:19 - 시간 복잡도 도출 기준 내 코드의 시간 복잡도를 따질 때는 가장 많이 중첩되는 중첩문을 기준으로 봐야함,
냥충이님 안녕하세요. 알고리즘 시간 복잡도에서 log는 이진로그를 사용하는 것이 일반적입니다. ^^ 아마도 병합정렬 핵심이론을 보시면 조금 더 자연스럽게 이해가 되실 것 같은데 병합정렬의 원리를 생각해보면 이진탐색과 매우 흡사한 것을 알 수 있습니다. 예를들어 8개의 원소를 정렬한다고 하였을 때 4 1 6 8 7 5 3 2 14 68 57 23 1468 2357 12345678 병합을 하는 루프가 3번 도는 것을 알 수 있습니다. 2개씩 병합 => 4개씩 병합 => 8개 병합 즉 log8(이진로그) => 3 이렇게 해석이 됩니다. 그리고 각 루프에서는 n개의 데이터를 접근합니다. 때문에 n개의 데이터를 병합정렬도 돌린다고 하면 nlogn의 시간복잡도를 갖는 것입니다. 꼭 병합정렬이 아니더라고 아주 특수한 상황이 아니고서는 저는 일반적으로 시간복잡도에서 로그는 이진로그라고 생각했던것 같습니다. 감사합니다. 좋은하루 되세요 :)
드디어 자바편 책에 있는 문제 전부 1회독을 했습니다 ㅎㅎ 궁금한 게 있는데 제가 코테에만 시간을 많이 투자하기 여유가 없을 거 같은데 뒤 유형들 풀다 보면 기억이 가물하기도 하고 이론은 기억나지만 디테일한 구현이 생각 안나서 까먹는 부분이 있어서 책에 있는 문제들을 N회독을 할까 생각중인데 N회독을 해서 이론과 풀어본 문제를 확실하게 가져가는 게 좋을까요 아니면 새로운 문제를 더 많이 풀어보는게 좋을까요? 선생님의 의견이 궁금합니다!
안녕하세요 흐규규님 반갑습니다. 완전 개인 의견이고 취향이니 참고만 부탁드립니다. ! 만약 문제들을 코딩까지 직접 다해서 풀어보신것을 가정으로 하면 새로운 문제를 계속 접하시면서 공부하시는 것도 방법이 될 것 같습니다. 예를들어 같은 바이너리 서치를 이용한다고 하여도 문제마다 약간씩 추가적인 아이디어나 변형을 요구하는 경우도 꽤 있어서 이런것을 많이 경험해보시면 좋지 않을까 생각합니다. 만약 직접 코딩해보신것 까지는 아니고 내용을 읽고 이해하신것이라면 실제로 코딩해보시는 것도 추천드립니다. 논리적으로 이해한것과 프로그래밍 언어로 표현하는 것은 또 다른 부분일 수 있기 때문입니다. 그런데 이건 사실 취향 차이여서 ^^;; 사람마다 다를 것 같습니다. 코테도 그렇고 다른 준비하시는 것도 다 잘되시길 바랍니다. 즐거운 하루되세요 :) 감사합니다.
까만괭님 안녕하세요. 반갑습니다 :) 먼저 for문의 경우 i값이 0~99까지 순차적으로 탐색을 하게 됩니다. 그리고 findNumber 값의 경우 Math.random()의 리턴 값이 0.0이상 1.0미만의 값을 주기 때문에 여기에 * 100을 하게 되면 랜덤 값이긴 하지만 범위를 0~99 사이로 제한하게 됩니다. 때문에 불일치하는 경우는 생기지 않을 것 같습니다. 도움이 되셨으면 좋겠습니다. :) 즐거운 하루 되세요!
@@까만괭 안녕하세요!! 아마도 제가 의미 파악을 정확하게 하지 못한것 같습니다.~ i는 반복문에서 0~99까지 순차적으로 증가하기 때문에 랜덤값과 i는 1번은 무조건 필연적으로 일치하게 되어있습니다. 그리고 보통 이러한 작업을 무한대로 반복 한다고 하였을때 평균적으로 50번정도의 탐색후 찾게 됩니다. 그리고 이러한 원리로 세타 값이 50(N/2)이 됩니다. 음 아마도 이 답변도 정확하게 원하시는 답변이 아닐 수도 있을 것 같긴합니다. ^^;;; 즐거운 저녁 되세요!!
유진초이님 안녕하세요 :) 상수는 기본적으로 무시된다가 대 전재이지만 상황에 따라 약간 다를 수 있어 그때그때 복잡도를 적용해보면 더 정확할 것 같습니다. 문제 상황에서 보통 N의 최대 크기가 100, 200 정도라면 3이라는 값이 영향도가 크겠지만 N이 10000이라고 예를 들면 N*N => 1억 => 1초 정도의 시간, 3N*N => 3억 => 3초 정도의 시간의 차이가 나게 됩니다. 언뜻 생각했을때는 차이 많이나는데? 생각할 수 있는데... N*N*N*과 비교하면 큰 차이가 아닙니다. 아주 높은 수준의 대회나 Fail Pass의 형태가 아닌 속도 줄이기등의 특수한 상황이 아닌 일반적인 코딩테스트에서는 시간제한이 1초가 주어졌을 경우 정답 코드가 0.98초만에 돈다거나 하는 상황은 거의 없습니다. ( 컴퓨터 성능이나 변수가 존재하기 때문입니다.) 예를들어 시간제한이 0.5초인데 N이 최대 10000까지 될 수 있다면 N*N 시간복잡도 알고리즘으로 문제를 풀면 무조건 탈락이고 N이 1000개까지라면 N*N시간복잡도로 풀게 되어도 문제가 없을 것 같습니다. => 실제로 이 경우에 3N*N의 경우라고해도 3*1000*1000 => 3,000,000이 되고 50,000,000 보다는 훨씬 작기 때문에 3은 거의 무시가 되는 것입니다. ( 자리수 자체가 차이가 나게 되죠 ^^;;) 다만 N이 작은 경우에는 상수도 그만큼 영향도가 커지게 되기 때문에 위처럼 시간복잡도를 따져보는 것을 많이 연습해보시면 도움이 되시지 않을까 싶습니다. ! 감사합니다. 좋은하루 되세요 :)
Loup님 안녕하세요. 반갑습니다. :) 이 부분은 개개인 마다 영향도가 너무 다릅니다. 때문에 저도 의견을 드리기 매우 조심스러운 부분이라.. 지나가는 한명의 의견정도로 참고만 부탁드립니다. 파이썬의 경우 확실히 몇 가지 코딩을 편하게 해주는 요소들이 있기는 합니다. 그리고 처음 막 공부를 시작의 경우는 이 부분이 좀 크게 느껴 질 수 있고 꽤 영향을 줄 수 있다고 생각합니다. 다만 궁극적으로 이렇게 편하게 제공해주는 부분 역시 동작 원리를 알고 써야 하고, 더불어.. 좀 난이도가 있는 문제에서는 (정말 특정 문제를 제외하고) 언어로 엄청 큰 차이가 나는지는 물음표입니다. 제 개인적으로는 C
병주님 안녕하세요. 반갑습니다 ~ 군데 군데 자연스럽게 다루고 있는 곳이 있는데 아마도 아래 영상 참고하여 보시면 도움이 될 것 같습니다. 핵심이론 : DFS -> ruclips.net/video/lFtQnOhKnr0/видео.html 문제풀이 : 연결요소의 개수 구하기 => ruclips.net/video/Y2kHlj7xqfU/видео.html 감사합니다. 좋은 하루 되세요 :)
병주님 안녕하세요. 반갑습니다. 음.... 그건 아마도 개인마다 다를 것 같은데, 제 생각은 DFS, 재귀함수, 백트래킹, DP에서의 top-down으로 푸는 방식등이 거의 같은 원리? 말이라는 생각이 들고, 관련 문제들을 풀다보면 자연스럽게 이해가 되지 않을까 싶습니다. 좋은 하루 되세요 ~
먼저 제가 말씀드리는 것이 정답은 아니고 개인의 의견 정도로 이해해주시면 감사드리겠습니다. 결론적으로는 공부의 목표가 무엇인지에 따라 다를 것 같습니다. 두개의 영역이 생각보다는 다른 분야라고 느껴집니다. 겹치는 부분이 문법적인 부분인데 이 부분은 중요한 기초 부분은 맞지만 실제 본격적인 공부 영역은 서로 좀 다르다고 생각되기 때문입니다. 제 생각으로는 시간적 여유가 있어서 차근히 이해를 하면서 두개를 같이 공부할 수 있으면 같이 공부하면 좋을 것 같고 특정 목적으로 둘 중 하나가 빠르게 결과(성과)가 나와야 하는 것이면 하나의 집중하는게 좋지않을까 하는 의견입니다. 좀 답변이 모호한것 같아 죄송합니다. ^^;; 즐거운 저녁 되세요~
![BLACK BAG - Official Trailer [HD] - Only in Theaters March 14](http://i.ytimg.com/vi/Du0Xp8WX_7I/mqdefault.jpg)
진작에 강의를 들을 걸 그랬네요. 어렴풋이 이해만 하던게 강의를 들으니 명확해졌어요
알고리즘 코딩테스트 핵심이론 강의 - 시간복잡도 (Java)
1:17 시간 복잡도 개념
1:17 시간 복잡도 유형
실제를 문제를 보면 '시간제한'이 있음,
ex. 시간제한 2초 = 2억번 연산 안에 답이 나와야한다,
알고리즘 마다 시간 복잡도를 가지고 있다,
ex. 버블 정렬 = O(n2), 병합 정렬 = O(nlogn)
8:25 시간 복잡도 활용하기
1. 알고리즘 선택의 기준으로 사용하기
10:02 - 연산 횟수 계산 방법
최대 데이터 크기를 확인 후, 알고리즘을 판단
2. 시간 복잡도를 바탕으로 코드 로직 개선하기(성능)
13:19 - 시간 복잡도 도출 기준
내 코드의 시간 복잡도를 따질 때는 가장 많이 중첩되는 중첩문을 기준으로 봐야함,
오탈 찾고 이해가안되서 질문을 드렸는데 영상까지 만들어주시고! 감사합니다!!
minu님! 관심 가져주셔서 감사드리고, 도움이 되셨으면 좋겠습니다 :)
강의 정말 감사합니다 :D
여기서 궁금한게 병합 정렬 시간 복잡도 계산할때 log(1,000,000) 에 따로 밑이 2라고 나와있지는 않은데 왜 2로 계산하는 걸까요? ㅠㅠ
냥충이님 안녕하세요. 알고리즘 시간 복잡도에서 log는 이진로그를 사용하는 것이 일반적입니다. ^^
아마도 병합정렬 핵심이론을 보시면 조금 더 자연스럽게 이해가 되실 것 같은데
병합정렬의 원리를 생각해보면 이진탐색과 매우 흡사한 것을 알 수 있습니다. 예를들어 8개의 원소를 정렬한다고 하였을 때
4 1 6 8 7 5 3 2
14 68 57 23
1468 2357
12345678
병합을 하는 루프가 3번 도는 것을 알 수 있습니다. 2개씩 병합 => 4개씩 병합 => 8개 병합
즉 log8(이진로그) => 3 이렇게 해석이 됩니다. 그리고 각 루프에서는 n개의 데이터를 접근합니다.
때문에 n개의 데이터를 병합정렬도 돌린다고 하면 nlogn의 시간복잡도를 갖는 것입니다.
꼭 병합정렬이 아니더라고 아주 특수한 상황이 아니고서는 저는 일반적으로 시간복잡도에서 로그는 이진로그라고 생각했던것 같습니다.
감사합니다. 좋은하루 되세요 :)
@@codingtest 아~ 이제 좀 이해가 갑니다 감사합니다! ^^
드디어 자바편 책에 있는 문제 전부 1회독을 했습니다 ㅎㅎ 궁금한 게 있는데 제가 코테에만 시간을 많이 투자하기 여유가 없을 거 같은데 뒤 유형들 풀다 보면 기억이 가물하기도 하고 이론은 기억나지만 디테일한 구현이 생각 안나서 까먹는 부분이 있어서 책에 있는 문제들을 N회독을 할까 생각중인데 N회독을 해서 이론과 풀어본 문제를 확실하게 가져가는 게 좋을까요 아니면 새로운 문제를 더 많이 풀어보는게 좋을까요? 선생님의 의견이 궁금합니다!
안녕하세요 흐규규님 반갑습니다.
완전 개인 의견이고 취향이니 참고만 부탁드립니다. !
만약 문제들을 코딩까지 직접 다해서 풀어보신것을 가정으로 하면
새로운 문제를 계속 접하시면서 공부하시는 것도 방법이 될 것 같습니다.
예를들어 같은 바이너리 서치를 이용한다고 하여도 문제마다 약간씩 추가적인 아이디어나 변형을 요구하는 경우도 꽤 있어서
이런것을 많이 경험해보시면 좋지 않을까 생각합니다.
만약 직접 코딩해보신것 까지는 아니고 내용을 읽고 이해하신것이라면 실제로 코딩해보시는 것도 추천드립니다.
논리적으로 이해한것과 프로그래밍 언어로 표현하는 것은 또 다른 부분일 수 있기 때문입니다.
그런데 이건 사실 취향 차이여서 ^^;; 사람마다 다를 것 같습니다.
코테도 그렇고 다른 준비하시는 것도 다 잘되시길 바랍니다.
즐거운 하루되세요 :)
감사합니다.
항상 감사합니다.😊
안녕하세요 좋은 강의 잘듣고 있습니다 :)
질문사항이 있는데요 시간 복잡도 세타 설명하실때 평균 50이라고 하셨는데요, 50번내에 값을 찾을 수 있다고 하셨는데 findNumber가 랜덤 값이고 i는 순차적인 값인데 if문에 조건에 불일치 하는 경우도 있지 않나요??
까만괭님 안녕하세요. 반갑습니다 :)
먼저 for문의 경우 i값이 0~99까지 순차적으로 탐색을 하게 됩니다.
그리고 findNumber 값의 경우
Math.random()의 리턴 값이 0.0이상 1.0미만의 값을 주기 때문에 여기에 * 100을 하게 되면 랜덤 값이긴 하지만 범위를 0~99 사이로 제한하게 됩니다.
때문에 불일치하는 경우는 생기지 않을 것 같습니다.
도움이 되셨으면 좋겠습니다. :)
즐거운 하루 되세요!
i가 0부터 순차적으로 증가하는데 랜덤값이 딱 일치하는 경우가 확률적으로 발생하지 않을까 궁금했습니다 :)
@@까만괭 안녕하세요!!
아마도 제가 의미 파악을 정확하게 하지 못한것 같습니다.~
i는 반복문에서 0~99까지 순차적으로 증가하기 때문에 랜덤값과 i는 1번은 무조건 필연적으로 일치하게 되어있습니다.
그리고 보통 이러한 작업을 무한대로 반복 한다고 하였을때 평균적으로 50번정도의 탐색후 찾게 됩니다. 그리고 이러한 원리로 세타 값이 50(N/2)이 됩니다.
음 아마도 이 답변도 정확하게 원하시는 답변이 아닐 수도 있을 것 같긴합니다. ^^;;;
즐거운 저녁 되세요!!
3N * N인 중첩반복문의 경우 에서도 상수 3은 무시되나요?
유진초이님 안녕하세요 :) 상수는 기본적으로 무시된다가 대 전재이지만
상황에 따라 약간 다를 수 있어 그때그때 복잡도를 적용해보면 더 정확할 것 같습니다.
문제 상황에서 보통 N의 최대 크기가 100, 200 정도라면 3이라는 값이 영향도가 크겠지만
N이 10000이라고 예를 들면 N*N => 1억 => 1초 정도의 시간,
3N*N => 3억 => 3초 정도의 시간의 차이가 나게 됩니다.
언뜻 생각했을때는 차이 많이나는데? 생각할 수 있는데... N*N*N*과 비교하면 큰 차이가 아닙니다.
아주 높은 수준의 대회나 Fail Pass의 형태가 아닌 속도 줄이기등의 특수한 상황이 아닌 일반적인
코딩테스트에서는 시간제한이 1초가 주어졌을 경우 정답 코드가 0.98초만에 돈다거나 하는 상황은 거의 없습니다. ( 컴퓨터 성능이나 변수가 존재하기 때문입니다.)
예를들어 시간제한이 0.5초인데
N이 최대 10000까지 될 수 있다면
N*N 시간복잡도 알고리즘으로 문제를 풀면 무조건 탈락이고
N이 1000개까지라면 N*N시간복잡도로 풀게 되어도 문제가 없을 것 같습니다.
=> 실제로 이 경우에 3N*N의 경우라고해도 3*1000*1000 => 3,000,000이 되고 50,000,000 보다는 훨씬 작기 때문에 3은 거의 무시가 되는 것입니다. ( 자리수 자체가 차이가 나게 되죠 ^^;;)
다만 N이 작은 경우에는 상수도 그만큼 영향도가 커지게 되기 때문에 위처럼 시간복잡도를 따져보는 것을 많이 연습해보시면 도움이 되시지 않을까 싶습니다. !
감사합니다. 좋은하루 되세요 :)
@@codingtest 혹시 50,000,000 이라는 숫자는 시간제한이 0.5초라서 나온 숫자인걸까요?
안녕하세요^^- 네 언어마다 조금 다르지만 일반적으로 1초 시간제한 기준이 1억번 연산정도로 보기 때문입니다 :)
@@codingtest 감사합니다!
1강 완강~
자바를 사야하는데 C++을 사버렸어요... 교환하고 싶다 ㅠ
앗... 그러셨군요 ㅠㅠ 하지만 언어에 상관없이 알고리즘 이론 부분의 원리는 동일하기 때문에 화이팅하십시오!!
@@codingtest 티어 낮은 문제부터 쭉 풀고, 한 바퀴 다 돈 다음에 푸는게 나을가요 아니면 정주행하는게 나을까요?
자바 주로 사용하는 백엔드 개발자 지망생인데 코테를 위해서 파이썬을 공부할지 말지 고민되네요 편한 기능이 너무 많아서 쓰고는 싶은데 할때마다 새로워요 ㅠ 자바로 그냥 해도 크게 지장 없을까요
Loup님 안녕하세요. 반갑습니다. :)
이 부분은 개개인 마다 영향도가 너무 다릅니다.
때문에 저도 의견을 드리기 매우 조심스러운 부분이라.. 지나가는 한명의 의견정도로 참고만 부탁드립니다.
파이썬의 경우 확실히 몇 가지 코딩을 편하게 해주는 요소들이 있기는 합니다.
그리고 처음 막 공부를 시작의 경우는 이 부분이 좀 크게 느껴 질 수 있고 꽤 영향을 줄 수 있다고 생각합니다.
다만 궁극적으로 이렇게 편하게 제공해주는 부분 역시 동작 원리를 알고 써야 하고,
더불어.. 좀 난이도가 있는 문제에서는 (정말 특정 문제를 제외하고) 언어로 엄청 큰 차이가 나는지는 물음표입니다.
제 개인적으로는 C
답변 감사합니다~ 책사서 열심히 해보겠습니다ㅎㅎ
강사님 구매 전에 여쭙습니다. 혹시 재귀함수에 대해서도 다루고 있나요? 목차에 없어서 문의드립니더
병주님 안녕하세요.
반갑습니다 ~ 군데 군데 자연스럽게 다루고 있는 곳이 있는데 아마도
아래 영상 참고하여 보시면 도움이 될 것 같습니다.
핵심이론 : DFS -> ruclips.net/video/lFtQnOhKnr0/видео.html
문제풀이 : 연결요소의 개수 구하기 => ruclips.net/video/Y2kHlj7xqfU/видео.html
감사합니다. 좋은 하루 되세요 :)
@@codingtest 감사합니다! 혹시 DFS 쪽 공부하면 백트래킹은 자연스럽게 해결될까요?
병주님 안녕하세요. 반갑습니다.
음.... 그건 아마도 개인마다 다를 것 같은데,
제 생각은 DFS, 재귀함수, 백트래킹, DP에서의 top-down으로 푸는 방식등이 거의 같은 원리? 말이라는 생각이 들고,
관련 문제들을 풀다보면 자연스럽게 이해가 되지 않을까 싶습니다.
좋은 하루 되세요 ~
자바를 처음공부하게되었는데 알고리즘과 같이 시작해도될까요?
먼저 제가 말씀드리는 것이 정답은 아니고 개인의 의견 정도로 이해해주시면 감사드리겠습니다.
결론적으로는 공부의 목표가 무엇인지에 따라 다를 것 같습니다.
두개의 영역이 생각보다는 다른 분야라고 느껴집니다.
겹치는 부분이 문법적인 부분인데 이 부분은 중요한 기초 부분은 맞지만
실제 본격적인 공부 영역은 서로 좀 다르다고 생각되기 때문입니다.
제 생각으로는
시간적 여유가 있어서 차근히 이해를 하면서 두개를 같이 공부할 수 있으면 같이 공부하면 좋을 것 같고
특정 목적으로 둘 중 하나가 빠르게 결과(성과)가 나와야 하는 것이면 하나의 집중하는게 좋지않을까 하는 의견입니다.
좀 답변이 모호한것 같아 죄송합니다. ^^;;
즐거운 저녁 되세요~