제어의 역전(Inversion of Control) 이라는 말이 조금 어렵게 느껴진다.

라이브러리 vs 프레임워크 차이에 대해서 공부할때도 잠깐 공부했었지만, 이 참에 제대로 다시 정리 해보려고 한다.

 

라이브러리 vs 프레임워크

둘의 차이는?

프레임워크는 라이브러리를 포함한다. 프레임워크 위에 개발자가 작성한 애플리케이션 코드가 올라가고, 이 코드에서 라이브러리를 호출한다.

제어의 흐름이 어디에 있는가로 설명가능하다.

 

프레임워크는 제어의 역전 개념이 적용된다. 제어흐름을 프레임워크에 넘겨 틀안에서 수동적으로 동작.

 

라이브러리는 이러한 제어의 흐름이 개발자에게 있다. 개발자에게 전적으로 제어 흐름이 있으며 능동적으로 라이브러리를 호출하여 사용한다.

https://hudi.blog/inversion-of-control/

 

프론트엔드에서 IOC 적용예시

늘 그렇듯, 용어가 어려울 뿐이지 우리가 사용해봤던 여러 메서드나 기타 코드에서 제어의 역전 개념이 쓰인적이 있을거라고 생각했다.

 

IOC는 일반적으로 프레임워크에 의해 적용되는 말이지만, 개발자가 직접 해당 원리를 적용하여 코드를 작성할 수도 있다.

코드의 유연성과 재사용성이 증가하며 애플리케이션의 확장과 유지보수가 용이해진다. 

--> 코드를 작성하고 그것을 실행하는것은 호출한 모듈이 실행하는 셈.

 

 

Render props 패턴

제어의 역전의 한 예시이다.

const Counter = (props) => {
  const [count, setCount] = useState(0);

  return (
    <div onClick={() => setCount((prev) => prev + 1)}>
      props.children
    </div>
  );
};

Counter 컴포넌트의 count를 children에 어떻게 전달할 수 있나.

count가 업데이트 될때마다 children 또한 업데이트 해보자.

const Counter = (props) => {
  const [count, setCount] = useState(0);

  return (
    <div onClick={() => setCount((prev) => prev + 1)}>
      {props.children(count)}
    </div>
  );
};

function App() {
  const { author } = {
    author: "lee",
  };

  return (
    <div className='App'>
      <Counter>
        {(count) => {
          return (
            <>
              <div>작성자: {author}</div>
              <div>{count}</div>
            </>
          );
        }}
      </Counter>
    </div>
  );
}

-> Counter 컴포넌트는 count 상태를 관리하고, 해당 상태를 자식 컴포넌트로 전달하는 기능을 함.

자식 컴포넌트는 props.children으로 전달받은 함수를 호출하면서 count 값을 인자로 넘겨준다.

 

 

DI(의존성 주입)

리액트에서 컴포넌트를 다룰때 많이 사용되는 컴포넌트 주입이 있다.

부모 컴포넌트가 자식 컴포넌트의 동작을 제어하거나 데이터를 주입하면서, 자식 컴포넌트는 이에 의존하여 동작하는 구조를 만들 수 있다. 

 

 

https://brunch.co.kr/@finda/556

문제링크

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

 

9095번: 1, 2, 3 더하기

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

www.acmicpc.net

문제설명

 

문제

정수 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은 양수이며 11보다 작다.

출력

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

예제 입력 1 

3
4
7
10

예제 출력 1 

7
44
274
문제풀이

 

코드
T = int(input())

tmp = []

for _ in range(T):
    tmp.append(int(input()))

cache = [0,1,2,4]

for i in range(4,max(tmp)+1): #4부터 N까지 저장된 최댓값까지
    cache.append(cache[i-1]+cache[i-2]+cache[i-3])

for n in tmp:
    print(cache[n])
문제링크

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

 

1389번: 케빈 베이컨의 6단계 법칙

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻

www.acmicpc.net

문제설명

문제

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

...

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다.

출력

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

 

예제 입력 

5 5
1 3
1 4
4 5
4 3
3 2

예제 출력 

3

 

문제풀이

핵심

- 친구 관계는 서로 맺는 것이므로 양방향 즉, 무향 그래프이다.

- 단계를 나타내므로 가중치는 1이라 생각하자

 

1. 인접행렬 생성 및 초기화(자기자신이면 0으로, 나머지는 무한대로 초기화)

2. 입력값으로 주어진 친구관계 정보를 인접행렬에 저장.

3. 플로이드-워셜 수행하며 모든 중간경로 탐색.

4. 2차원 배열의 각 행의 총합(케빈 베이컨 수) 저장

5. 케빈베이컨 수를 비교하여 값이 최소인 인덱스를 추출 (여러개라면, 더 작은 번호 출력)

 

코드
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
matrix = [[float('inf') for _ in range(N+1)]  for _ in range(N+1)]
kev = []
answer = []

# A와 B가 같은 비용은 없다 했으므로 자기 자신으로 가는 비용은 0
for a in range(N+1):
    for b in range(N+1):
        if a == b:
            matrix[a][b] = 0
        if a == 0 or b == 0:
            matrix[a][b] = 0

# 입력값 받아서 해당 행렬 원소 1로 만들기.
for _ in range(M):
    n1, n2 = map(int, input().split())
    matrix[n1][n2] = 1
    matrix[n2][n1] = 1

def floydWarshall():
    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(1, N+1):
                matrix[i][j] = min(matrix[i][j], matrix[i][k]+matrix[k][j])
                        

def main():
    #플로이드 워셜 수행
    floydWarshall()

    # 그래프의 행에 속한 원소들의 합을 kev리스트에 삽입.
    for row in matrix:
        kev.append(sum(row))    

    # 최솟값 구할 것이므로 0번째 인덱스는 다시 무한대 수로 수정.
    kev[0] = float('inf')
    minValue = min(kev)

    # 케빈베이컨 수가 가장 적은 사람을 고르는 로직
    for index, value in enumerate(kev):
        if value == minValue:
            answer.append(index)

    print(min(answer))


if __name__ == "__main__":
    main()
문제링크

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

 

1325번: 효율적인 해킹

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한

www.acmicpc.net

문제설명

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

예제 입력 1 

5 4
3 1
3 2
4 3
5 3

예제 출력 1 

1 2​
문제풀이

5초로 시간제한이 긴 문제였지만, 파이썬으로 구현하니 15초가 걸렸지만 성공이다. (처음엔 시간초과인줄 안..)

 

BFS로 풀었다.

일반적인 BFS 방식에서 조금 더 변화를 주면 되는 문제였다.

 

가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터는?

=> 가장 신뢰높은 컴퓨터라는 얘기가 된다.

 

즉, 각 컴퓨터에 신뢰도 점수를 부여해 신뢰도가 최댓값인 노드를 찾으면 되는 일이다.

 

1. 입력값 받아 그래프를 나타내는 이차원배열 생성

2. 모든 컴퓨터를 기점으로 BFS를 진행하며(예제입력값으로 하면 컴퓨터 5대이므로 총 5번)  

   + 탐색을 수행하면서 신뢰도 증가 

3. 모든 BFS 마친후, 신뢰도 리스트 탐색하며 최댓값과 일치하는 인덱스 오름차순 출력

 

코드
from collections import deque
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
arr = [[] for _ in range(N+1)]
relyList = [0] * (N+1)  # 신뢰도 점수 쌓는 리스트
                        # 전역변수로 둔다. 모든 노드 BFS 각각 하면서 정보 업데이트 할것이므로
answer = []

for _ in range(M):
    n1, n2 = map(int, input().split())
    arr[n1].append(n2)

def BFS(node, graph):
    visited = [False] * (N+1)
    queue = deque()
    queue.append(node)
    visited[node] = True

    while queue:
        cur = queue.popleft()
        for v in graph[cur]:
            if not visited[v]:
                queue.append(v)
                visited[v] = True
                relyList[v] += 1  #특정 노드가 참조한 노드는 신뢰한다는 의미이므로 신뢰도 +1
for i in range(1, N+1):
    BFS(i, arr)

maxValue = max(relyList)

# 신뢰도 리스트 객체 반복하며 max값과 일치하는 인덱스 모두 정답 배열에 삽입
for index, value in enumerate(relyList):
    if value == maxValue:
        answer.append(index)

answer.sort()
print(*answer)
문제링크

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

 

2343번: 기타 레슨

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경

www.acmicpc.net

문제설명

 

문제

강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.

강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.

강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.

출력

첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.

예제 입력 1 

9 3
1 2 3 4 5 6 7 8 9

예제 출력 1 

17

 

문제풀이

 

코드
# 이분탐색
# "뭔가 기준점이 있어야하고 그 기준점은 조건에 따라 달라질수가있다." => 이분탐색이겠구나

# 나머지는 일반적인 이분탐색 풀이와 같습니다. 
# 하지만 약간 난이도 있는 이분탐색 문제의 특징처럼 단순히 start와 end 만으로 mid를 찾는 방식이 아니라 주어진 조건을 고려하면서 mid값을 찾아나갔습니다.
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = list(map(int, input().split()))

# ★일반적인 이분탐색과 달리, 정렬 사용하면 안된다. => 문제조건: 순서 보장해야하므로.

start, end = max(arr), sum(arr)

while start <= end:
    mid = (start + end) // 2
    cnt, sum = 0, 0

    # 블루레이에 강의 넣기
    for i in range(N):
        # 지정한 bluRay크기(mid값).벗어난다면 1개 완성.
        if sum + arr[i] > mid: 
            cnt += 1 # bluray 1개 만들어지고 해당 인덱스 원소는 sum에서 제외
            sum = 0 
        sum += arr[i] 
        
        # sum이 0이 아니면 마지막 블루레이 필요
    if sum != 0:
        cnt += 1

    if cnt > M:  # mid값 크기의 blu로 모든 레슨 저장 불가능.
        start = mid + 1    
    else:        # mid값 크기 bluRay로 모든 레슨 저장 가능.
        end = mid - 1


print(start)
문제링크

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

 

1541번: 잃어버린 괄호

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다

www.acmicpc.net

문제설명

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입력

55-50+40

예제 출력

-35

 

문제풀이
 

 

 

코드
arr = input().split("-")
sum = 0
# input값이 100-40+50+74-30+29-45+43+11 이라면
# arr = [100, 40+50+74, 30+29, 45+43+11]

# 0번째 인덱스에 존재하는 문자열도 +가 들어있을 수 있는 문자열임.
# 따라서 +기점으로 분리하여 각 숫자의 총합 구한다.
for item in arr[0].split("+"):
    sum += int(item)

# arr의 1번째 인덱스부터 마지막 원소까지 반복.
# 각 인덱스의 문자열을 +기준으로 split시킨 배열 순회.
# 그리고 sum에서 그 값들을 전부 뺀다. => 최솟값.
for str in arr[1:]:
    for item in str.split("+"):
        sum -= int(item)

print(sum)
문제링크

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

 

18352번: 특정 거리의 도시 찾기

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개

www.acmicpc.net

문제설명

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

 

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

입력

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.

출력

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

예제 입력 

4 4 2 1
1 2
1 3
2 3
2 4

예제 출력

4

 

코드
from collections import deque
import sys

input = sys.stdin.readline
N, M, K, X = map(int, input().split())

arr = [[] for _ in range(N+1)]
visited = [-1] * (N+1)
answer = []

for _ in range(M):
    s, e = map(int, input().split())
    arr[s].append(e)

def BFS(node, graph, visited):
    #탐색시작
    queue = deque()
    queue.append(node)
    visited[node] += 1  # visited리스트에 거리정보 저장.(+1씩 하며)
    
    # queue에 데이터가 있는동안
    while queue:
      cur = queue.popleft()
      for v in graph[cur]:
          if visited[v] == -1:
              visited[v] = visited[cur] + 1
              queue.append(v)
    
    return visited

# BFS 실행
visited = BFS(X, arr, visited)

# visited배열 순회하며 최단거리가 K인 도시 찾기
for i in range(1, N+1):
    if visited[i] == K:
        answer.append(i)

answer.sort()

# 최단거리가 K인 도시가 하나도 없다면 -1출력
if not answer:
    print(-1)
else:
    for item in answer:
        print(item, end='\n')
문제링크

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

 

2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍

www.acmicpc.net

문제설명

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 

7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 

4

 

문제풀이

BFS로 쉽게 풀 수 있다.

 

구하고자 하는 건 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수이므로,

1번에서 BFS 시작하여 연결된 모든 노드 수를 구하면 됨.

(그리고 1번은 제외해야하므로 1을 빼주면 끝.)

 

코드
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
E = int(input())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)

for _ in range(E):
    s, e = map(int, input().split())
    graph[s].append(e)
    graph[e].append(s)

#연결된 모든 노드 수 구하면 됨.

def BFS(graph, start):
    queue = deque()
    queue.append(start)
    cnt = 0

    while queue:
        cur = queue.popleft()

        # 방문하지 않은 노드라면
        if not visited[cur]:
            # 방문!
            visited[cur] = True
            cnt += 1
            for node in graph[cur]:
                queue.append(node)

    answer = cnt - 1
    print(answer)

BFS(graph, 1)
문제링크

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

 

1931번: 회의실 배정

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

www.acmicpc.net

문제설명

 

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1 복사

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1 복사

4
문제풀이

처음에 시도했던 방법은 시작시간을 우선적으로 정렬해보려고 했다.

 

하지만 핵심은,

시작시간이 아닌 종료시간을 기준으로 우선적으로 정렬하고 종료시간이 같은 강의가 여러개 있다면 그 후 시작시간을 기준으로 정렬하는 것이 핵심. 

 

그 후 배열을 반복 순회하면서

이전 강의시간의 종료시간보다 이후에 시작하는 강의가 있으면 해당 강의를 포함시킴. (정렬된 상태이므로)

그리고 prev값 갱신

 

코드
import sys

input = sys.stdin.readline
N = int(input())
arr = [[0, 0] for _ in range(N)]
answer = 0

for i in range(N):
    arr[i][0], arr[i][1] = map(int, input().split())

arr.sort(key=lambda x: (x[1], x[0]))

prev = arr[0][1]
answer = 1
for i in range(1, N):
    # 이전 강의시간의 종료시간보다 나중에 시작한다면
    if arr[i][0] >= prev:
        prev = arr[i][1]
        answer += 1
print(answer)

목차
1. 실행 컨텍스트
2. 렉시컬 환경
3. 실행 컨텍스트 생성과정

 

 

1. 실행 컨텍스트

1. 개념

현재 실행중인 코드에 대한 세부정보(제어 흐름의 위치, 변수함수, this, arguments 등)를 저장해놓은 내부 데이터 구조.

 

2. 종류
(1) Global Execution Context
생성시점: 스크립트가 처음 실행될때
(2) Function Execution Context
생성시점: 함수가 호출될때

이렇게 생성된 이것들은 실행 컨텍스트 스택(==콜스택)에 저장되어 관리.

여기서 자료구조가 '스택'이라는 거에 주목하면 된다.

스크립트가 처음 실행될때 생성되는 global execution context는 스택의 가장 아랫부분에 위치하고
이 말은 곧, 프로그램이 종료되고 나서야 메모리에서 제거된다는 뜻.
cf. 재귀함수: 종료조건을 잘못 설정하여 실행 컨텍스트가 계속해서 콜스택에 push되어 쌓이게 되면 스택 오버플로우 발생할 수 있다. 조심하자. (재귀방식보다는 반복문 방식이 메모리 공간을 절약하는 방법이다.)

 

3. 구조

(1) 스크립트 전체

(2) 코드블록 {...}

(3) 호출된 함수

이 세개는 렉시컬 환경이라는 것을 가지고 있다.

 

2. 렉시컬 환경 (Lexical Environment)

렉시컬 환경은 식별자와 식별자에 바인딩된 값, 그리고 상위 스코프에 대한 참조를 기록하는 자료구조로 실행 컨텍스트를 구성하는 컴포넌트이다.

cf. 실행 컨텍스트 스택(콜스택)이 코드의 실행 순서를 관리한다면, 렉시컬 환경은 스코프와 식별자를 관리한다.

 

1. 환경 레코드 - 현재 실행중인 코드환경의 this값 및 호출된 함수에서 선언된 변수, 함수 저장

2. 외부 렉시컬 환경 - 부모환경의 렉시컬 환경 참조값을 가지고 있다. (외부변수에 접근 가능)

이렇게 두 부분으로 구성되어있다.

코드로 자세히 살펴보면,

<script>
    // (A)
    let name1 = 'Son'; // (B)
    var name2 = 'ny';

    function solution() {
        let answer = 'Nice one';
        console.log(`${answer} ${name1}${name2}`);  // (C)
    }

    solution(); // (D)
</script>

위 코드에서는 총 2개의 렉시컬 환경이 존재한다.

- Global 렉시컬 환경

- 함수 solution의 렉시컬 환경

여기서 2개는 정해진 개수가 아니라, 선언된 함수의 수에 따라 프로그램은 더 많은 렉시컬 환경을 가질 수 있다.

 

실행 순서

1. (A) 에서 global 렉시컬 환경이 만들어진다.

2. (D)에서 solution 함수가 실행되고 solution 함수의 렉시컬 환경이 만들어진다.

3. JS 엔진이 (C) 부분에서 문자열 템플릿 리터럴 내에서 사용되는 변수들을 찾기위해 solution의 렉시컬 환경의 환경 레코드를 탐색한다.

4. answer만 존재하고 name1, name2는 찾을 수 없다.

5. 외부 렉시컬 환경의 참조를 통해 global영역의 환경 레코드에 접근한다. => name1, name2 찾음.

 

★ 외부 렉시컬 환경은 함수가 실행되는 시점이 아닌 선언된 시점의 외부 환경을 가리킨다는 사실이다.

let name = 'Son';

function f1() {
    let name = 'Kim';
    f2();
}

function f2() {
    console.log(name);
}

f1();

f1()을 실행하고 나면 출력되는 값은 'Son'이다.

f1함수내에서 f2를 호출했기 때문에 'Kim'을 출력한다고 생각할 수 있겠으나,
함수가 선언된 시점의 외부 환경을 참조하므로 f2의 외부렉시컬 환경은 Global 영역이 되겠다.

그래서 스크립트 전역에 선언된 name변수를 참조하여 'Son'을 출력하는 것이다.

 

3. 실행 컨텍스트 생성과정

실행 컨텍스트 내부구조

1. 생성단계

  1. Lexical Environment가 생성된다.
    • 함수
      함수 선언문: 메모리에 바로 올라간다.
      함수 표현식: 함수가 할당된 변수의 선언문만 호이스팅 된다.
    • 변수
      var: 선언문이 호이스팅 되고 undefined로 초기화됨.
      let,const: 선언문이 호이스팅 되고 uninitialized 상태가된다.
  2. This 바인딩.
    • Global: 브라우저 환경일 경우 window가 전역오브젝트로 this에 window가 할당된다.
    • Function: argrument 객체가 초기화 된다. (window 할당은 없음)

3. 모든 변수가 생성 단계에서 Lexical 환경에 초기화 되기때문에 JS엔진은 변수들의 존재를 모두 미리 인지하게 되고, 이게 호이스팅이 발생하는 이유다.

 

2. 실행단계

생성 단계에서 결정된 Lexical 환경을 가지고 있는 상태로, 코드를 한 줄씩 실행해 나간다.

그 과정에서 변수에 값을 할당하면 렉시컬 환경의 해당 변수 값이 변경된다.

=> 실행 컨텍스트는 이렇게 두 단계에 걸쳐 생성되어 코드 흐름에 따라 콜스택에 관리 된다.

 

 

cf. 함수 코드 평가 순서

함수가 호출되면 전역 공간에 있던 코드의 제어권이 함수의 내부로 이동하면서 함수 코드를 평가하게 되는데,

다음과 같은 순서로 함수코드를 평가한다.

 

① 함수 실행 컨텍스트 생성

② 함수 Lexical Environment 생성

2-1) 함수 environment 레코드 생성

2-2) this 바인딩

2-3) 외부 렉시컬 environment에 대한 참조 결정

 

 

 

 

 

 

참고: https://kwangsunny.tistory.com/37

+ Recent posts