패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 강의 1주차

     알고리즘을 마주한 나(ㅎㅎ)

 

 

알고리즘 공부를 해야 하는데, 기본 지식이 많이 부족한 것 같아 강의를 수강해야겠다고 마음먹었다.

마침 패스트캠퍼스에서 자바를 사용한 알고리즘 강의가 있길래 커리큘럼을 확인하곤 마음에 들어 수강 버튼을 눌렀다.

 

 

나의 공부 방법은 대략

1. 챕터 별 개념 강의 듣기 (챕터 시작 시 개념 강의부터 시작한다) 

2. 해당 개념을 활용한 문제 풀기 (강의를 듣기 전 먼저 푼다)

3. 문제 해설 강의 듣기

4. 다시 한번 더 풀어보기

5. 프로그래머스에서 비슷한 문제유형 풀기

이다.

 

 

현재 진행 상황은 문자열과 시간 복잡도를 끝내고, 챕터 3에 들어가 배열에 대한 내용을 배우고 있다.

배열에 대한 개념, 알고리즘에서 어떻게 활용하는지, 배열을 이용한 백준 문제를 풀고 피드백을 들었다.

배열 챕터에서의 공부 내용은 대략 아래와 같다.

 

 

---

10989 수 정렬하기3

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

내 시간복잡도에 문제가 없는데, 시간 초과가 난다면

- 입출력 시간을 측정해보자.

- Scanner, System.out.println은 상대적으로 느리다.

 

package 배열;

import java.io.*;

public class BOJ10989 {
    //백만단위 이상이면 BufferdReader를 쓰자
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] cnt = new int[10001]; //1~10000까지를 인덱스로 쓸 것
        for(int i=0;i<N;i++)
            cnt[ Integer.parseInt(br.readLine())]++;

        for(int i=1;i<=10000;i++)
            while(cnt[i] --> 0){ //cnt[i]가 존재할 때까지
                bw.write(i + "\n");
            }
        bw.flush();
    }
}

 

---

3273 두수의 합

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

1) 숫자 기록 배열 만들기

해당 수가 있는지 확인하는 불린타입 배열을 만든다. (중복이 없다고 했으므로 카운트가 아닌 불린으로 만든다.)

boolean[] exist = new boolean[1000001]; // 문제에서 수의 범위가 백만이라고 했기 때문에 

단, 수를 1부터 카운트 할 것이기 때문에 인덱스를 1부터 사용할 것이므로 1000001 크기의 배열을 만든다.

그 후, exist 배열에 입력받은 수를 인덱스로 넣어준다.

  for(int i=0; i<N; i++)
            exist[a[i]] = true;

 

2) (X-1)/2 (X는 결과값) 만큼 for문을 돈다.

예를 들어,

* input : 1 2 3 4 5 6 7 8 * 합산값 : 9

---> 나올 수 있는 쌍: (1,8) / (2,7) / (3,6) / (4,5) / (5,4) / (6,3) / (7,2) / (8,1)  ---> 총 8개 ---> 답은 4개

이 경우 중복되는 쌍들은 카운트할 필요가 없다.

따라서 합산값에 2를 나눈 몫만큼만 for문을 돈다. (X/2)

 

단, 합산값이 짝수일 경우 

* input : 1 2 3 4 5 6 7 8 * 합산값 : 8

---> 나올 수 있는 쌍: (1,7) / (2,6) / (3,5) / (4,4) / (5,3) / (6,2) / (7,1)  ---> 총 7개 ---> 답은 3개

합산값이 짝수일 경우 (4,4)라는 동일 값이 순서쌍으로 생겨날 수 있으므로 1을 빼서 (어차피 동일한 숫자는 하나밖에 없으므로)

(X-1)/2 만큼을 반복문을 돌린다.

 

import java.util.Scanner;

//https://www.acmicpc.net/problem/3273
public class BOJ3273Re {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[N];
        for (int i=0; i< N; i++)
            a[i] = sc.nextInt();
        int X = sc.nextInt();

        boolean[] exist = new boolean[1000001]; //숫자 기록배열
        for(int i=0; i<N; i++)
            exist[a[i]] = true;

        int ans = 0;
        for(int i=1; i<=(X-1)/2;i++)
            if(i<=1000000 && X-i <= 1000000) //범위 체크 필수
                ans += (exist[i] && exist[X-i]) ? 1 : 0; //동일 쌍이 있으면 카운트를 해준다.
        System.out.println(ans);
    }

}

 

 

강의 듣기 전 미리 문제 풀기!

 

강의 들은 후, 문제 다시 풀고 포스팅하기

 

 

코테 챌린지도 하고 있는데... 이미 많이 안했지만 앞으로라도 매일...!!

 

나처럼 알고리즘을 어려워하는 사람이 많은데, 요즘은 기업 채용 시 코딩테스트가 필수적이다 보니 공부는 피할 수 없다.

강의가 어렵지 않기도 하고, 강의를 따라 차례차례 문제를 풀다 보면 코딩테스트에서 활용되는 개념들에 대한 감을 잡을 수 있을 것 같다.

나도 꾸준히 공부하기 위해 앞으로 매주 문제 풀고 포스팅 + 수강후기를 올릴 계획이다.

언젠가 알고리즘을 두려워하지 않게 될 내가 되길 바라며...!!

 

 

 

  알고리즘을 극복한 나(ㅋㅋㅋ)

 

 

 

내가 지금 듣고 있는 강의(핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java) 수강 페이지는 아래와 같다.

강의 페이지 : https://fastcampus.co.kr/dev_online_codingtest

 

 

 

 

 

 

"본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다."