코딩 테스트 준비 회고
'여긴 어디... 나는 누구...'
Section 2는 나에게 있어서 늪과 같은 섹션인 것 같다. 자료구조와 알고리즘이 마무리되어 이제는 재미있는 주제들을 진행한다고하니 그나마 한숨 돌릴 수 있을거라는 기대가 든다.😭😭
의사코드와 탐욕알고리즘까지는 그래도 이해도가고 재미도 있었으나, 명절 후유증인지... 아니면 정말 수학적 사고가 많이 부족한 것인지... 순열, 조합, 최대공약수, 멱집합 등은 수포자로써 너무나도 생소한 개념들이었다... 찾아보니 중학교 수학이라는데... 나란 녀석... 질풍노도의 시기를 제대로 보냈었구나...
의사코드의 개념과 작성법
의사코드의 개념 및 필요성
의사코드는 프로그래밍 언어로 코드를 작성하기전에 우리가 쓰는 일상 언어로 프로그램이 작동하는 논리를 먼저 작성하는 것이다. 사람에게는 상상력이 존재, 컴퓨터는 0과 1만으로 이루어진 기계이기 때문에 컴퓨터에게 명령을 내리는 코드를 작성하기위해서는 기초적인 부분부터 구체적이고 상세하게 명령해야함
의사코드의 작성의 장점
- 시간이 단축된다.
- 디버깅에 용이하다.
- 프로그래밍 언어를 모르는 사람과 소통할 수 있다.
- 의사코드를 구체적으로 작성해야하는 이유
의사코드 작성 방법
- 다른 사람도 이해할 수 있는 자연어
- 자연어와 프로그램 언어의 조합
시간복잡도의 개념과 종류
시간 복잡도의 개념
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 소요되는 시간
- 효율적인 알고리즘 구현 = 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 구성
Big-O 표기법
Bing-O 표기법은 입력값 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼만큼 걸리는 가를 표기하는 방법.
- O(1) : constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않음
- O(n) : linear complexity라고 하며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것
- O(log n) : logarithmic complexity라고 하며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가짐.
- O(n^2) : quadratic complexity라고 하며, 력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것
- O(2^n) : exponential complexity라고 하며, Big-O 표기법 중 가장 느린 시간 복잡도를 가짐.
알고리즘 문제풀이 예시
아직 알고리즘 문제풀이를 잘하진 못 하지만, 그래도 기본부터 하나하나 익숙해져가는 과정이라고 생각하며, 묵묵하게 수행하고 있다.
문제해결 순서
문제를 이해해라!
- 주어진 조건(문제의 설명, 입출력예시, 제한사항 그리고 주의사항 등)을 토대로 문제가 무엇인지 이해하는 것이 필요
문제를 어떻게 해결할 수 있을지 전략을 세워라!
- 전체적인 그림을 그려가며, 전체적인 흐름을 파악
- 인간의 사고로 문제해결할 수 있어야 함
- 수도코드 작성
- 문제 해결 과정을 설명해보라
문제를 코드로 옮겨 보기
- 구상한 전략을 코드로 옮겨보기
- 구현한 코드에 대해 논의하고 구현한 코드의 최적화를 시도
위의 순서에 따라 나름대로 아래와 같이 문제해결을 하고 있다.
public class Solution {
public int boringBlackjack(int[] cards) {
// TODO:
// 3장 카드의 조합 중 소수인 개수
// 3장의 카드 조합 모두 나열하고,
// 3장의 카드 조합이 소수인지 확인하여 값을 반환
// 결과 변수 선언
int result = 0;
// 구현의 편의성을 위해 카드 배열의 길이 변수 선언
int LEN = cards.length;
// cards를 순회하면서 3장의 카드를 전체적인 경우의 수 뽑아냄
// 첫번째 카드 경우의 수
for (int i = 0; i < LEN; i++) {
// 두번째째 카드 경우의 수
for (int j = i+1; j < LEN; j++) {
// 세번째 카드 경우의 수
for (int k = j+1; k < LEN; k++) {
// 세카드의 조합이 합을 구하고
int sum = cards[i] + cards[j] + cards[k];
// sum이 소수인지 확인하고 소수이면 result+1
if(isPrime(sum)) result++;
}
}
}
return result;
}
// 소수를 구하는 메서드를 구현
public boolean isPrime(int sum) {
for (int l = 2; l <= Math.sqrt(sum); l++) {
if(sum % l == 0) return false;
}
return true;
}
}아직 부족한 점이 너무나도 많지만, 묵묵히 따라가다보면 어느샌가 성장해있겠지... 오늘도 나쁜 머리 굴리느라 고생 많았던 나에게 셀프 칭찬을 해본다.
"화이팅!! 잘 하고 있다~"
