코딩테스트/알고리즘
🧑🏻💻 하루코딩 님의 Do it! 알고리즘 코딩테스트 강의(인프런)를 듣고 정리한 내용입니다. 01. 구간 합 ➡️ 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 ➡️ 코딩 테스트에서 사용 빈도가 높으니 알아두는 것이 좋음! ✔️ 구간 합의 핵심 이론 구간 합 알고리즘을 활용하기 위해서는 먼저 합 배열을 구해야 한다. 합 배열의 정의는 다음과 같다 → S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] → 즉 배열 A가 있을 때 합 배열 S[i]는 A[0]부터 A[i] 사이의 합을 말하는 것이다. → 합 배열 S를 만드는 공식 : S[i] = S[i-1] + A[i] 구간 합을 구하는 공식 → S[j] - S[i-1] // i 에서 ..
🧑🏻💻 하루코딩 님의 Do it! 알고리즘 코딩테스트 강의(인프런)를 듣고 정리한 내용입니다. https://www.acmicpc.net/problem/1546 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net 01. 문제 분석하기 만약 아래 예제를 가지고 생각을 해 본다면 세 가지 주어진 점수 중 최댓값은 80이다. 그래서 각각 점수를 고쳐 본다면 40/80*100 = 50 80/80*100 = 100 60/80*100 = 75 이러한 결과가 나올 것이고 이들의 총 평균을 구하면 75가 나오게 된다. ..
🧑🏻💻 하루코딩 님의 Do it! 알고리즘 코딩테스트 강의(인프런)를 듣고 정리한 내용입니다. https://www.acmicpc.net/problem/11720 11720번: 숫자의 합 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. www.acmicpc.net 1. 문제 설명 만약 예제 입력값이 숫자 5개, 공백 없이 주어진 숫자가 5개 54321 라면 5 + 4 + 3+ 2 + 1을 더해서 15를 출력해야 한다. 숫자 54321에서 각각의 숫자를 뽑아내기 위해서는 54321 / 10000 = 5, 54321 % 10000 = 4321, 4321 / 1000 = 4, 4321 % 1000 = 321 ... 이런 연산을 반복하여 뽑아내야 한다..
🧑🏻💻 하루코딩 님의 Do it! 알고리즘 코딩테스트 강의(인프런)를 듣고 정리한 내용입니다. 03-1. 배열과 리스트 ➡️ 두 자료구조의 특징을 정확하게 이해하고 문제가 요구하는 조건에 따라 적절하게 선택하여 사용하는 것이 중요하다. ✔️ 배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조이다. 인덱스를 통해 참조할 수 있다는 것이 가장 큰 특징이라고 할 수 있다. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. → 값을 삭제하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다. 배열의 크기는 선언할 때 지정할 수 있으면 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 구조가 간단하므로 코딩테스트에서 많이 사용한다. ✔️ 리스트 값과 포인터를 묶은 노드..
🧑🏻💻 하루코딩 님의 Do it! 알고리즘 코딩테스트 강의(인프런)를 듣고 정리한 내용입니다. 02. 코드의 논리 오류를 잡는 방법 - 디버깅 디버깅(Debugging)이란? : 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정이다. : 문법 오류는 컴퍼일러가 자동으로 찾아주기 때문에 문제가 되지 않지만 논리 오류는 코드가 사용자의 의도와 다르게 동작하는 것이며 다양한 형태로 발생하기 때문에 찾기가 쉽지 않다. 그렇기 때문에 디버깅이 필요하다. 디버깅하는 법 코드에서 디버깅하고자 하는 줄에 중단점(break point)을 설정한다. (여러 개 설정 가능) IDE의 디버깅 기능을 실행하면 코드를 한 줄씩 실행하거나 다음 중단점까지 실행할 수 있으며 이 과정에서 추적할 변숫값도 지정할 수 ..
🧑🏻💻 하루코딩 님의 Do it! 알고리즘 코딩테스트 강의(인프런)를 듣고 정리한 내용입니다. 01. 알고리즘 선택의 기준이 되는 시간 복잡도 ➡️ 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 의미한다. ➡️ 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다. (만약 시간제한이 2초라면 2억 연산 안에 답이 나와아한다는 것) ✔️ 시간 복잡도 유형 빅-오메가(Ω(n)) : 최선일 때의 연산 횟수를 나타내는 표기법 빅-세타(Θ(n)) : 보통일 때의 연산 횟수를 나타내는 표기법 빅-오(O(n)) : 최악일 때의 연산 횟수를 나타내는 표기법 ※ 실제 코딩 테스트에서 염두해야 할 표기법은? 빅-오(O(n)) → 다양한 테스트 케이스를 수행해 모든 케이스를 통과..
