문제 설명

문제

캡틴 이다솜은 자신의 해적선에 적을 공격하기 위한 대포알을 많이 보관해 놓는다. 다솜이는 미적감각이 뛰어나기 때문에, 대포알은 반드시 사면체 모양으로 쌓아놓아야 한다고 생각한다. 사면체를 만드는 방법은 길이가 N인 정삼각형 모양을 만든다. 그 위에 길이가 N-1인 정삼각형 모양을 얹고 그위에 계속 해서 얹어서 1크기의 정삼각형 모양을 얹으면 된다.

각각의 삼각형은 1, 3, 6, 10 ,..... 와 같이 대포알을 가지고 있다. 따라서 완벽하게 쌓았을 때, 한 사면체에는 1, 4, 10, 20 ,.... 개를 가지고 있을 것이다.

현재 다솜이의 해적선에 대포알이 N개가 있다. 다솜이는 영식이를 시켜서 사면체를 만들게 하고 싶다. 영식이는 물론 하기 싫지만 어쩔수 없이 다솜이가 시키는대로 사면체를 가능한 최소 개수 만큼 만들려고 한다. N개의 대포알로 만들 수 있는 사면체의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 입력 N이 들어온다. N은 300,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 영식이가 만들 수 있는 사면체 개수의 최솟값을 출력한다.

풀이 과정

1. 사면체가 될수있는 경우의 수를 테이블에 저장 및 DP테이블에 1로 설정한다. (최솟값이므로)
   • 즉, 경우의 수 테이블에는 [1, 4, 10, 20, ... ]이 저장된다.
   • DP[1] = 1, DP[4] = 1, DP[10] = 1, ... 이 저장된다.
2. 이후 Bottom-up 방식으로 DP테이블을 채워나가면 된다.
   • i개 대포알로 만들수 있는 최소 개수를 구할 때, 저장해 둔 경우의 수 테이블의 값들을 j라고 한다면
   • DP[i] = min(DP[i], DP[i-j[k]]) (i-j[k] > 0) 일때
3. 이후 DP[n]을 출력하면 된다.

소스 코드

import sys


N = int(sys.stdin.readline().rstrip())
curr = 1
step = 1
k = 1
area = 1
INT_MAX = int(10e9)
dp = [INT_MAX] * 300001
four = [1]
dp[1] = True
dp[0] = True
# 사면체 경우의 수 구하는 부분
while True:
    if N == area:
        print(1)
        sys.exit(0)
    if N < area:
        break
    k += 1
    curr += k
    area += curr
    four.append(area)
    if area <= 300000:
        dp[area] = 1

# dp 테이블 채우는 부분
for i in range(1, N+1):
    for j in four:
        if i - j > 0:
            dp[i] = min(dp[i], dp[i-j]+1)

print(dp[N])

비동기 실행

• Start! → end! → fetch 실행

console.log('start!')

fetch('https://jsonplaceholder.typicode.com/users')
    .then((response) => response.text())
    .then((result) => {console.log(result);});

console.log('end!')

• then 메소드 : 콜백을 등록하는것, 실행하지는 않음.
• 따라서 end가 먼저 실행되고, 서버의 response가 도착하면 콜백이 실행됨.
• fetch → promise 객체 리턴, 비동기 실행과 연관 있음.

비동기 실행

• 특정 작업을 시작하고 완벽하게 다 처리하기 전에, 실행 흐름이 바로 다음 코드로 넘어가고 나중에 콜백이 실행되는 것

• 동기 실행 → 한번 시작한 작업을 다 처리하고 나서 다음코드로 넘어감

  비동기 실행 함수

  1. setTimeout 함수

     • 특정 함수의 실행을 원하는 시간만큼 뒤로 미루기 위해 사용하는 함수

       console.log('start!')
       
       setTimeout(() => { console.log("end1"); }, 2000) // 2초 뒤
       
       console.log('end2')

  2. setInterval 함수

     • 특정 콜백을 일정한 시간 간격으로 실행하도록 등록하는 함수

       console.log('start!')
       
       setInterval(() => { console.log("end1"); }, 2000) // 2초 간격으로 계속 실행
       
       console.log('end2')

  3. addEventListener

     • 특정 조건(클릭 등)이 만족될때 마다 실행

       btn.addEventListener('click', (e) => {
         // 처리 내용
       });

  • fetch 함수는 좀 더 새로운 방식으로 비동기 실행을 지원하는 자바스크립트 문법
    • Promise 객체 리턴
    • Promise 객체 : 비동기 실행을 지원하는 또 다른 종류의 문법

Promise

• 작업에 관한 상태 정보를 갖고 있는 객체
• 작업이 성공했는지 실패했는지 알 수 있음.
  • pending - 작업 진행 중
  • fulfilled - 작업 성공 → 작업의 성공 결과또한 가지고 있음.(fetch의 then의 response)
  • rejected - 작업 실패 → 작업의 실패 이유에 대한 정보또한 가지고 있음.
• then 메소드도 Promise의 메소드

fetch('https://jsonplaceholder.typicode.com/users')
    .then((response) => response.text())
    .then((result) => {console.log(result);});
// then은 pending->fulfilled 상태가 되었을때 실행할 코드 등록
// 작업 성공 결과는 콜백의 첫번째 파라메터

Promise Chaining

• then메서드 뒤에 then메서드를 붙이는 것
• Promise 객체를 계속해서 연결
• then 메서드가 새로운 Promise 객체를 리턴함.
  • 가장 처음에는 Pending 상태
  • callback에서 리턴하는 값에 따라 달라짐
    1. promise 객체 리턴 ⇒ 콜백에서 리턴한 promise 객체와 같은 상태, 같은 정보
    2. promise가 아닌것 리턴 ⇒ fulfilled 상태, 작업 성공 결과 : return값

fetch('https://jsonplaceholder.typicode.com/users')
    .then((response) => response.text()) // text 메서드는 promise 리턴
    .then((result) => {
        return 'a';
    }).then((t) => { console.log(t); });

• response.text(), response.json() ⇒ promise 객체 리턴
• 비동기 작업을 순차적으로 실행할 때, 전체 코드를 깔끔하게 하기 위해 사용

Rejected 상태일때의 콜백

• then 메서드의 두번째 인자에 error시의 콜백함수
• 작업 실패 시 작업 실패 정보가 들어옴

fetch('https://jsonplaceholder.typicode.com/users')
    .then((response) => response.text(), (error) => { console.log(error); }) 
    .then((result) => {
        return 'a';
    }).then((t) => { console.log(t); });

• 콜백 실행 중간에 에러 발생 시
  • Rejected, 작업 실패 정보로 에러 객체를 가짐.

Callback

1. Promise 객체 이외의 값 리턴

   → fulfilled, 작업 성공 결과로 해당 값 가짐

2. 콜백의 리턴이 없음

   → fulfilled, undefined 리턴한 것으로 간주

3. 콜백 내부 에러

   → rejected, 작업 실패 정보로 에러 객체

4. 콜백이 없을때

   → 이전 promise 객체와 동일한 상태와 정보를 가짐.

Catch

• promise rejected시 실행되는 코드 지정(then메서드의 두번째 콜백 안써줌)

• Catch 메서드는 fulfilled 리턴

• then 메서드를 변형한것과 같음.

  • then(undefined, (error) => { console.log(error); })

  • 에러가 발생하더라도 then메서드를 타고 내려간다. 종료 X (에러 객체가)

    fetch('https://jsonplaceholder.typicode.codddm/users')
      .then((response) => response.text())
      .catch((error) => { console.log(error); })
      .then((result) => {
          return 'a';
      }).then((t) => { console.log(t); });

• catch 메소드는 마지막에 쓰인다.

  • 어디서 에러가 생기던지 간에 가장 잘 대처하는 방법

  • 넘어온 에러는 name과 message 프로퍼티를 통해 살펴볼 수 있다.

    fetch('https://jsonplaceholder.typicode.codddm/users')
      .then((response) => response.text())
      .then((result) => {
          return 'a';
      })
      .then((t) => { console.log(t); })
      .catch((error) => { console.log(`${error.name}이고, 이유는.. ${error.message}`); });

• 에러 발생시 대안을 뒤로 넘겨줄 수 있다면 catch를 중간에 써도 됨.

  • 작업을 살릴수 있는 방법이 있다면 Promise Chaining 중간에 catch
  • 예시로 .. A → B → C로 넘겨줄 때, B에서 에러가 발생한 경우 D로 대체할 수 있다면 catch문에서 B를 D로 대체 후 진행.
    • A → D → C

Finally

• 성공하던지, 실패하던지 상관 없이 항상 실행하고 싶은 코드 등록

• catch보다도 뒤에 작성

  • 파라메터는 따로 필요하지 않음

    fetch('https://jsonplaceholder.typicode.codddm/users')
      .then((response) => response.text())
      .then((result) => {
          return 'a';
      })
      .then((t) => { console.log(t); })
      .catch((error) => { console.log(`${error.name}이고, 이유는.. ${error.message}`); })
      .finally(() => {console.log('i am finally')});
    
    fetch('https://jsonplaceholder.typicode.codddm/users')
      .then((response) => response.text())
      .then((result) => {
          return 'a';
      })
      .then((t) => { console.log(t); })
      .catch((error) => { 
          console.log(`${error.name}이고, 이유는.. ${error.message}`);
          new Error('error!!'); 
      })
      .finally(() => {console.log('i am finally')});

Promise 객체의 등장 배경

• Promise가 없다면?

  • 콜백 지옥 또는 콜백 헬(callback hell), 지옥의 피라미드

    fetch(url, function c1() {
      fetch(url, function c2() {
          fetch(url, function c3() {
              ...
          }
      }
    })

• 콜백 헬 문제 해결, 비동기 작업 처리에 관한 좀 더 세밀한 처리 가능

Promise 생성

const prom = new Promise((resolve, reject) => {
    //setTimeout(() => { resolve('success');}, 2000);
    setTimeout(() => { reject(new Error('fail')); }, 2000);
});

//prom.then((result) => {console.log(result);})
prom.catch((error) => {console.log(error);})

• resolve, reject ⇒ 'executor' 함수
• resolve ⇒ fulfilled로 만들수 있는 함수
• reject ⇒ rejected로 만들수 있는 함수

resolve, reject 사용하여 바로 생성

const prom1 = new Promise.resolve('success'); // fulfilled 상태의 promise 객체 생성
const prom2 = new Promise.reject(new Error('fail')); // fail 상태의 promise 객체 생성

// prom1은 then의 첫번째 파라메터 실행
// prom2는 then의 두번째 파라메터나 catch

Promise 객체는 언제 생성?

1. 전통적인 형식의 비동기 실행 함수를 사용하는 코드를 Promise 기반의 코드로 변환

   • Promise Chaining 안에서 setTimeout 등 비동기 실행 함수 사용시 리턴값을 Promise Chain에서 사용할수 없음.

   • Promise 객체 생성

       function wait(text, milliseconds) {
         const p = new Promise((resolve, reject) => {
           setTimeout(() => { resolve(text); }, 2000);
         });
         return p;
       }
     
       fetch('https://jsonplaceholder.typicode.com/users')
         .then((response) => response.text())
         .then((result) => wait(`${result} plus alpha`, 2000))
         .then((result) => { console.log(result); });

   • Promisify

     • 비동기 실행 함수를 Promise 객체로 감싸서 Promise 객체를 리턴하는 형식으로 만드는 작업

• 콜백을 여러번 하는 경우(setInterval, EventListener)

  • Promisify 해서는 안된다.

    ⇒ 한번 pending에서 fulfilled/rejected 상태가 되면 그 뒤로는 상태와 결과가 바뀌지 않음.

여러 Promise 객체

all 메소드

Promise
.all([프로미스 객체, ... ])
.then((results) => {
    console.log(results); // array
});

• 모든 객체가 fulfill 되기까지 기다림
• 하나라도 reject가 되면 all 메소드는 reject 프로미스 리턴
• 하나의 작업이라도 실패하면 전체 작업이 실패할 때 사용

race 메소드

Promise
.race([프로미스 객체, ...])
.then((result) => {
    console.log(result); // 단일 객체
});

• 가장 먼저 fulfilled / reject 상태가 되는 Promise 객체와 동일한 상태/결과인 Promise 리턴

allSettled

• fulfilled와 rejected 상태를 묶어서 settled 상태라고 한다.
• 배열 내의 모든 Promise 객체가 fulfilled / rejected 상태가 되기까지 기다림,
• 각 Promise 객체의 최종 상태(status), 작업 성공결과(value)/작업 실패정보(reason) 리턴

any

• Promise 객체중 가장 먼저 fulfilled 상태가 된 Promise 객체의 상태/결과 반영
• 모든 Promise 객체가 rejected 상태가 되면 AggregateError 에러 (rejected)

axios

• Ajax 통신을 할 수 있는 또다른 방법

axios
  .get('https://jsonplaceholder.typicode.com/users')
  .then((response) => {
    console.log(response);
  })
  .catch((error) => {
    console.log(error);
  });

• axios에서도 promise 객체를 리턴한다.
• axios는 별도의 패키지 다운로드가 필요함.
• axios의 기능 / 장점
  • 모든 리퀘스트, 리스폰스에 대한 공통 설정 및 공통된 전처리 함수 삽입 가능
  • serialization, deserialization을 자동으로 수행
  • 특정 리퀘스트에 대해 얼마나 오랫동안 리스폰스가 오지 않으면 리퀘스트를 취소할지 설정 가능(request timeout)
  • 업로드 시 진행 상태 정보를 얻을 수 있음
  • 리퀘스트 취소 기능 지원

문제 설명

문제

양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.

무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.

구슬이 3g인 경우 아래 <그림 1>과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다.

<그림 1> 구슬이 3g인지 확인하는 방법 (1은 1g인 추,4는 4g인 추, ●은 무게를 확인할 구슬)

<그림 2>와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다.

추들의 무게와 확인할 구슬들의 무게가 입력되었을 때, 주어진 추만을 사용하여 구슬의 무게를 확인 할 수 있는지를 결정하는 프로그램을 작성하시오.

<그림 2> 구슬이 5g인지 확인하는 방법

입력

첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무게는 500g이하이며, 입력되는 무게들 사이에는 빈칸이 하나씩 있 다. 세 번째 줄에는 무게를 확인하고자 하는 구슬들의 개수가 주어진다. 확인할 구슬의 개수는 7이하이다. 네 번째 줄에는 확인하고자 하는 구슬들의 무게가 자연수로 주어지며, 입력되는 무게들 사이에는 빈 칸이 하나씩 있다. 확인하고자 하는 구슬의 무게는 40,000보다 작거나 같은 자연수이다.

출력

주어진 각 구슬의 무게에 대하여 확인이 가능하면 Y, 아니면 N 을 차례로 출력한다. 출력은 한 개의 줄로 이루어지며, 각 구슬에 대한 답 사이에는 빈칸을 하나씩 둔다.

풀이 과정

1. 추를 오름차순으로 두면서, 각각의 추를 둘 때 가능한 경우의 수는 3가지이다.
   • 추를 왼쪽에 둘 때
   • 추를 오른쪽에 둘 때
   • 현재 추만 오른쪽에 두고 왼쪽에 추를 모두 두었을 때
2. 따라서, 위의 3가지 경우의 수로 DP를 구성하면 된다.
3. 마지막으로 각각의 구슬에 대해, 확인 가능 여부를 출력해주면 된다.

소스 코드

import sys

input = sys.stdin.readline

weights_count = int(input().rstrip())
weights = list(map(int, input().rstrip().split()))

marbles_count = int(input().rstrip())
marbles = list(map(int, input().rstrip().split()))

dp = [False] * 40001
dp[0] = True

for weight in weights:
    canmake = set()
    for i in range(40001):
        if dp[i] == True:
            if i + weight <= 40001:
                canmake.add(i+weight) # 오른쪽에 놓았을때,
            if i - weight >= 0:
                canmake.add(i-weight) # 왼쪽에 놓았을 때
            if weight - i >= 0:
                canmake.add(weight-i) # 현재 물체만 오른쪽에 두고 나머지는 왼쪽에 두었을 때
    for c in canmake:
        dp[c] = True

for marble in marbles:
    if dp[marble] == True:
        print('Y', end=" ")
    else:
        print('N', end=" ")

JSON

• JSON 데이터 Response 받는 코드

fetch('https://jsonplaceholder.typicode.com/users')
    .then((response) => response.text())
    .then((result) => { console.log(result) });

• JSON(JavaScript Object Notation)

  • 자바 스크립트의 문법과 비슷

  • 사용자 하나의 정보를 객체로 표현(중괄호 이내에 프로퍼티)

  • 여러개의 데이터를 대괄호([])로 표현

  • 프로퍼티의 이름을 반드시 큰따옴표("") 사용해주어야 한다.

  • 값이 문자열인 경우 반드시 큰따옴표("") 사용

  • undefined, NaN, Infinity 등 사용 불가능

  • 주석 추가 불가능

    {
     "attr1":"문자문자열",
     "attr2":0,
     "attr3":15,
     "attr4":["문자열1", "문자열2"]
    }

JSON ↔ 객체 변환

• 문자열 → JSON 객체 변환

fetch('https://jsonplaceholder.typicode.com/users')
    .then((response) => response.text())
    .then((result) => { 
        const users = JSON.parse(result); 
        console.log(users.length);
        console.log(users);
        users.forEach((element) => {
            console.log(element.name);
        });
    });

• parse의 결과 배열이 리턴되었음. 아마 가장자리가 []로 되어있어서 그런듯.
• [ ]로 안되있는 경우 테스트.

const test = '{"a":"b"}'
console.log(JSON.parse(test));

• 그냥 Object가 나타나는것을 볼 수 있음.

CRUD

• 웹 브라우저가 서버로 보내는 리퀘스트의 종류에 크게 4가지 종류

1. GET : 기존 데이터 조회
2. POST : 새 데이터 추가
3. PUT : 기존 데이터 수정
4. DELETE : 기존 데이터 삭제

Request 테스트

• 사이트 => 비공개

• 전체 직원(GET)

    fetch('https://../api/members')
        .then((response) => response.text())
        .then((result) => { 
            console.log(result);
        });

• 특정 직원(GET)

    fetch('https://../api/members/3')
        .then((response) => response.text())
        .then((result) => { 
            console.log(result);
        });

• 직원 추가(POST)

  • fetch에 새로운 argument(옵션 객체) 추가

    • 옵션 객체에 method와 body 추가

  • JSON.stringify : 객체를 JSON 데이터로 변환

    const newMember = {
      name: 'Jerry',
      email: 'jerry@codeitmall.kr',
      department: 'engineering',
    }
    
    fetch('https://../api/members', {
      method: 'POST',
      body: JSON.stringify(newMember),
    }).then((response) => response.text())
      .then((result) => { console.log(result) });

• 직원 변경(PUT)

    const member = {
        name: 'Alice',
        email: 'alice@codeitmall.kr',
        department: 'marketing',
    }
  
    fetch('https://../api/members/2', { // 2번 유저에대한 데이터 수정
        method: 'PUT',
        body: JSON.stringify(member),
    }).then((response) => response.text())
        .then((result) => { console.log(result) });

• 직원 삭제(DELETE)

    fetch('https://../api/members/2', { // 2번 유저에대한 데이터 삭제
        method: 'DELETE',
    }).then((response) => response.text())
        .then((result) => { console.log(result) });

문제 설명

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

풀이 과정

• 문제만으론 정확히 어떤 경우에 이분 그래프인지 몰라서 더 찾아보았다.

• 요약해 보면, 색이 0과 1이 있고, a-b가 연결되어 있을때 a와 b의 색이 다르다 보면 된다.

1. bfs를 활용한다.
   1. 현재 색이 0일때, 인접한 노드의 색을 1로 한다.
   2. 현재 색이 1일때, 인접한 노드의 색을 0으로 한다.
2. bfs 진행 도중에 현재 색과 인접한 노드의 색이 같은 경우에는 이분 그래프가 되지 않는다.
3. 전체 정점에 대해서 이분 그래프인 경우에는 True, 아닌 경우에는 False를 리턴한다.

소스 코드

import sys
from collections import deque

input = sys.stdin.readline

K = int(input().rstrip())

def bfs(graph, visited, start):
    visited[start] = 0 # 시작 색은 0
    queue = deque([[start, 0]])
    while queue:
        e, v = queue.popleft() # 현재 색깔
        value = 1 if v == 0 else 0 # 현재 색깔 전환
        for next_edge in graph[e]:
            if visited[next_edge] == -1:
                queue.append([next_edge, value])
                visited[next_edge] = value
            elif visited[next_edge] == v: # 다음 엣지의 색이 현재 색과 같으면 실패
                return False
    return True # 시작 정점에 대한 bfs 성공


for _ in range(K):
    V, E = map(int, input().rstrip().split())
    graph = [[] for _ in range(V+1)]
    for __ in range(E):
        a, b = map(int, input().rstrip().split())
        graph[a].append(b)
        graph[b].append(a)
    visited = [-1] * (V+1)

    answer = True
    for i in range(1, V+1):
        if visited[i] == -1:
            if not bfs(graph, visited, i):
                answer = False
                break

    if answer:
        print("YES")
    else:
        print("NO")

문제 설명

문제

몇 개의 자연수로 이루어진 두 집합 A와 B가 있다. 집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 빈 칸을 사이에 두고 주어진다. 하나의 집합의 원소는 2,147,483,647 이하의 자연수이며, 하나의 집합에 속하는 모든 원소의 값은 다르다.

출력

첫째 줄에 집합 A에는 속하면서 집합 B에는 속하지 않는 원소의 개수를 출력한다. 다음 줄에는 구체적인 원소를 빈 칸을 사이에 두고 증가하는 순서로 출력한다. 집합 A에는 속하면서 집합 B에는 속하지 않는 원소가 없다면 첫째 줄에 0만을 출력하면 된다.

풀이 과정

• 이진 탐색 문제로도 풀 수 있음. B를 정렬한 후, A의 각 원소를 B에서 이진탐색으로 구현하면 될듯?
• Set의 in연산자를 쓰면 빠르게 해결할 수 있음.

1. A의 원소를 정렬한다. (오름차순으로 출력해야 하므로)
2. B를 Set 자료구조로 바꾼다. (찾을때 리스트보다 훨씬 빠름, 또한 중복되는 원소가 없으므로)
3. A의 각 원소가 B에 존재하는지 확인한다.
   • 있으면 따로 리스트에 저장해 둔다.
4. 리스트의 길이와 리스트의 요소들을 출력해주면 된다
   • python에서 * 쓰면 쉽게 리스트의 요소들 출력 가능(" ".join한것과 같음)

소스 코드

import sys


nA, nB = map(int,sys.stdin.readline().rstrip().split())
A = list(map(int, sys.stdin.readline().rstrip().split()))
B = list(map(int, sys.stdin.readline().rstrip().split()))

A.sort()
B = set(B)
answer = []

for a in A:
    if a not in B:
        answer.append(a)

print(len(answer))
if answer:
    print(*answer)

웹 기초

Fetch

• 크롬 - F12 - 개발자 도구

• https://google.com 접속

• 다음 코드 콘솔에 입력

    fetch('https://www.google.com') // url로 request 요청
        .then((response) => response.text()) // 응답 가져옴, arrow function, 곧바로 리턴
        .then((result) => {console.log(result);}); // 위 콜백이 실행된 다음에 실행. 
        // 위 then의 리턴값이 아래 then의 입력값으로 들어감
  
    // 어떤 조건이 만족되었을때 실행되는 함수 : 콜백 함수
    // .then => 콜백 등록 메소드, fetch가 리턴될 때 호출(promise)
  

  ⇒ fetch 함수를 통해 서버로 request를 보낸 후 응답을 콘솔에 나타냄

  • fetch의 return은 response
    • response의 부가정보와 실제 내용을 가진 객체

URL : Uniform Resource Locator

• 특정 데이터를 나타내는 문자열
• 프로토콜://호스트/경로(path)/쿼리(Query)
• 쿼리는 등호=값, &로 연결되어 있음.
• 프로토콜에 맞게 request / response 해주어야 함.
• http : HyperText Transfer Protocol
• https : http + secure

문제

문제

수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.

이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하면 순서를 적절히 조절하여 순서를 정해줄 수 있다. 또한 같은 방법으로 괄호 등도 필요 없게 된다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다.

중위 표기식을 후위 표기식으로 바꾸는 방법을 간단히 설명하면 이렇다. 우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.

예를 들어 a+b*c는 (a+(b*c))의 식과 같게 된다. 그 다음에 안에 있는 괄호의 연산자 *를 괄호 밖으로 꺼내게 되면 (a+bc*)가 된다. 마지막으로 또 +를 괄호의 오른쪽으로 고치면 abc*+가 되게 된다.

다른 예를 들어 그림으로 표현하면 A+B*C-D/E를 완전하게 괄호로 묶고 연산자를 이동시킬 장소를 표시하면 다음과 같이 된다.

이러한 사실을 알고 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성하시오

입력

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다.

출력

첫째 줄에 후위 표기식으로 바뀐 식을 출력하시오

풀이과정

1. 식을 순차적으로 한자리씩 방문한다.
2. A, B, C등 피연산자는 그대로 출력해준다.
3. 연산자일 때는 스택에 넣어준다.
   • +, - 연산자일때는 괄호('(')를 만나기 전까지 스택에서 모두 빼주고 넣음(곱하기나 나눗셈보다는 우선순위가 낮고, 덧셈, 뺄셈과는 동등)
   • *, / 연산자 일때는 괄호를 만나기 전까지 스택에서 *과 /를 빼주고 넣는다.(덧셈, 뺄셈보다 우선순위가 높으므로 덧셈,뺄셈 위에 있을 수 있음, 곱하기와 나눗셈은 우선순위가 동등하므로 빼줌)
   • '(' 일때는 그냥 넣어도 되지만, ')'일때는 '('를 만날 때까지 스택에서 연산자들을 빼준다.
   • 맨 마지막에는 스택이 빌때까지 모두 빼준다.
4. 피연산자는 그냥 문자열에 붙여주고, 연산자같은 경우는 pop될때마다 붙여주면 된다.

소스 코드

import sys

t = sys.stdin.readline().rstrip()

op_stack = []
answer = ''
p = ['+', '-', '*', '/', '(', ')']
for s in t:
    if s not in p:
        answer += s
    elif s == '+' or s == '-':
        while op_stack:
            if op_stack[-1] != '(':
                answer += op_stack.pop()
            else:
                break
        op_stack.append(s)
    elif s == '*' or s == '/':
        while op_stack:
            if op_stack[-1] == '*' or op_stack[-1] == '/':
                answer += op_stack.pop()
            else:
                break
        op_stack.append(s)
    elif s == ')':
        while op_stack:
            if op_stack[-1] != '(':
                answer += op_stack.pop()
            else:
                op_stack.pop()
                break
    else:
        op_stack.append(s)

while op_stack:
    answer += op_stack.pop()

print(answer)

문제 설명

문제

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

입력

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

출력

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

풀이 과정

• 전체적으로 소스가 길어지는 문제인거 같음..

1. 현재 지훈이의 위치를 큐에 넣어준다.
2. 현재 불의 위치를 구해 준다.
3. bfs를 활용하여 큐의 맨 앞에서부터 위치를 빼주면서 지훈이가 갈수있는 위치를 큐에 넣어준다.
   • 이 과정을 하다 보면 이동 횟수가 바뀌는 시점이 존재한다.
   • 이동 횟수가 바뀌는 시점에 bfs를 통해 불을 확산시킨다, 이 때, 매 순간 반복문으로 불의 위치를 찾으면 시간 초과가 난다.
   • 따라서.. 한번 확산시키면서, 확산된 불의 위치 또한 큐에 저장해두어야 한다.
4. 배열의 범위를 넘게되는 순간 탈출한 것이므로 그때의 이동 횟수를 출력하고 종료한다.
5. 만약 (4)를 실행하지 않고 큐의 요소가 비게 되면 탈출이 불가능한 것이므로 IMPOSSIBLE을 출력해 준다.

• 소스가 조금 복잡하게 짜여 있음.

import sys
from collections import deque

input = sys.stdin.readline

# 불 확산 함수
Fire = deque()
def spread(matrix, R, C):
    global Fire
    stop_flag = 0
    if Fire:
        stop_flag = Fire[0][2]

    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    while Fire:
        if Fire[0][2] > stop_flag:
            break
        cx, cy, step = Fire.popleft()
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C:
                if matrix[nx][ny] == '.' or matrix[nx][ny] == 'J':
                    matrix[nx][ny] = 'F'
                    Fire.append([nx, ny, step+1])


R, C = map(int, input().rstrip().split())
matrix = [list(input().rstrip()) for _ in range(R)]

for i in range(R):
    for j in range(C):
        if matrix[i][j] == 'F':
            Fire.append([i, j, 0])

J_x, J_y = 0, 0
flag = False
# 지훈이의 위치 찾음
for i in range(R):
    for j in range(C):
        if matrix[i][j] == 'J':
            J_x, J_y = i, j
            flag = True
            break
    if flag:
        break


Jh_queue = deque([[J_x, J_y, 0]])
visited = set()
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
last = 0
visited.add((J_x, J_y))
answer_flag = False
answer = 0
while Jh_queue:
    jx, jy, movement_count = Jh_queue.popleft()
    # 이동 횟수가 늘어나면 불 확산
    if last != movement_count:
        spread(matrix, R, C)
        last = movement_count

    # 현재 방문하려는 위치에 이미 불 퍼진 상태면 스킵
    if matrix[jx][jy] == 'F':
        continue

    for i in range(4):
        nx, ny = jx + dx[i], jy + dy[i]
        if 0 <= nx and nx < R and 0 <= ny and ny < C:
            if matrix[nx][ny] == '.' and (nx, ny) not in visited:
                Jh_queue.append([nx, ny, movement_count+1])
                visited.add((nx, ny))
        elif 0 > nx or nx >= R or 0 > ny or ny >= C:
            answer_flag = True
            answer = movement_count + 1
            break
    if answer_flag:
        break

if answer_flag:
    print(answer)
else:
    print("IMPOSSIBLE")

객체지향 프로그래밍

• 객체
  • 객체의 상태를 나타내는 변수
  • 객체의 행동을 나타내는 함수

객체 생성

• 객체 생성 방법

    const object = {
        attr1: 'a',
        attr2: 'b', // 프로퍼티
        func(a) {
            console.log(`${this.attr1}`); // this는 자기 자신 객체 가리킴
        },
    };

• Factory Function

  • 객체를 생성하는 함수를 따로 만들어 줌.

    function createObject(attr1, attr2) {
      const object = {
          attr1: attr1,
          attr2: attr2, // 프로퍼티
          func(a) {
              console.log(`${this.attr1}`); // this는 자기 자신 객체 가리킴
          },
      };
      return object;
    }
    
    // 위에거 축약
    function createObject(attr1, attr2) {
      const object = {
          attr1,
          attr2, // 프로퍼티
          func(a) {
              console.log(`${this.attr1}`); // this는 자기 자신 객체 가리킴
          },
      };
      return object;
    }
    
    obj1 = createObject('a', 'b') // 객체 편하게 생성 가능

• Constructor Function (생성자 함수)

  • 생성자 함수를 정의 & new 연산자 사용

    function Object(attr1, attr2) { // 함수를 통해서 객체 생성 가능
      this.attr1 = attr1; // this : constructor function으로 생성한 객체
      this.attr2 = attr2;
      this.f = function(a) {
          ..
      };
    }
    
    const obj = new Object('a', 'b') // 반드시 new를 붙여주어야 함.
    

• Class

  • class를 정의하여 객체 생성 가능

    class Object { 
      constructor(attr1, attr2) { // 생성자 안에서는 프로퍼티
          this.attr1 = attr1;
          this.attr2 = attr2;    
      }
    
      f(a) { // 메서드는 생성자 밖에서 선언
          ...
      }
    }
    
    const obj = new Object('a', 'b')

객체지향 프로그래밍

1. 추상화

   • 구체적인 존재를 간략화해서 나타내는 것
   • 클래스명, 프로퍼티명, 메소드명을 잘 정하는 것이 중요
   • 코드에 코멘트나 별도의 문서를 두어 잘 이해할 수 있도록 하는게 중요

2. 캡슐화

   • 객체의 특정 프로퍼티에 직접 접근하는 것을 막음

     class object {
       constructor() {
           this.attr1 = "attr";
       }
     
       set attr1(arg) { // setter, attr1 프로퍼티 값 수정할때 이상한 값 넣었는지 체크
           if (arg === 'a') {
               this._attr1 = arg; // _가 붙은 프로퍼티에 값 넣어줌(숨긴 프로퍼티)
           } else {
               throw new Error('value error');
           }
       }
     
       get attr1() { // getter 메서드
           return this._attr1; // 리턴값은 원하는대로 수정 가능
           // return `attr1 : ${_attr1}`;
       }
     }
     
     obj = new object();
     obj.attr1 = 'a'; // setter 호출
     console.log(obj.attr1) // getter 호출
     

3. 상속

    class object {
        constructor(a) {
            this.attr1 = a;
        }
    }
   
    class obj_child extends object {
        constructor(a, b) {
            super(a); // 상속 시에는 부모 클래스의 생성자를 super를 통해 반드시 호출
            this.attr2 = b;
        }
    }

4. 다형성

   • 많은 형태를 갖는 성질

   • 오버라이딩 : 원래 정의된 부모 클래스의 메소드를 덮어씌움

   • 하나의 변수가 다양한 종류의 객체 접근 가능

     class object {
       constructor(a) {
           this.attr1 = a;
       }
       f(a) {
           console.log("parent:"+a);
       }
     }
     
     class obj_child extends object {
       constructor(a) {
           super(a);
       }
       f(a) {
           console.log("child:"+a);
       }
     }
     
     let p_arr = [new object(10), new obj_child(10)];
     p_arr.forEach((element) => {
       element.f(10); // object, obj_child 두개 다 접근 가능
     });
     

클로저(Closure)

function createObject(a) {
    let outera = a; // outera는 외부에서 사용 불가능
    function f() { // f는 외부에서 호출 불가능

    }
    const obj = { // 객체 내부에서는 outera, f 사용하더라도 보존됨.
        get a() {
            return outera;
        },
        set a(newa) {
            outera = newa;
        }
    }
}

• 클로저 : 어떤 함수와 그 함수가 참조할 수 있는 값들로 이루어진 환경을 하나로 묶은 것
• 즉, outera는 외부에서는 obj.a를 통해서만 읽을 수 있다.

JavaScript

부모 클래스의 메소드 사용

• super.메소드()

class obj {
    constructor(a) {
        this.a = a
    }
    f(a) {
        console.log("parent->f")
    }
}

class obj_child extends obj {
    constructor(a) {
        super(a);    
    }
    f(a) {
        super.f(a)
    }
}

현재 변수의 클래스 확인

• instanceof 연산자 사용
  • child가 parent를 상속한 경우
  • child instanceof parent ⇒ True
  • child instanceof child ⇒ True
  • parent instanceof child ⇒ False
• instanceof를 활용한 분기문보다는 다형성을 활용하여 메소드 구성하는게 더 나음

변수 instanceof 클래스 // ==> 변수가 클래스인 경우에만 True

Static 프로퍼티 / Static 메서드

• 클래스에 직접적으로 달려있는 프로퍼티와 메서드

class Calculator {
    static i = 0;
    static sum(a, b) {
        return a + b;
    }
}

Calculator.i; // 0
Calculator.sum(3, 5); // 8

/* 프로퍼티 추가&변경 / 메서드 추가 가능 */
Calculator.i = 10;
Calculator.minus = function(a, b) {
    return a - b;
}