문제 설명


문제

다음과 같이 정의된 수열이 있다.

  • D[1] = A
  • D[n] = D[n-1]의 각 자리의 숫자를 P번 곱한 수들의 합

예를 들어 A=57, P=2일 때, 수열 D는 {57, 74(=5^2+7^2=25+49), 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …}이 된다. 그 뒤에는 앞서 나온 수들(57부터가 아니라 58부터)이 반복된다.

이와 같은 수열을 계속 구하다 보면 언젠가 이와 같은 반복수열이 된다. 이때, 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하는 프로그램을 작성하시오. 위의 예에서는 {57, 74, 65, 61}의 네 개의 수가 남게 된다.

입력

첫째 줄에 A(1 ≤ A ≤ 9999), P(1 ≤ P ≤ 5)가 주어진다.

출력

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.


풀이 과정

  1. set에 반복되는 요소가 나올때까지 수열을 넣는다
    • 반복되는 요소가 나온다면 해당 요소의 값을 따로 저장만 하고 넣지는 않음.
  2. 반복되는 요소에서부터 set에서 나오지 않을때까지 수열을 구하고 해당 수열을 set에서 빼준다.
  3. set에 남아있는 수열이 즉, 반복되는 부분이 제외된 수열이다.

소스 코드

import sys
input = sys.stdin.readline

A, P = map(int, input().rstrip().split())

def get_next(n, p):
    nvalue = 0
    while n > 0:
        nvalue += (n % 10) ** p
        n = n // 10
    return nvalue

visited = set()

current = A
dup_start = 0
# 1. 지나간 숫자중에 하나가 다시 나타나는 경우 중복의 시작
while True:
    if current not in visited:
        visited.add(current)
    else:
        dup_start = current
        break
    current = get_next(current, P)

# 2. 중복 시작점에서 중복 끝날때까지 요소들 빼줌
while dup_start in visited:
    visited.remove(dup_start)
    dup_start = get_next(dup_start, P)

# 3. 남아있는 요소의 개수 출력
print(len(visited))

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 1918 ] [Stack] 후위 표기식  (0) 2021.07.31
[ 4179 ] [BFS] 불!  (0) 2021.07.31
[ 10451 ] [DFS] 순열 사이클  (0) 2021.07.30
[ 2491 ] [DP] 수열  (0) 2021.07.29
[ 17175 ] [DP] 피보나치는 지겨웡~  (0) 2021.07.29

문제 설명


문제

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면

(1 2 3 4 5 6 7 8

3 2 7 8 1 4 5 6) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

              순열을 배열을 이용해 (1…i…n  π1…πi…πn) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.


풀이 과정

  1. 그래프로 보면.. 1번 노드가 3번 노드와 연결되어 있다 이런식으로 해석 가능
  2. 노드 1~n번째 각각에서 연결된 노드가 사이클을 형성할때까지 이동해본다.
    • dfs 사용
    • 끝나는 조건 : 이동할 때 시작 숫자 = 순열[index]
  3. visited를 두어 방문했던 노드들을 다시 방문하지 않도록 처리한다.

소스 코드

import sys

input = sys.stdin.readline

T = int(input().rstrip())

def dfs(visited, sequence, start, current):
    if visited[current] == True:
        return False
    visited[current] = True
    if current == start:
        return True
    return dfs(visited, sequence, start, sequence[current])

for _ in range(T):
    N = int(input().rstrip())
    sequence = [0] + list(map(int, input().rstrip().split()))
    visited = [False] * (N+1)
    answer = 0
    for i in range(1, N+1):
        if visited[i] == False:
            answer += 1
            dfs(visited, sequence, i, sequence[i])
    print(answer)

'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글

[ 4179 ] [BFS] 불!  (0) 2021.07.31
[ 2331 ] 반복 수열  (0) 2021.07.30
[ 2491 ] [DP] 수열  (0) 2021.07.29
[ 17175 ] [DP] 피보나치는 지겨웡~  (0) 2021.07.29
[ 14916 ] [DP] 거스름돈  (0) 2021.07.29

[배열] forEach와 map


  • for .. of문과 비슷

  • forEach

      arrays.forEach((element) => {
          console.log(`${element}`);
      });
    
      arrays.forEach((element, idx) => {
          // element, index
      });
    
      arrays.forEach((element, idx, arr) => {
          // 개별요소, 개별요소의 인덱스, 호출한 배열
      });
  • map

      const newarray = arrays.map((element, idx) => {
          return element + p
      }); // 모든 요소에 p를 더한 새로운 배열 반환
  • forEach, map 도중에 배열에 추가/삭제 가능. 추가하더라도 호출한 시점의 요소 수만큼만 반복

  • 단, 삭제시에는 forEach/map이 삭제된 요소 수만큼 덜 반복

  • JavaScript에서

  • 태그의 값 수정하기

      new_element.innerText=`${idx+1}.${title}`
      new_element.textContent = `${idx+1}.${title}`

[배열]Filter/find


  1. Filter

    1. 조건에 맞는 요소들만 가져옴

    2. 배열이 리턴됨.

      const filtering_array = arrays.filter((element) => element.a === 'a') // 
      
      const filtering_array = arrays.filter((element) => {
       return element.a === 'a';
      });
  2. find

    1. 조건에 맞는 하나의 요소를 가져옴

    2. 하나 찾는순간 종료(0에서부터 첫번째)

    3. 존재하지 않으면 undefined 리턴

      const filter_target = arrays.find((element) => element.a === 'a');
      
      // 다른 예시
      const user = data.find((e) => {
       return e.userName === nameValue && e.phoneNumber === phoneValue;
      })

[배열] some/array


  1. some : 만족하는 요소가 1개라도 있는지

    • 첫번째 요소를 찾는 순간 반복 종료

      const p = [1, 2, 3, 4, 5]
      const test = p.some((e) => e>=5); // true
  2. every : 모든 요소가 조건을 만족하는지

    • 요소가 조건을 만족하지 않는다면 반복 종료

      const p = [1, 2, 3, 4, 5]
      const test = p.every((e) => e>=5); // false
  • 빈 배열의 경우 some은 false, every는 true

[배열] reduce


  1. reduce

     arrays.reduce((acc, el, i, arr) => {
         return nextAccValue;
     }, initialAccValue); // 초기 acc 값 조정
    
     // acc : 누산기, 다음 요소로 전달
     // el : 현재 요소
     // i : 현재 요소의 인덱스
     // arr : 전체 배열
    
     const totalCareer = data.reduce((acc, element, i, arr) => {
       acc += element.month
       return acc
     }, 0) // 전체 일한 개월수 구하는 소스

[배열] sort, reverse


  1. sort

    • 유니코드 기준 오름차순/내림차순이어서 평소 알던대로 정렬되지 않음.

    • 콜백함수 정의

        arrays.sort((a, b) => b-a) // 내림차순
        arrays.sort((a, b) => a-b) // 오름차순
      
        // 원본 배열의 요소들을 정렬함.
  2. reverse

     arrays.reverse() // 원본 배열을 뒤집음

Map, Set


  1. Map
    • 메소드를 통해 값 추가/접근
    • 메소드
      • new Map() ⇒ 생성
      1. map.set(key, value) ⇒ key,value 추가
      2. map.get(key) ⇒ key에 해당하는 값 리턴
      3. map.has(key) ⇒ key 존재 여부
      4. map.delete(key) ⇒ key에 해당하는 값 삭제
      5. map.clear() ⇒ map 초기화
      6. map.size ⇒ map의 크기
  2. Set
    • 중복을 허용하지 않음
    • 메소드
      • new Set(), new Set(배열)
      • set.add(value) ⇒ value 추가
      • set.has(value) ⇒ value 포함하는지
      • set.delete(value) ⇒ value 삭제
      • set.clear() ⇒ 초기화
      • set.size ⇒ 요소의 개수

모듈


  • 모듈화 : 공통된 기능이나 특별한 목적으로 분할
    • 효율적 관리, 재사용

모듈 파일의 조건


  1. 독립적인 스코프(모듈 스코프)

    • 모듈 파일 내에서의 변수는 해당 파일 내에서만 사용
    • 지키지 않는 경우 덮어씌워지거나 SyntaxError등 문제 많음.
  2. 모듈 스코프를 만들어주려면

    • type에 module 설정

      <script type="module" src="js파일 경로"></script> 
      // 에러 발생 => 로컬파일 안됨, 웹 서버를 통해 script 실행해야 함
    • VSCODE의 Live Server 확장 프로그램 설치 → 우측 하단의 go live 통해 간이 서버

모듈 문법


export const p = 'hh';
export function f(value) {
    return value;
}

import {p, f} from './myjs.js';
  • export 키워드를 써주면 외부로 내보낼 수 있음

  • import를 통해 불러올 수 있음.

  • import 시 rename

    • as 키워드 사용하여 이름 변경

      import {p as newname, f as newname2} from './myjs.js'
  • 모든 대상을 한번에 import

      import * as myjsobj from './myjs.js'; // export하는 모든 요소 한번에 import
    
      myjsobj.p
      myjsobj.f
    
      // 한번에 export
      export { p as variables, f as function }; 
      // 선언문 앞의 export 키워드들 지우고 맨마지막에 한번
      // 여기서는 * 쓰면 안되요.
  • default export

      export default 'aabb'; // 모듈 내에서 단 한번만 사용 가능, 하나의 값만
      import { default as a } from './myjs.js'; // default는 반드시 as 사용해주어야 함
      import a, {b, c} from './myjs.js'; // 중괄호 없는것을 default
    
      import * as p from './myjs.js';
      p.default // default
    
      export default { a, b } // default = 객체 { a:a, b:b }
    
      import obj from './myjs.js'; // 중괄호 없으면 default keyword이므로 obj에 { a, b }
      import {default as obj} from './myjs.js' // 위와 똑같은 소스

'Language > JavaScript' 카테고리의 다른 글

[ JavaScript ] 웹 기초  (0) 2021.07.31
[ JavaScript ] 객체지향 프로그래밍  (0) 2021.07.30
[ JavaScript ] 함수, 표기법, 예외 처리  (0) 2021.07.29
[ JavaScript ] 데이터 타입  (0) 2021.07.29
[JavaScript] 몰랐던 문법  (0) 2021.07.26

JavaScript


  • 함수 선언을 값처럼 → 함수 표현식
  • 함수 선언 : 호이스팅, 함수 내에서 선언된것이 아닌 코드블록 내에서는 전역변수처럼 사용
  • 함수 표현식 : 호이스팅되지 않음, 스코프 존재, 선언 이후에만 호출 가능.
  • 둘중 한가지 방식으로 일관되게 사용하는것이 좋음, 함수 선언이 조금 더 권장
function 함수(파라미터) { // 함수 선언
    return 리턴값;
}

const p = function() { // 함수 표현식
    return 리턴값;
};

btn.addEventListener('click', function() {
    ...
});

Named Function Expression(기명 함수 표현식)


  • 재귀 함수에서는 기명 함수 표현식을 쓰는것이 좋음.
  • 재귀함수 사용 시 사용하려는 함수가 null이 되버리면 문제가 되므로 네이밍을 다르게 해준다.
const func = function test() {
  ...
}

test() // Error

const factorial = function (n) {
    if (n <= 1)
        return 1
    return n * factorial(n-1);
}

let f = factorial;
factorial = null;
t = f(5) // => 오류

const factorial = function fact(n) {
    if (n <= 1)
        return 1
    return n * fact(n-1);
}

let f = factorial;
factorial = null;
t = f(5) // 에러 x

즉시 실행 함수


  • 함수가 선언된 순간 바로 실행 (IIFE)
  • Immediately Invoked Function Expression
  • 외부에서 사용 불가능, 재귀함수로 만들 때는 이름 필요
(function func() {
    실행문
})();

func(); // 에러 발생

(function init() {
    // 초기화
})();

const fact = (function factorial(n) { // 재귀함수 만들때 이름 및 변수에 바로 리턴값 저장
    if (n <= 1)
        return 1
    return n * factorial(n-1);
})(5); // 입력한 매개변수가 위 인자로 들어감

함수 값


  • typeof 함수 ⇒ function, 함수는 객체
  • 파라메터에 함수이름 ⇒ 콜백 함수
  • 함수를 리턴할 수도 있음.
function a(b, c) {
    return b() + c()
}

function f1() {
    return 1;
}

function f2() {
    return 2;
}

a(f1, f2) // f1, f2를 콜백함수라고 함

function a(b, c) {
    return function() {
        return b() + c(); // 여기서 b + c 하면 함수 코드 문자열 자체가 더해지는듯..
    };
}

function f1() {
    return 1;
}

function f2() {
    return 2;
}

console.log(a(f1, f2)()) // 괄호를 하나 더 써줘서 바로 함수 호출하도록

Parameter


  • 함수 선언에서 function a(b,c) 에서 b,c는 파라메터
  • a('1', '2')에서 '1', '2'는 argument
  • 파라메터에 기본값 적용 가능
    • function a(b='1', c)
    • 기본값 없으면 전달 안되었을 시 undefined
  • argument는 순서대로 전달
  • undefined 전달시 기본값 사용
    function a(b=100, c=b+50) { 
      console.log(b + c); 
    } 
    a(undefined, undefined); // 250

Argument


  • 함수 호출시 a(b, c)에서 b,c는 argument

  • Argument의 개수에 따라 유연하게 동작하는 함수

      function a(b, c, d) {
          arguments // argument에 어떤것들이 전달되었는지
          for (let arg of arguments) {
              console.log(arg);
          }
      }
    
      a('a', 'b', 'c', 'd')
    • 따라서, 변수/함수명을 arguments로 지어서는 안됨!!
  • 파라메터의 개수보다 적거나 많이 입력하더라도 입력한 개수만큼 출력

  • 유사배열 → 배열의 메서드 사용 불가능

  • 인덱싱을 통한 세분화가 필요함.

Rest Parameter


  • ...변수명으로 선언
  • args가 배열이므로 배열의 메서드들 사용 가능
  • 일반 파라메터와 함께 사용 가능, 하지만 앞에 정의된 파라메터에 argument를 먼저 할당하고 나머지 argument를 배열로 묶으므로 가장 마지막에 선언해주어야 함
function a(...args) {
    arguments // argument에 어떤것들이 전달되었는지
    for (let arg of args) {
        console.log(arg);
    }
}

a('a', 'b', 'c', 'd')

function a(...args) { // 단 3개만 나오도록
  let temp = args.slice(0, 3);
    for (let arg of temp) {
        console.log(arg);
    }
}

a('a', 'b', 'c', 'd')
// 맨 앞 아규먼트만 빼고 나머지 출력하기
function ignoreFirst(a, ...args) {
  for (let arg of args) {
    console.log(arg)
  }
}

function ignoreFirst(...args) {
    args.shift()
  for (let arg of args) {
    console.log(arg)
  }
}

Arrow Function


  • 파라메터 1개 → 소괄호 생략 가능
  • 파라메터가 없거나 2개이상 → 소괄호 필수
  • return문 한개만 존재한다면 return문도 생략 가능
  • return문 외에 다른 구문 필요시 생략 불가능
  • return문이 객체인 경우는 함수의 중괄호와 헷갈릴 수 있으므로 () 감싸주어야 함.
  • arguments 객체 사용하는 경우는 Arrow Function으로 바꾸기 어려움.
  • rest parameter은 사용 가능.
const calc = (a, b)=>{
    return a + b;
}

const calc = (a,b) => a+b;

const calc = (a,b) => ({answer: a+b}); // 소괄호 빼면 오류

This


  • this : 함수를 호출하는 객체를 가르키는 키워드
    • 호출한 객체에 따라 값이 달라짐.
  • Arrow Function에서의 this는 arrow function이 선언되기 직전에 유효한 this 값
  • 다른 객체(a)의 메소드에서 this를 사용하더라도, 또다른 객체(b)가 해당 메소드(a.f)를 가져와서 사용하는 경우 this에는 b가 들어간다.
console.log(this) // window

const obj = {
    a: "11",
    b: "22",
    f: function () {
        console.log(this)
    }
}

const obj2 = {
    a: "112",
    b: "223",
    f: function () {
        console.log(this)
    },
      f2: obj.f
};

obj.f(); // obj
obj2.f(); // obj2
obj2.f2(); // obj2

조건 연산자


  • if문을 간결하게 표현
  • 표현식 ? true일때 : false일때
if (조건) {
} else {
}

switch(변수) {
    case 1:
        break
    default:
}

// 조건 ? truthy일때 표현식 : falsy일때 표현식

function half(i) {
    return i>50 ? true : false;
}

console.log(half(10)) // false

Spread 구문


  • 배열의 요소를 펼쳐줌
const numbers = [1, 2, 3]

console.log(...numbers); // 1,2,3으로 출력됨.
console.log(1, 2, 3)
  • slice()로 배열 복사해야 하는 문제점 해소 및 배열 concat시 사용
const numbers = [1, 2, 3]
const numbers_copy = [...numbers, 4]
const numbers2 = [4, 5, 6]
const numbers_concat = [...numbers, ...numbers2]

function a(b, c, d) {
    return b + c + d;
}

a(...numbers); // spread, numbers를 여러개의 값으로 펼침

// ...numbers를 일반 변수에 대입 X

console.log({...numbers}) // 객체화 하는 경우 0:1, 1:2, 2:3 이런식으로 ..
  • 객체 Spread
    • 해당 객체의 프로퍼티들이 펼쳐지면서 복사 가능
      const p = { 'a': 1, 'b': 2 } const q = { ...p, 'c': 3 }
    • 새로운 배열 생성 / 함수 아규먼트 사용 불가능 (배열 spread는 가능)

모던한 프로퍼티 표기법


  • 프로퍼티명과 변수/함수명이 같은 경우 프로퍼티명만 써주어도 됨.

  • const a = 'a'; const b = 'b'; const c = 'c'; const obj = { a, // == a:a b, c, }; console.log(obj)

  • 객체 내부에서 function 선언하는 경우 :(콜론 기호)와 function 키워드 생략 가능

      const obj = {
          c() {
              return 5;    
          }
      }
    
      obj.c();
  • ⇒ 함수 이름이 반드시 필요하기 때문에 Arrow Function 사용시도 이름 써주어야 함.

  • 프로퍼티명을 표현식으로

    const obj = { //[표현식]:값 
      ["a" + "b"]:1 
    }

옵셔널 체이닝


  • 중첩 객체에서 프로퍼티 확인 방법

    • a객체 내부의 b객체가 null이나 undefined라면 undefined 리턴

    • 아니라면 a.b.c 리턴

      const a = 'a'
      const b = 'b'
      const obj = {
        a,
        b,
        c: {
            d: 'hello world!'
        }
      }
      
      const obj2 = {
        a,
        b,
      }
      
      function check(obj) {
        return obj.c?.d;
      }
      
      console.log(check(obj)) // hello world!
      console.log(check(obj2)) // undefined
        function check(a) { 
          return a.b?.c; 
        }

Destructuring(구조 분해)


  • 배열 순서에 따라 값 매핑

    const arr = ['a', 'b', 'c', 'd'] 
    const [r1, r2, r3, r4] = arr // 인덱스에 따라 순서대로 할당, arr이 더 길더라도 순서대로만 
    const [r1, r2, r3, ...r4] = arr // r1~r3은 순서대로 할당, 나머지 값들은 r4에 넣어줌 
    const [r1='1', r2, r3, r4] = arr // 기본값 입력 가능 
    // Destructuring을 활용한 swap 
    let a = 10; 
    let b = 15; 
    [a, b] = [b, a] 
    console.log(a + "//" + b) 
    // 만약 arr의 길이가 더 짧다면 매핑 안되는 부분은 undefined 
    /* r1 = arr[0] r2 = arr[1] r3 = arr[2] */`
  • 객체 Destructuring

    • 프로퍼티 이름에 대해 매핑
    • Rest → {프로퍼티명, ...프로퍼티명} = 객체
      const obj = { a: 'a' b: 'b' } 
      const { a, b } = obj //
      const { a: d, b: e} = obj // d, e로 선언(이름 지정) 
      // 객체 내부에 변수 이름으로 사용할수 없는 프로퍼티명이 있는 경우 반드시 필요 
      // [] 사용하여 표현식 쓸수 있음. 
      const { a: d, b: e, c=123 } = obj // 기본값 지정 
      const { a, ...rest } = obj
      console.log(a) 
      console.log(b)
      

    ```

    • 파라메터에서 Destructuring → DOM 이벤트 다룰때 유용하게 사용 가능에러


      • 자바스크립트에서 에러 발생시 프로그램이 멈춰버리는 문제

      • 에러 객체의 프로퍼티

        • name
        • message
        const myerror = new TypeError('Type Error가 발생했습니다.');
        myerror.name
        myerror.message
        
        throw myerror; // 에러 발생시키기
      • Try - catch문

        • Try문에서도 에러 발생 이후의 코드는 실행되지 않음. 바로 catch로 넘어감
        • 에러 발생시 catch문으로 바로 내려감
        • 프로그램이 종료되지 않음.
        • 실행조차 안되는 코드는 실행되지 않음(문법 에러 등)
          try { 
          // 코드 
          } catch (error) { // 에러 발생시 동작 // 
          console.error => 실제 에러처럼 출력 가능 
          } 
          Finally
          • 최종적으로 실행될 코드를 다룰 때 활용
          • 에러 유무와 관련 없음. 무조건 실행.
          • finally에서 에러가 발생하는 경우 중첩 try-catch문으로 해결 가능
              button.addEventListener('click', (event) => { event.target.toggle('a') });
            button.addEventListener('click', ({target}) => { target.classList.toggle('a') }); 
            button.addEventListener('click', ({target}) => { const {classList} = target; classList.toggle('a'); });                         button.addEventListener('click', ({target: { classList }}) => { classList.toggle('a') });

'Language > JavaScript' 카테고리의 다른 글

[ JavaScript ] 객체지향 프로그래밍  (0) 2021.07.30
[ JavaScript] 배열, 모듈  (0) 2021.07.29
[ JavaScript ] 데이터 타입  (0) 2021.07.29
[JavaScript] 몰랐던 문법  (0) 2021.07.26
[JavaScript] 이벤트 처리  (0) 2021.07.26

데이터 타입


기본형

  • Number
  • String
  • Boolean
  • Symbol → 유일한 값
  • BigInt → 아주 큰 숫자를 다룰 때
  • Null
  • Undefined

참조형

  • object

Symbol, BigInt


  • Symbol

    • 유일한 값을 가진 변수 이름

      const symbol = Symbol('aa')
    • 다른 어떤 값과 비교해도 true가 될 수 없는 고유한 변수

    • 똑같은 설명 붙이더라도 False

  • BigInt

    • 기본적으로 JS는 253-1 ~ 253+1, 해당 범위보다 큰 정수 표현할 때 사용됨.

    • 정수형 뒤에 알파벳 n 붙이거나 BigInt 함수 사용

      90512512521512n
      BigInt(90512512521512)
    • 소수 표현 사용 불가능 (1.5n같은 경우 사용 x)

    • 소수 리턴되는 연산은 소숫점 아래 버림

      10n / 6n // 1n
    • BigInt끼리만 연산 가능, 서로 다른 타입의 경우 명시적 타입 변환 해주어야 함.

      5n * 6n
      5n * 6 // 에러
      5n * BigInt(6)
      Number(5n) * 6

typeof


  • typeof(a), typeof a 두가지로 사용 가능
  • typeof null → object
  • typeof function → function

Boolean


  • Falsy 값 : false, null, undefined, NaN, 0, '' ⇒ False 처리
  • Truthy 값 : Falsy값이 아닌 나머지 값 ⇒ True 처리

AND/OR


  • AND
    • 왼쪽값이 True이면 오른쪽값 리턴
    • 왼쪽값이 False이면 왼쪽값 리턴
  • OR
    • 왼쪽값이 True이면 왼쪽값 리턴
    • 왼쪽값이 False면 오른쪽값 리턴

NULL 병합 연산자(??)


  • const example = null ?? 'a';
    • 왼쪽에 null이나 undefined → 오른쪽 값 리턴
    • 왼쪽이 null이나 undefined가 아님 → 왼쪽 값 리턴
    • FALSY값 확인하는게 아닌것에 유의 !!

변수와 스코프


  • var : 비권장
    • 변수를 만들기도 전에 사용 가능한 문제(hoisting)
    • 중복 선언 가능한 문제
    • 함수가 아닌 조건문, 반복문 내에서 선언한 변수도 사용가능한 문제
  • let, const : 권장
    • 변수 만들기 전에는 접근 불가능
    • 중복 선언 불가능
    • 코드 블록 범위

'Language > JavaScript' 카테고리의 다른 글

[ JavaScript] 배열, 모듈  (0) 2021.07.29
[ JavaScript ] 함수, 표기법, 예외 처리  (0) 2021.07.29
[JavaScript] 몰랐던 문법  (0) 2021.07.26
[JavaScript] 이벤트 처리  (0) 2021.07.26
[JavaScript] 배열  (0) 2021.07.25

문제 설명


문제

0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라.

예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2 의 경우에는 1 ≤ 2 ≤ 2 ≤ 4 ≤ 4 ≤ 5 ≤ 7 ≤ 7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4, 1, 3, 3, 2, 2, 9, 2, 3 의 경우에는 3 ≥ 3 ≥ 2 ≥ 2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1, 5, 3, 6, 4, 7, 1, 3, 2, 9, 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다.

입력

첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.

출력

첫째 줄에 가장 긴 길이를 출력한다.


풀이 과정

  1. DP 테이블을 2개 구성한다 (증가, 감소)
    • up_dp, down_dp는 모두 기본값을 1로 구성한다(자기 자신만으로 구성된 수열의 길이:1)
    • seq[i] <= seq[i-1]인 경우 down_dp[i] = down_dp[i-1] + 1
    • seq[i] >= seq[i-1]인 경우 up_dp[i] = up_dp[i-1] + 1
  2. 테이블을 모두 채웠으면 down_dp의 최댓값, up_dp의 최댓값중 큰 값을 리턴하면 된다.

소스 코드

import sys

input = sys.stdin.readline

n = int(input().rstrip())
sequence = list(map(int, input().rstrip().split()))

down_dp = [1] * n
up_dp = [1] * n

for i in range(1, n):
    if sequence[i-1] <= sequence[i]:
        up_dp[i] = up_dp[i-1] + 1
    if sequence[i-1] >= sequence[i]:
        down_dp[i] = down_dp[i-1] + 1

print(max(max(up_dp), max(down_dp)))

문제 설명


문제

혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 문제를 만들려 한다.

int fibonacci(int n) { // 호출
  if (n < 2) {
    return n;
  } return
  fibonacci(n-2) + fibonacci(n-1);
}

위와 같이 코딩하였을 때 fibonacci(n)를 입력했을 때에 fibonacci 함수가 호출되는 횟수를 계산해보자.

입력

fibonacci 함수에 인자로 입력할 n이 주어진다. (0 ≤ n ≤ 50)

출력

fibonacci 함수가 호출된 횟수를 출력한다.

출력값이 매우 커질 수 있으므로 정답을 1,000,000,007 로 나눈 나머지를 출력한다.


풀이 과정

  1. 아래에서부터 바텀-업 방식으로 진행
    • fibonacci(0)일때는 1번 호출하므로 dp[0] = 1
    • fibonacci(1)일때는 1번 호출하므로 dp[1] = 1
  2. fibonacci(n >= 2) 일때는, fibonacci(n-1)을 호출하므로 fibonacci(n-1)번, fibonacci(n-2)를 호출하므로 fibonacci(n-2)번, 그리고 자기 자신까지 +1해주면 된다.
    • 즉, dp[i] = dp[i-1] + dp[i-2] + 1
  3. 마지막으로 dp[n]을 1000000007로 나눈 나머지 값을 출력하면 된다.

소스 코드

import sys

n = int(sys.stdin.readline().rstrip())
dp = [0] * (n+1)
if n <= 1:
    print(1)
else:
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2] + 1

    print(dp[n] % 1000000007)

문제 설명


문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.


풀이 과정

  1. i원이 되기 위해서는 i-2원에서 2원짜리를 주던가, i-5원에서 5원짜리를 주던가 두가지 경우밖에 없다.
  2. 따라서 점화식을 dp[i] = min(dp[i-2]+1, dp[i-5]+1)로 세우면 된다.
  3. 도달 불가능한 금액이 있을수 있으므로 초기값을 INF로 두고, dp[n]이 INF라면 -1을 출력하면 된다.

소스 코드

import sys

n = int(sys.stdin.readline().rstrip())
INF = int(10e9)
dp = [INF] * (n+1)
dp[0] = 0

for i in range(1, n+1):
    if i-2 >= 0:
        dp[i] = min(dp[i], dp[i-2]+1)
    if i-5 >= 0:
        dp[i] = min(dp[i], dp[i-5]+1)


if dp[n] == INF:
    print(-1)
else:
    print(dp[n])

문제 설명


문제

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

입력

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.

셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다.


풀이 과정

  1. Dijkstra 알고리즘 및 최소 히프 사용해서 시간 단축
  2. 현재 시점에서 거리가 가장 짧은 노드 선택해서(최소 히프 사용) 연결된 노드들의 최단 경로 갱신
    • 최단 경로가 갱신된 경우 최소 히프에 등록
  3. 과정을 반복하다 보면 .. 히프에 하나의 노드로 가는데 거리가 여러개가 나올 수 있음. [거리, 노드]라고 할때 [4, 9], [7, 9]
    • 따라서, 처음에 히프에서 빼줄 때, 현재 거리와 비교하는 과정 필요, ==> 이과정을 생략하면 시간 초과 나옴.
  4. 최단 경로도 알아야 하므로, parent 배열에 자신을 방문하기 이전 노드들의 정보를 저장함.
    • 1->2 라고 할때, parent[2] = 1

소스 코드

import sys
import heapq

input = sys.stdin.readline
n = int(input().rstrip())
m = int(input().rstrip())
INT_MAX = int(10e9)

graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().rstrip().split())
    graph[a].append([b, c])

start, end = map(int, input().rstrip().split())
distance = [INT_MAX] * (n+1)
parent = [i for i in range(n+1)]
distance[start] = 0
candidate = [[0, start]]
while candidate:
    dist, node = heapq.heappop(candidate)
    if dist > distance[node]:
        # 갱신된 경우에는 넘겨줌
        continue
    for next_node, cost in graph[node]:
        if dist + cost < distance[next_node]:
            distance[next_node] = dist + cost
            parent[next_node] = node
            heapq.heappush(candidate, [distance[next_node], next_node])

print(distance[end])
answer = []
temp = end
while parent[temp] != temp:
    answer.append(temp)
    temp = parent[temp]
answer.append(start)
print(len(answer))
answer.reverse()
print(" ".join(list(map(str, answer))))

문제 설명


문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.


풀이 과정

  1. n에 도달하기 위해서는 n-1에서 1 더하거나, n-2에서 2 더하거나, n-3에서 3 더하는 방법밖에 없음.
  2. 따라서 dp를 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]으로 해주면 된다.
  3. 이 때, 그냥 해주면 수가 너무 커지게 되서 시간 초과가 나옴.
    • 매 순간 더해주는 값과 결과에 % 100000009를 해주어야 함.

소스 코드

import sys

input = sys.stdin.readline
n = int(input().rstrip())

dp = [0] * 1000001
a = 1
b = 2
c = 4
d = 0
for j in range(4, 1000001):
    d = (a + b + c) % 1000000009
    a = b % 1000000009
    b = c % 1000000009
    c = d % 1000000009
    dp[j] = d

for i in range(n):
    tc = int(input().rstrip())
    if tc == 1:
        print(1)
    elif tc == 2:
        print(2)
    elif tc == 3:
        print(4)
    else:
        print(dp[tc]) 

+ Recent posts