비전공 개발자의 쉬운 CS

문제링크 : https://www.acmicpc.net/problem/1520

문제 접근

• Topological Sort 기본문제
• 개념 참조 : https://dev-jango.tistory.com/12

시간복잡도 계산

• 모든 노드 : V
  • 모든 노드에 인접한 노드의 indeg 감소 : E
  • O(V + E)
  • e4 + e5
    

인트 계산

• 숫자범위 생각할 숫자 없음
  

코드

문제유형

• topological sort
  

비슷한 문제

문제 정의

• 일부 노드들의 순서가 주어졌을때, 전체 순서를 정하는 문제

문제 접근

• 노드 순서를 인접 리스트(adj)로 저장
  • 인접 리스트로 저장하면서, 노드에 들어오는 간선의 개수(indeg)를 기록
  • 큐를 하나 생성해서, indeg가 0인 것들을 추가
    • indeg가 0이란 의미 : 들어오는 간선이 없으므로, 출발노드
  • 각 큐에 들어있는 노드에 대해서 다음을 반복
    • 결과 리스트에 추가
    • 각 노드에 인접한 노드들에 대해, indeg를 감소
    • 이떄, indeg가 0인 노드는 큐에 새로 추가
  • 결과 리스트 출력

시간복잡도

• 모든 노드 : V
  • 모든 노드에 인접한 노드의 indeg 감소 : E
  • O(V + E)

인트 계산

• 모든 입력 >> 10억 이하의정음수 >> INT 가능
• dp값 : 최악의 케이스는 약 4^2500? >> 안전하게 LL 사용

대표예제 : 백준 2252 줄세우기

비슷한 유형

• 몇번째 순서인지 구하는 문제
  • topological sort는 전체 순서는 맞지만, 내가 몇번째 순서인지 정확히 알수는 없음
    • 예시 : 1번 노드가 2번쨰 순서도 정답이고 3번째 순서도 정답임
    • 즉, 순서가 뒤틀리거나 틀리지만 않으면 됨
  • 내가 정확히 몇번째 순서를 구하는 문제는 플로이드를 통해서 확인 가능
  • https://www.acmicpc.net/problem/2458
  • map[j][k] = 1 && map[k][i] ==1 >> map[j][i] =1

문제링크 : https://www.acmicpc.net/problem/2805

문제 접근

• 모든 높이를 기준으로, 전체 나무 순회 >> O(M*N) >> 2e9 * 1e6 >> 시간초과
• 자르려는 높이 증가할수록 얻을수 있는 나무의 길이가 감소 >> 선형적이므로 이진탐색 사용 가능
  • 자르려는 높이를 이진탐색 O(lgM)
  • 이때 나무 순회하면서 얻을 수 있는 나무를 구함 >> O(N)
  • O(N*lgM)
• Lower vs Upper
  • 이진 탐색 하는것을 그래프로 그려봤을때
  • X축 : 자르려는 높이, Y축 : 얻게되는 나무의 수
  • 같은값이 없을때 더 낮은 높이를 설정해야함 > UpperBound
  • 더 높은 높이를 설정할 경우, 얻게 되는 나무의 수가 부족한 현상 발생

시간복잡도 계산

• 자르려는 높이를 이진탐색 O(lgM)
• 이때 나무 순회하면서 얻을 수 있는 나무를 구함 >> O(N)
• O(N*lgM)

인트 계산

• 이진탐색 시 필요한 나무길이 : 나무길이 최대 1e6 * 2e9 >> 2e15 >> 인트 사용 불가, long long
  • 나무 높이 : 1e9 이하 >> 인트 사용 가능

코드

문제유형

• 이진탐색 - 케이스
  • 이진 탐색 문제 중 정답이 되는 값을 이진탐색 하는 문제
  • 이와 반대 유형으로 '이진탐색 - 모든 케이스'
    • 모든 케이스에 대해서, 연산을 이진탐색 해주는 유형
      

비슷한 문제

• https://www.acmicpc.net/problem/1300
• https://www.acmicpc.net/problem/1939
• https://www.acmicpc.net/problem/2805

문제링크 : https://www.acmicpc.net/problem/14226

문제 접근

• BFS로 해서, 각 시간별 작업을 큐에 넣고 하면 되지 않을까
  • 큐 : 화면, 클립보드
  • 화면, 클립보드 중복 체크
    • 그래서 S개를 만드는데 시간 최소를 구하면 되지

시간복잡도 계산

• BFS 시간복잡도 O(V+E) : 4e6
• 노드 : 화면 * 클립보드 1e6
• 간선: 3개 * 노드
• O(V+E) : 4e6

인트 계산

• S는 1000개 이하, 시간도 그보다 이하
  

코드

문제유형

• 최소시간 구하는 BFS

문제링크 : https://www.acmicpc.net/problem/1744

문제 접근

• 숫자끼리 더하거나 곱해서 최대로 나올수 있는 방법이 있음 >> 그리디
  • 양수 : 큰수는 큰수끼리 곱해야함
  • 음수 : 큰 음수끼리 곱해야함
  • 0 :
    • 음수가 짝수일때 >> 그냥 더함
    • 음수가 홀수일때 >> 음수에 곱함
      • 예외 케이스
  • 1곱하기 1인경우 >> 그냥 더하는게 나음
  • -1곱하기 -1은 >> 곱하는게 나음

시간복잡도 계산

• 정렬한뒤 순차탐색 >> O(NlgN + N) >> O(NlgN) >> 20 * e5 = 2e6

인트 계산

• 정답은 항상 2^31 보다 작음 >> Int 가능?
• 근데 연산하는 중 수가 더 커질수도 있음
  • 예시 : e4 * e4 가 5000쌍일경우
  • 그래서 안전하게 long long으로

코드

문제유형

• 그리디 - 숫자관련 최소 최대

문제링크 : https://www.acmicpc.net/problem/1963

문제 접근

• 각 케이스를 변경하면서 최소횟수를 구하니까 BFS
  • 각 자리수마다 한자리수만 바꿔서 소수가 될수있는것을 찾아서 큐에 넣어줌
  • 이떄, 중복확인 체크 필요
  • 그럼 소수인지 확인 여부는?, sqrt까지 나머지가 0되는게 있는지여부로 확인

시간복잡도 계산

• BFS(V+E)
• V = 총 e4개
• E = 각 숫자에서 각 한자리씩만 바꾸니까 40개씩, e4 * 40= 4e5
  • 그리고 소수인지 각각 체크해야하니까. 4e5 * sqrt(10000) = 4e7

인트 계산

• INT 넘어가는수 >> 최소 횟수
• 근데 총 숫자가 e4개 있으니까, 이 횟수는 안넘어갈것임

코드

문제유형

• BFS - 최소값

문제링크 : https://www.acmicpc.net/problem/1309

문제 접근

• 어떻게 해야하는지 감이 안오는데? 우선 각 케이스를 구해보자
  • 2 X 0 : 0마리 1
  • 2 X 1 : 0마리 1, 1마리 2
  • 2 X 2 : 0마리 1, 1마리 4, 2마리 2
  • 2 X 3 : 0마리 1, 1마리 6, 2마리 8, 3마리 2
• 다음 우리의 개수와 이전 우리의 개수의 연관관계 찾을때, 사자가 인접하지 않는다는 조건 때문에 복잡
  • 첫째줄에 사자가 없는경우, 왼쪽에 있는경우, 오른쪽에 있는 경우로 나누면 어떨까 >> 케이스별 2차원 DP
  • DP[N][0] = 2XN 타일 중 첫번쨰 줄에 사자 없는경우 = DP[N-1][0] + DP[N-1][1] + DP[N-1][2]
  • DP[N][1] =2XN 타일 중 첫번쨰 줄의 왼쪽에 사자 있는경우 = DP[N-1][0] + DP[N-1][2]
  • DP[N][2] =2XN 타일 중 첫번쨰 줄의 오른쪽에 사자 있는경우 = DP[N-1][0] + DP[N-1][1]
• 초기조건
  • DP[0][0] = 1, DP[0][1] = 0, DP[0][2]= 0
  • DP[1][0] = DP[0][0] + DP[0][1] + DP[0][2] = 1
  • DP[1][1] = DP[0][0] + DP[0][2] = 1
  • DP[1][2] = DP[0][0] + DP[0][1] = 1
• 사자가 없는 경우의수는 DP[0][0] 에 포함되며, 이후에도 계속 포함되서 계산됨

시간복잡도 계산

• N칸에서 3번 계산 해줘야함, O(3*N), 3e5

인트 계산

• 경우의수 9901 나머지 이므로 인트 범위 가능

코드

문제유형

• 케이스별 2차원 DP
  • 각 케이스로 쪼개서 DP를 계산
  • 조건이 조금 복잡하다 싶으면, 이 유형인지 한번 확인 필요

비슷한 문제

• https://www.acmicpc.net/problem/2579

문제링크 : https://www.acmicpc.net/problem/1890

문제 접근

• 이전의 경우의 수가 다음것에 바로 사용됨 >> DP
• DP
  • 3이라고 적혀있는 칸일경우, 3칸 오른쪽이나 아래쪽에 값을 반영 가능할까? >> 가능할것 같음
  • DP[Y][X] = Y,X칸을 갈 수 있는 경우의 수
  • DP[0][0] = 1; , DP[0][0]의 값이 K일경우
  • DP[K][0] += DP[0][0], DP[0][K] += DP[0][0]

시간복잡도 계산

• 가로 * 세로 >> O(N^2) >> 1e4

인트 계산

• 모두 갈수 있는 경우라면 >> 2^100 >> 1e30 >> 인트 초과 >> DP값은 long long 사용

코드

문제유형

• 일반 DP
  

문제링크 : https://www.acmicpc.net/problem/2225

문제 접근

• 감이 안오는데? 각 케이스를 생각해보자

  • 20 = 19 + 1, 18+2, 17+3
  • 만약 K가 3일경우엔, 20 = 18+1+1, 17+1+2, 17+2+1, ...
  • 이전 값을 다시 재활용해서 사용할 수 있을것 같음 >> DP로 해보자 >> 종류 2차원 DP 문제
    • DP[K][N] = K개를 사용해서 N을 구하기 위해서 경우의 수
  • 앞에는 1개로 정해놓고 뒤에만 움직이는경우
    • DP[K][N] = DP[1][0] +DP[K-1][N] + DP[1][1] + DP[K-1][N-1] + DP[1][2] + DP[1][K-2] + ...
  • 근데 어짜피 K가 1이면 DP[1][K] = 1
  • DP[K][N] = DP[K-1][0] + DP[K-1][1] + DP[K-1][2] + ...DP[K-1][N]
  • 이때 예외가 있을까?
    • K = 1일때는 적용 안됨, 항상 종류 1
      ### 시간복잡도 계산

• DP[N][K]에서 연산횟수 >> N-1번, 약 N번이라고 가정시

  • O(N_K_N) = O(N^2 * K) = 8e6 >> 가능
    ### 인트 계산

• dp값을 1e9 나머지로 계산해줘서 신경써줄 필요없음
  ### 코드

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

  #include <iostream>   using namespace std; int dp[210][210]; int main() {     int N,K;     cin >> N >> K;     fill(&dp[0][0], &dp[209][210], 0);     dp[0][0]= 1;     // K=1 일경우 경우의수 1개 >> 각 수를 내서 만들수 있으니까     fill(&dp[1][0], &dp[1][210], 1);          for(int j=2; j<=K; j++) {         for(int i=0; i<=N; i++) {             for(int k=0; k<=i; k++) {                 dp[j][i] = (dp[j][i] + dp[j-1][k]) % 1000000000;             }                      }     }          cout << dp[K][N] << '\n';               return 0; }   Colored by Color Scripter

  cs

문제유형

• DP - 이전 종류값 만을 포함
  • dp[N][K] = N개의 종류를 가지고있을때, K가치를 가질때의 dp 값
  • 단, 이전값만을 활용하는경우, dp[N]으로 줄여서 사용할 수 있음
    • 단 한번만 빼줘야함, 뺀곳에 여러번 뺀 경우의 수가 담겨있음
  • 대표문제 : knapsack
    • 여러 종류의 아이템을 한번씩 넣을수있을때, 한정된 비용에서의 최대가치 구하는 문제
    • dp[N][K] : N개의 종류를 들고, K만큼의 무게에서의 가질수 있는 최대 가치
    • https://www.acmicpc.net/problem/12865

비슷한 문제

• https://www.acmicpc.net/problem/2293
• https://www.acmicpc.net/problem/2294
• https://www.acmicpc.net/problem/2225
• https://www.acmicpc.net/problem/12865

객체 생성방식

• 리터럴 : 일반적이고 간단

  1

  var a = {b : ‘c’, d : ‘e’}

  cs

   

• 생성자 함수 : 오늘 알아볼것

  1 2 3 4 5 6 7 8 9

  function a() {   this.b = ‘c’;   this.d = ‘e’;   }   var a = new a();

  cs

생성자 함수

• new와 함께 호출하여 객체를 생성하는 함수

• new없이 호출하면 생성자 함수가 아닌 일반 함수로 동작

• 종류 : Object, String, Number, Boolean, Function, Array, Date, RegExp, Promise 등

• 사용하는 이유

  • 객체 리터럴의 문제점 : 동일한 객체 여러번 생성할때 비효율적

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

    const a1 {   num : 123,   printnum() {return this.num};    }   console.log(a1.printnum()); // 123       const b1 {   num : 456,   printnum() {return this.num};    }   console.log(b1.printnum()); // 456

    cs

  • 생성자 함수를 사용할 경우 프로퍼티 구조 동일한 객체를 간편하게 생성 가능
  • 자바의 클래스 개념과 유사

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

    function a(num) {   this.num = num;   this.printnum = function() {return this.num};   }       const a1 = a(123);   const b1 = a(456);       console.log(a1.printnum()); // 123   console.log(b1.printnum()); // 456

    cs

생성자 함수, 인스턴스 생성 과정

• 인스턴스 생성과 this 바인딩
  • 빈 인스턴스가 생성
  • this는 빈 인스턴스에 바인딩
    • 앞에 new 붙이지 않으면, this는 window를 가르킴(일반 함수로 호출되기 때문)
    • 그래서 함수와 생성자 함수를 구분하기 위해서 생성자 함수는 첫글자를 대문자로함(파스칼 케이스라고 부름)
  • 위 과정은 생성자 함수 코드가 실행되기 전에 실행됨
    • 어려운 말로, 런타임 이전에 실행
• 인스턴스 초기화
  • 생성자 함수 코드 한줄씩 실행되며, 인스턴스를 초기화
• 인스턴스 반환
  • return 따로 명시하지 않아도 this를 반환
  • 만약 this아닌 다른 객체를 return 하면, this가 아닌 다른 객체를 return
  • this 아닌 primitive 반환하면 무시
    • primitive : String, Number 등
    • 이러면 꼬이게됨, 일반적으로 return을 생략해서 사용
• 예시

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  function Circle(radius) {   // 1. 빈 인스턴스 생성 및 this에 바인딩       // 2. 코드 한줄씩 실행되며 인스턴스 초기화   this.radius = radius;   this.getDiameter = function() {       return 2 * this.radius;   };       // 3.this를 return   };   Colored by Color Scripter

  cs

생성자 함수로 만든 객체가 일반 객체와 다른점

• 일반 객체는 호출할 수 없지만 함수는 호출 가능
  • 일반 객체에게 없는, 함수로서 동작하기 위한 내부슬롯과 내부 메소드를 가짐
  • 내부슬롯, 내부메소드 : 외부로 노출되진 않지만, 자바스크립트 내부에서 동작하는 객체, 메소드
  • 내부슬롯
    • [[Environment]]
    • [[FormalPrameters]]
  • 내부 메소드
    • [[Call]] : 일반함수로서 호출되면 실행
    • [[Construct]] : new 연산자와 함께 호출되면 실행

생성자 함수로 객체 생성이 불가능한 함수

• 함수 내부 메소드로 [[Construct]]가 없는것은 생성자로 함수로 객체 생성이 불가능
• 객체 생성이 가능한 함수
  • constructor로 부름
  • 함수 선언문 : function Circle() {~~}
  • 함수 표현식 : var Circle = function() {~~}
  • 클래스(클래스도 함수)
• 객체 생성이 불가능한 함수
  • ES6 메서드 축약 표현 :
    const obj = {
    x() {}
    }
  • 화살표 함수 : const Circle = () => {};

생성자 함수가 일반 함수와 다른점

• this
  • 생성자 함수는 this가 인스턴스를 가르키지만,
• 일반 함수의 this는 window를 가르킴
  • 그래서 함수와 생성자 함수를 구분하기 위해서 생성자 함수는 첫글자를 대문자로함(파스칼 케이스라고 부름)
• new.target : 생성자 함수로서 호출되었는지 확인 가능
• 생성자 함수로 호출되면(new 연산자로 호출되면), new.target은 함수 자신을 가르킴
  • 일반 함수로 호출되면 new.target은 undefined
  • 일반 함수로 호출되어도 생성자 함수로 호출되도록 사용하기 위해 활용됨

    1 2 3 4 5 6 7 8 9

    function Circle(radius) {     if(!new.target) {         return new Circle(radius); // 일반 함수로 호출되었을경우 생성자로 다시 호출 }   this.radius = radius; this.getDiameter = function() {return 2*this.radius;};   } Colored by Color Scripter

    cs

  • 스코프 세이프 생성자 패턴
    • new.target은 ES6부터 도입해서, 비교적 최신 버전에서만 지원
    • 그래서 new.target 대신, this instanceof Circle 로 사용하기도 함