1. 알고리즘 입문

1.1 알고리즘과 코딩 테스트

1) 알고리즘

[일반적 정의]

• 어떤 문제를 풀기 위한 절차나 방법
• 주어진 입력을 출력으로 만드는 과정
• 각 단계는 구체적이고 명료해야 함
  • 컴퓨터는 주어진 명령을 수행하므로, 알고리즘이 구체적이지 않으면 올바르게 계산할 수 없다.

[프로그래밍에서의 정의]

• 특정 문제를 해결하는데 필요한 명령어들의 순서적 집합
• 중요 성질
  • 정확성
  • 효율성 

2) 코딩 테스트

• 알고리즘 지식과 프로그래밍 능력을 평가하는 테스트
• 많은 IT 기업들은 채용 과정에서 코딩 테스트를 활용하여 지원자의 코딩 능력과 문제 해결 능력을 평가

3) 왜 알고리즘과 코딩 테스트 준비를 해야 하나요?

• 실력 향상 관점
  • 문제 해결 능력 향상: 다양한 문제 유형을 통해 문제를 분석하고 해결하는 능력 배양
  • 효율적인 코드 작성: 시간과 자원을 절약하며, 프로그램의 성능을 향상
  • 프로그래밍 언어 실력 향상: 해당 언어에 대한 깊은 이해와 숙련
• 취업 준비 관점
  • [기업]기업의 기술력 평가 도구: 지원자의 프로그래밍 능력, 문제 해결 능력, 알고리즘 지식을 평가
  • [지원자]다양한 기업 지원 가능: 넓은 범위의 IT채용에 흔히 사용되므로, 다양한 기업 지원이 가능
    • + 블로그에 과정을 기록하기 좋다.

 

1.2 알고리즘 학습 방향

1) 저는 1도 모르는데 어떡하죠?

• 주 사용 언어의 기본 문법 학습 및 숙달
  • C++, 자바, 파이썬 중 택 1 기본 문법 학습
  • 표준 라이브러리(기본 제공 기능)만 잘 알아도 많은 문제를 해결 가능
    • tcpschool: http://tcpschool.com/java/intro
    • pythontutor:  https://pythontutor.com/java.html#mode=edit
    • w3sschools: https://www.w3schools.com/java/default.asp
  • 주의: 많은 경우 Java8(1.8을 기준으로 평가환경이 세팅되기 때문에, java11 이후 신 문법은 지원하지 않는 경우가 다수
• 자료구조 이해
  • 배열(리스트), 맵, 스택, 큐, 트리, 그래프 등 자료구조의 특징만 알아도 풀 수 있는 문제가 절반
  • 자료구조 : 데이터를 효율적으로 처리하고 저장하는 방법
  • 알고리즘이 사용하는 데이터를 어떻게 저장하고 조직화하느냐에 따라, 그 알고리즘이 효과적으로 실행될 수 있는지가 결정된다.
    • SW Expert Academy Learn(삼성, 무료 강의 제공): https://swexpertacademy.com/main/learn/course/courseList.do
    • 컴퓨터 알고리즘 기초: https://www.youtube.com/playlist?list=PL9mhQYIlKEhdvKFh-wVpDuihNQv6C1gSy
    • 알고리즘 코딩테스트 문제풀이 강의: https://www.youtube.com/playlist?list=PLFgS-xIWwNVU_qgeg7wz_aMCk22YppiC6
• 주요 문제 풀이 기법 학습
  • DFS, BFS, 동적계획법 등 노력과 암기로 해결할 수 있는 문제들이 대부분
  • 문제 출제
    • 백준(표준입출력): 
    • 프로그래머스(함수형 문제): https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&page=1&languages=java
    • 이런 코딩테스트 문제 출제 사이트를 풀이하는 과정을 블로그, 깃 등에 주 3회 이상 업로드하는 것을 추천.

2) 표준입출력

• 표준 출력(Standard Output)
  • 프로그램 결과나 메시지를 사용자에게 보여주는 방법
  • System.out.println() 메소드 사용
• 표준 입력(Standard Input)
  • 프로그램 내에서 사용자로부터 데이터를 받는 방법
  • Scanner 클래스 활용

 

[백준 써보기]

꼬마정민 : https://www.acmicpc.net/problem/11382

import java.util.Scanner;

//https://www.acmicpc.net/problem/11382
class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    // A + B + C
    // 77 77 7777
    long A = sc.nextLong();
    long B = sc.nextLong();
    long C = sc.nextLong();
    sc.close();
    // System.out.println(A);
    // System.out.println(B);
    // System.out.println(C);
    System.out.println(A + B + C);
  }
}

1.3 알고리즘 뜯어보기

1) 알고리즘 분석 : 알고리즘의 성능, 특성을 분석하는 일

2) 알고리즘의 구성요소

알고리즘: 문제를 풀기 위한 절차나 방법이며, 주어진 입력을 출력으로 만드는 과정을 구체적이고 명료하게 표현한 것

• 문제: 해결하고자 하는 문제 인식
• 입력: 값을 특정하지 않고 변수로 입력을 받는 경우가 많음(다양한 입력에 대한 결과를 얻기 위해)
• 출력: 처리 후 반환해야 하는 값

3) 입력 크기와 계산 횟수

• 입력 크기는 알고리즘의 수행 성능에 영향을 미침
  • 계산횟수(알고리즘 계산의 복잡도) ∝ 입력 크기
  • 입력크기와 수행 성능의 관계를 계산 복잡도를 통해 표현
• 대문자 O(빅 오) 표기법
  • O(n): 필요한 계산 횟수가 입력 크기 n과 비례
  • O(1): 필요한 계산 횟수가 n과 무관
  • O(n²): 필요한 계산 횟수가 n의 제곱에 비례
• 계산 복잡도
  • 시간 복잡도(time complexity)
    • 어떤 알고리즘을 수행하는 데 얼마나 오랜 시간이 걸리는지 분석
    • 수업 중 언급되는 계산 복잡도는 대개 시간 복잡도를 의미(효율성 측면)
  • 공간 복잡도(space complexity)
    • 어떤 알고리즘을 수행하는 데 얼마나 많은 공간(메모리/기억 장소)이 필요한지 분석