-
항해 99 5기 TIL_55항해 99 2022. 3. 6. 02:56
▶ Today I Learned
<알고리즘>
[이항 계수1]
소요시간: 50분
해결 여부: 해결
백준 11050번
https://www.acmicpc.net/problem/11050
풀이코드
// 설명용 코드 // 이항계수 공식 대입 및 팩토리얼 구현 필요 // 문제에서는 0<=k<=n 라는 조건이 있으며 1<=n<=10 // 만약 k < 0 || n < k 라면 결과값 0 // n!/k!(n-k)!라는 결과를 구해야 함 let n = 5 let k = 2 // 팩토리얼 구하기 factorial = (num) => { let result = 1 for(let i = 1 ; i < num + 1 ; i++) { result = result*i } return result } console.log(factorial(n)/(factorial(k)*factorial(n-k)))
// 백준용 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ') let n = input[0]/1 let k = input[1]/1 factorial = (num) => { let result = 1 for(let i = 1 ; i < num + 1 ; i++) { result = result*i } return result } console.log(factorial(n)/(factorial(k)*factorial(n-k)))
공식을 적용하는 건 사실 굉장히 간단했다.
여기서 뿌듯했던 것은 입력 값을 받아오는 부분을 복사하지 않았다는 것이다.
input 값을 구현하는 식내 함수들에 대해서 100% 이해한 것은 아니지만 각각의 요소가 어떤 역할을 하는지는
예전에 파악해두었고, 백준을 풀다보니 어떻게 짜야하는 지 기억이 나서 직접 짜보았다.
다음에 제출할 때도 복사하지 않고 직접 써넣어 보아야 겠다.
뿌듯쓰 :)
+ 이항 계수에 대해 배웠던 적은 없어서 간단히 자료를 참고해보았다.
https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98#:~:text=%EC%A1%B0%ED%95%A9%EB%A1%A0%EC%97%90%EC%84%9C%2C%20%EC%9D%B4%ED%95%AD%20%EA%B3%84%EC%88%98(%E4%BA%8C,%EC%97%86%EB%8A%94)%20%EC%A1%B0%ED%95%A9%EC%9D%98%20%EA%B0%80%EC%A7%93%EC%88%98%EC%9D%B4%EB%8B%A4.
팩토리얼의 개념이 나오는데 다행히 이는 배운 적이 있어 식 자체의 이해가 어렵지는 않았다.
이항계수의 쓰임새에 대해 찾아봤는데 통계학적으로 이항 분포라는 곳에 쓰이는 듯 하다.
복권에 당첨되는 것 혹은 당첨되지 않는 것, 시험에 통과하는 것, 떨어지는 것, 혹은 새로운 약물이 나왔을 때 약물이 질병을 치료하는 것,
치료하지 못하는 것 처럼 두 가지 결과만 존재하는 경우 사용하는 개념으로 보인다.
참고자료:
https://ko.wikipedia.org/wiki/%EB%B2%A0%EB%A5%B4%EB%88%84%EC%9D%B4_%EB%B6%84%ED%8F%AC
<CS>
[Array.length의 시간 복잡도]
Array.length의 시간 복잡도는 배열 내 요소의 갯수, 빅오표기법으로 나타내면 O(n)이라고 할 수 있다. (n은 배열 내 요소의 갯수)
보통 많이 사용하는 빅오 표기법에 따라 반복문내 기본적인 연산의 횟수만을 고려한다면
배열 내 요소를 한 번 순회하는 것이 전부이기 때문이다.
(기본적인 연산이란 더 이상 쪼갤 수 없는 최소한의 연산단위이다.)
cf) 시간복잡도란 무엇인가?
시간 복잡도란 특정 알고리즘이 어떤 알고리즘을 해결하는 데 걸리는 시간을 나타냄
cf) 시간 복잡도를 나타내는 빅오 표기법이란 무엇인가?
빅오 표기법은 전체 수행 시간에 큰 영향을 미치지 않는 상수 부분은 무시하고 반복문의 반복 수나 기본적인 연산만 고려하는 것,
절대적인 시간은 없고 반복문의 수행 횟수, 대입(변수할당), 사칙연산, 대소 비교와 같은 기본적인 연산의 횟수로 비교한다.
이때 반복을 한다면 최선의 케이스, 평균 케이스, 최악의 케이스가 있는데 그 중 보통 최악의 케이스를 계산한다.
ex) 배열의 길이가 n인 배열에서 특정한 값을 찾는 경우, 그 값이 바로 앞에 있을 경우 최선의 케이스는 1, 평균 케이스는 n/2, 최악의 케이스는 n
알고리즘의 시간은 직접 파일을 실행시켜서 절대적인 시간을 측정할 수도 있다.
그러나 컴파일러, 운영체제, 프로그래밍 언어 등 실행 환경이나 문자열 구현, 함수 인자 전달방식에 따라 달라질 수 있기 때문에
이는 적합하지 않다는 의견이 많다.
- 시간복잡도에 대해 참고할 것
- 시간 복잡도가 높다 => 입력의 크기가 증가할 때 알고리즘의 수행 시간이 더 빠르게 증가한다, 그래서 비효율적이라 할 수 있음
- 시간 복잡도가 낮다고 해서 언제나 더 빠르게 동작하는 것은 아님 (상수, 선형, 로그, 다항 그래프 등 다양한 종류의 그래프가 있고 증감의 차이가 다르기 때문)
- 입력의 크기가 낮은 알고리즘은 입력이 커질 수록 효율적 (입력이 낮은 경우에는 어떤 종류의 시간 복잡도 그래프 이든 비슷한 결과이기 때문), 입력의 크기가 매우 작을 경우 시간 복잡도는 큰 의미가 없을 수도 있음
- 시간 복잡도 계산에는 가장 큰 영향을 미치는 알고리즘 하나만 시간복잡도를 계산함 (반복문이 하나가 있으나 2개가 있으나 수십개가 있으나 O(n)임)
- 시간복잡도 계산에서는 정확한 값을 산출하는 것이 아니라 근사치를 계산함
예시 코드
for(int i=0;i<input;i++){ for(int j=i;j<input;j++{ printf("hello"); } }
참고자료
https://eunguru.tistory.com/48
https://yurimkoo.github.io/algorithm/2020/05/09/time-complexity-1.html
https://coding-factory.tistory.com/608
[구조할당 분해]
객체나 배열에 저장된 데이터 전체가 아닌 일부만 필요한 경우가 있음,
이럴 때 객체나 배열을 변수로 '분해’할 수 있게 해주는 특별한 문법인 구조 분해 할당(destructuring assignment) 사용
예시
// 이름과 성을 요소로 가진 배열 let arr = ["Bora", "Lee"] // 구조 분해 할당을 이용해 // firstName엔 arr[0]을 // surname엔 arr[1]을 할당함 let [firstName, surname] = arr; alert(firstName); // Bora alert(surname); // Lee
배열이나 객체의 요소를 직접 변수에 할당할 때 보다 코드 양이 줄어든다는 장점이 있음
// 구조 분해 할당 let [firstName, surname] = arr; // vs // 배열의 값을 직접 할당 let firstName = arr[0]; let surname = arr[1];
쉼표를 사용하여 필요하지 않은 요소를 버릴 수도 있음
// 두 번째 요소는 필요하지 않음 let [firstName, , title] = ["Julius", "Caesar", "Consul", "of the Roman Republic"]; alert( title ); // Consul
cf) 이것은 객체나 배열의 값을 복사한 후 변수로 분해해준다는 것이지 분해대상을 수정 또는 파괴한다는 의미는 아님
참고자료
https://ko.javascript.info/destructuring-assignment
▶ 느낀 점
수학 공부를 할 수 있는 시간이 있다면 기존에 배웠던 것 + 기하와 벡터, 확률과 통계 등 이과의 수학도 배워보고 싶다.
논리적인 사고에 큰 보탬이 될 것 같다.
+
CS 공부를 위하여 또 다른 스터디를 새로 시작했다.
다시 CS를 제대로 공부하니 기본기가 탄탄한 개발자가 되는 기분이다.
튼튼한 기반이 있다면 분명 그것을 발판 삼아 더 멀리 나아갈 수 있을 것이다.
+
채팅을 위해 socket.io와 web RTC SFU 방식 코드를 연구하였지만 오늘은 큰 수확이 없었다.
쉬는 타임에 web rtc에 대해서 좀 더 공부하고 팀원 분과 협업하여 진행해 보아야겠다.
▶ 공부 시 참고 링크들
https://jinbroing.tistory.com/126
https://developer.mozilla.org/ko/docs/Web/API/WebRTC_API/Signaling_and_video_calling
https://millo-l.github.io/WebRTC-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-1-N-SFU/#github
cs공부 시 참고하기 좋은 링크 1
cs공부 시 참고하기 좋은 링크 2
https://github.com/JoMingyu/Lets-Study
'항해 99' 카테고리의 다른 글
항해 99 5기 WIL_8 (0) 2022.03.07 항해 99 5기 TIL_56 (0) 2022.03.06 항해 99 5기 TIL_54 (0) 2022.03.05 항해 99 5기 TIL_53 (0) 2022.03.04 항해 99 5기 TIL_52 (0) 2022.03.03