(Home.md

(algorithm.md

(디자인패턴.md

(디자인패턴.md

(BOJ1005.md

(BOJ1016.md

(BOJ10797.md

(BOJ10798.md

(BOJ10986.md

(BOJ10999.md

(BOJ11585.md

(BOJ11785.md

(BOJ12844.md

(BOJ13258.md

(BOJ1389.md

(BOJ1459.md

(BOJ1655.md

(BOJ17088.md

(BOJ17140.md

(BOJ17281.md

(BOJ1948.md

(BOJ1958.md

(BOJ20061.md

(BOJ20149.md

(BOJ23286.md

(BOJ2445.md

(BOJ25315.md

(BOJ2594.md

(BOJ2641.md

(BOJ3665.md

(BOJ4354.md

(BOJ5525.md

(BOJ6322.md

(BOJ6439.md

(BOJ9019.md

(백준 1045 도로.md

(백준 1075 나누기.md

(백준 12834 주간 미팅.md

(백준 1417 국회의원 선거.md

(백준 14428 수열과 쿼리 16.md

(백준 14725 개미굴.md

(백준 16434 드래곤 앤 던전.md

(백준 2104 부분배열 고르기.md

(백준 2224 명제 증명.md

(백준 22860 폴더 정리 (small).md

(백준 2476 주사위 게임.md

(백준 2613 숫자구슬.md

(백준 2693 N번째 큰 수.md

(백준 2752 세수정렬.md

(백준 4179 불!.md

(백준 5547 일루미네이션.md

(백준 1045 도로.md

(백준 1075 나누기.md

(백준 12834 주간 미팅.md

(백준 1417 국회의원 선거.md

(백준 14428 수열과 쿼리 16.md

(백준 14725 개미굴.md

(백준 16434 드래곤 앤 던전.md

(백준 2104 부분배열 고르기.md

(백준 2224 명제 증명.md

(백준 22860 폴더 정리 (small).md

(백준 2476 주사위 게임.md

(백준 2613 숫자구슬.md

(백준 2693 N번째 큰 수.md

(백준 2752 세수정렬.md

(백준 4179 불!.md

(백준 5547 일루미네이션.md

algorithm

(디자인패턴 - 옵저버 패턴.md

(디자인패턴 - 전략 패턴.md

디자인패턴

(디자인패턴 - 옵저버 패턴.md

(디자인패턴 - 전략 패턴.md

디자인패턴

content


# Home

* 텍스트를 기반으로하여 빠르게 글 작성 및 공유하는 페이지
* 더 자세한 내용 또는 이미지를 추가하여 작성할때는 tistory 블로그에 작성
  * [민트로피의 민트초코](https://mintropy.tistory.com/)

# Index

* [(algorithm](%28algorithm.md)
* [(디자인패턴](%28%EB%94%94%EC%9E%90%EC%9D%B8%ED%8C%A8%ED%84%B4.md)


(Home


# (algorithm

* [BAEKJOON](https://www.acmicpc.net/)
  * [백준 프로필](https://www.acmicpc.net/user/jun2korea)
  * [solved.ac 프로필](https://solved.ac/profile/jun2korea)

# 규칙

* 제목은 `BOJ0000`형태(문제출처+번호)
  * 작성의 편리함도 있지만, 주소를 더욱편리하게 지정하기 위함
* 언어는 해당 제출 언어 설정 기준으로 작성
  * Python3의 경우, Python으로 표기
  * 그 외에는 Go, Node.js, TypeScript 등으로 표시


(algorithm

(디자인패턴

(디자인패턴


# (BOJ1005 ACM Craft

* tags : [(algorithm](../%28algorithm.md) - *(topological sort*
* 문제 링크 : https://www.acmicpc.net/problem/1005
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/1000/1000/1005.py)

## 문제 설명

* 위상 정렬을 활용하여 특정 순서의 건물이 지어지는 시간을 구하는 문제
* 이 문제에서는 각 건물을 짓는데 걸리는 시간을 누적해 가야한다.
  * 그리고 이 시간을 위상 정렬에 맞게 처리해야 하므로 정렬 순서와 각 건물을 짓는데 걸리는 시간 등을 잘 확인하고 관리해야 한다.

## 문제 풀이

````python
N, K = MIIS()
buildings = [0] + list(MIIS())
before_count = [0] * (N + 1)
next_building = [[] for _ in range(N + 1)]
for _ in range(K):
	x, y = MIIS()
	next_building[x].append(y)
	before_count[y] += 1
````

* 우선 주어진 건물순서를 받아서 before_count에는 각 건물보다 먼저 지어져야 하는 건물의 수를, next_building에는 특정 건물 다음에 지을 수 있는 건물 번호를 저장한다.

````python
build_times = [0] * (N + 1)
queue = deque([])
W = II()
for i in range(1, N + 1):
	if not before_count[i]:
		if i == W:
			print(buildings[i])
			break
		build_times[i] = buildings[i]
		queue.append((i, buildings[i]))
else:
	while queue:
		x, t = queue.popleft()
		for y in next_building[x]:
			if build_times[y] < t + buildings[y]:
				build_times[y] = t + buildings[y]
			before_count[y] -= 1
			if not before_count[y]:
				queue.append((y, build_times[y]))
				if y == W:
					print(build_times[W])
					break
		else:
			continue
		break
````

* W건물을 짓는데 걸리는 시간을 구하기 위해 BFS를 응용한다.
* 우선, 위에서 구한 값을 기반으로 선행 건물이 없는 건물을 queue에 넣는다.
  * 만약 W 건물이 가장 먼저 지어질 수 있다면 해당 건물을 짓는데 걸리는 시간을 출력하고 종료한다.
* 다음 queue에 들어있는 건물을 확인하여 위상정렬을 수행한다. 
  * 각 건물을 확인하며, 다음 순서에 지을 수 있는 건물도 확인한다.
  * 모든 건물을 확인할 때마다 시간을 갱신한다. 이 때 시간은 최대한 늦는 시간으로 갱신한다.
  * 그리고 건물이 지어질 수 있다면 queue에 추가하여 탐색한다.


(BOJ1005


# (BOJ1016 제곱 ㄴㄴ 수

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/1016
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/1000/1000/1016.py)

## 문제 설명

* 가장 간단하게 설명하면, 특정 구간에서 특정 조건을 만족하는 수의 갯수를 구하는 문제이다.
* 조금 더 상세하게 살펴보면, 구간은 최대 100만 개의 숫자를 포함하고, 정답에서 제외해야 하는 숫자는 어떤 수의 제곱의 배수인 경우이다.
  * 만약 모든 숫자를 어떤 수의 제곱의 배수인지 확인한다고 하면 하나의 숫자를 확인하기 위해 그 수의 제곱근까지 모든 수를 확인해야 한다. 이는 O(logN)의 시간이 걸린다.
* 대신 단계를 조금 줄여보는 방향으로 생각해볼 수 있다.
  * 입력으로 주어지는 max값의 제곱근까지의 수를 탐색하고, 해당 숫자들의 제곱의 배수를 찾으면 된다.
  * 조금 더 단계를 줄인다면, max값의 제곱근까지의 수 중 소수만 탐색하여 해결할 수 있다.

## 문제 풀이

### 완전 탐색

````python
min_val, max_val = map(int, input().split())
check = [False] * (max_val - min_val + 1)
ans = max_val - min_val + 1
for n in range(2, int(max_val**0.5) + 1):
	n_square = n * n
	q = min_val // n_square + 1 if min_val % n_square else min_val // n_square
	q_max = max_val // n_square + 1
	for k in range(q, q_max):
		if not check[n_square * k - min_val]:
			check[n_square * k - min_val] = True
			ans -= 1
print(ans)
````

* max의 제곱근까지의 모든 숫자를 탐색하는 경우
* 정답을 구하기 위하여 min부터 max까지 구간 확인을 위한 리스트를 생성한다.
  * 이 때, 입력되는 수는 1조까지 나올 수 있으므로 전체 숫자를 확인하는 리스트 대신, min부트 max까지 값만 확인할 수 있는 리스트로 선언
  * 또한 `count()`메서드 등을 활용하여 답을 구할 수 있지만, ans값에 답을 저장하며 확인함
* 2부터 max의 제곱근까지 모든 수를 탐색하는 for문을 구성했고,
  * 해당 수의 제곱과 그 배수를 구하여 에라토스테네스의 체를 적용했다.

### 소수만 탐색

````python
min_val, max_val = map(int, input().split())
check = [True] * (max_val - min_val + 1)

if max_val <= 3:
	print(max_val - min_val)
	exit()
prime_square = [4]
max_sqrt = int(max_val**0.5)
is_prime = [True] * (max_sqrt // 2 + 1)
for i in range(3, max_sqrt + 1, 2):
	if is_prime[i // 2]:
		i_square = i * i
		prime_square.append(i_square)
		is_prime[i_square // 2 :: i] = [False] * (
			(max_sqrt - i_square + 1) // (2 * i) + 1
		)
for num in prime_square:
	st = num - min_val % num if min_val % num else 0
	check[st::num] = [False] * len(check[st::num])
print(check.count(True))
````

* max값이 4보다 작은 경우 더이상 탐색할 필요가 없기 때문에 조건문을 처리했다
* 아니라면 2이상 max의 제곱근 이하 모든 소수의 제곱을 탐색한다.
  * 여기서 탐색을 더 줄이기 위해 2 * 2 = 4를 먼저 추가하고,
  * 3부터 모든 홀수 중 소수를 탐색한다.
* 소수의 제곱을 구했을 때 min부터 max까지의 값을 다시 탐색하여 정답을 구한다.


(BOJ1016


# (BOJ10797 10부제

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/10797
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/10000/10700/10797.py)
  * [Go](https://github.com/mintropy/PS/blob/master/BAEKJOON/go/10000/10700/10797.go)
  * [Node.js](https://github.com/mintropy/PS/blob/master/BAEKJOON/Node/10000/10700/10797.js)

## 문제 설명

* 주어진 숫자를 이후 입력되는 숫자와 같은 값이 있는지 확인하는 문제

## 문제 풀이

### Python

````python
N = int(input())
seq = list(map(int, input().split()))
print(seq.count(N))
````

* list.count() 활용

### Go

````Go
for i := 0; i < 5; i++ {
	k := nextInt()
	if k == N {
		ans++
	}
}
````

* for문과 조건문을 활용하여 확인

### Node.js

````js
for (var k in seq) {
  if (seq[k] === N) {
    ans++
  }
}
````

* Go와 같이 for문과 조건문을 활용하여 확인


(BOJ10797


# (BOJ10798 세로읽기

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/10798
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/10000/10700/10798.py)
  * [Go](https://github.com/mintropy/PS/blob/master/BAEKJOON/go/10000/10700/10798.go)
  * [Node.js](https://github.com/mintropy/PS/blob/master/BAEKJOON/Node/10000/10700/10798.js)

## 문제 설명

* 2중 for문으로 탐색하며, 각 줄의 길이가 달라 조건문이 추가되는 문제
* 출력은 한줄로 이어서 하면 되므로 크게 신경쓸 부분은 없다

## 문제 풀이

### Python

````python
seq = [input().strip() for _ in range(5)]
ans = ""
for j in range(15):
	for i in range(5):
		if len(seq[i]) < j + 1:
			continue
		ans += seq[i][j]
print(ans)
````

* 다른 언어 풀이도 유사하게 풀었다.
* 5줄을 먼저 입력받고, 출력 문자열을 선언한 다음
  * 왼쪽부터 세로로 순회하며 문자열 길이를 초과하지 않을 때 출력 문자열에 추가한다.

### Go

````go
var seq []string
for i := 0; i < 5; i++ {
	sc.Scan()
	tmp := sc.Text()
	seq = append(seq, tmp)
}
for j := 0; j < 15; j++ {
	for i := 0; i < 5; i++ {
		if j < len(seq[i]) {
			wr.WriteByte(seq[i][j])
		}
	}
}
````

* Go 문자열은 immutable이므로 바로바로 출력하는 방식 사용

### Node.js

````js
let seq = []
for (let i = 0; i < 5; i++) {
  seq.push(input[i])
}
let ans = ""
for (let j = 0; j < 15; j++) {
  for (let i = 0; i < 5; i++) {
    if (seq[i].length > j) {
      ans += seq[i][j]
    }
  }
}
````

* Python과 유사하게 풀이


(BOJ10798


# (BOJ10986 나머지 합

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/10986
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/10000/10900/10986.py)

## 문제 설명

* 모든 구간을 탐색할 수 없다.
  * 최대 $10^6$개의 값이 나오므로, $O(N^2)$으로 탐색하면 시간 초과가 날 것이다.
* 대신 누적합으로 먼저 접근해본다.
  * 누적합 기준 M으로 나눈 값을 생각하는 것이므로,  누적합을 구하면 조금 빠르게 접근할 수 있을 것이다.
  * 누적합으로 그대로 접근하면 역시 전체 탐색이 필요할것이므로, 시간초과가 날 것이다.
* 누적합을 그대로 사용하지 않고 M으로 나눈 나머지를 저장하면 어떨까?
  * 이 경우라면 전체 탐색을 고민할 수 있지만, 
  * 나눈 나머지가 같은 값을 생각하면 조금 따르게 접근할 수 있다.

## 문제 풀이

````python
N, M = MIIS()
seq = [0] + list(MIIS())
mod_counts = [0] * M
mod_counts[0] += 1
for i in range(N):
	seq[i + 1] += seq[i]
	seq[i + 1] %= M
	mod_counts[seq[i + 1]] += 1
ans = sum([comb(x, 2) for x in mod_counts])
print(ans)
````

* 전체 코드는 길지 않다.
  * 누적합을 구하는 것과 동시에 나머지를 같이 구하여 저장했다.
  * 그리고 각 구간을 구하여야 하므로 가장 앞에 0값을 추가로 두었다.
* 누적합의 나머지가 같은 위치를 기준으로 잘라서 생각하면 결국 다시 나머지가 0이 될 것이다.


(BOJ10986


# (BOJ10999 구간 합 구하기 2

* tags : [(algorithm](../%28algorithm.md) - *(segment tree* - *(lazy propagation*
* 문제 링크 : https://www.acmicpc.net/problem/10999
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/10000/10900/10999.py)

## 문제 설명

* 처음 풀어본 lazy propagation 세그먼트 트리 문제
  * lazy값을 잘 활용하는 것이 이 문제 해결의 핵심인 것 같다.

## 문제 풀이

````python
class SegmentTree:
    def __init__(self, N: int, seq: list[int]) -> None:
        self.N = N
        self.seq = [0] + seq
        self.tree = [0] * (1 << (ceil(log2(N)) + 1))
        self.lazy = [0] * (1 << (ceil(log2(N)) + 1))
        self.init_tree(1, 1, N)

    def mid(self, start: int, end: int) -> int:
        return (start + end) // 2

    def init_tree(self, node: int, start: int, end: int) -> None:
        if start >= end:
            self.tree[node] = self.seq[start]
            return
        mid = self.mid(start, end)
        self.init_tree(node * 2, start, mid)
        self.init_tree(node * 2 + 1, mid + 1, end)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def update_lazy(self, node: int, start: int, end: int) -> None:
        if self.lazy[node]:
            self.tree[node] += (end - start + 1) * self.lazy[node]
            if start != end:
                self.lazy[node * 2] += self.lazy[node]
                self.lazy[node * 2 + 1] += self.lazy[node]
            self.lazy[node] = 0

    def update_range(
        self, node: int, start: int, end: int, left: int, right: int, diff: int
    ) -> None:
        self.update_lazy(node, start, end)
        if right < start or end < left:
            return
        if left <= start and end <= right:
            self.tree[node] += (end - start + 1) * diff
            if start != end:
                self.lazy[node * 2] += diff
                self.lazy[node * 2 + 1] += diff
            return
        mid = self.mid(start, end)
        self.update_range(node * 2, start, mid, left, right, diff)
        self.update_range(node * 2 + 1, mid + 1, end, left, right, diff)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def query(self, node: int, start: int, end: int, left: int, right: int) -> int:
        self.update_lazy(node, start, end)
        if right < start or end < left:
            return 0
        if left <= start and end <= right:
            return self.tree[node]
        mid = self.mid(start, end)
        left_sum = self.query(node * 2, start, mid, left, right)
        right_sum = self.query(node * 2 + 1, mid + 1, end, left, right)
        return left_sum + right_sum
````

* 우선 문제 풀이 코드부터 보면 다음과 같다.
* 처음 세그먼트 트리를 만들기 위한 `init_tree()`메서드를 선언 및 실행했고,
* 주어지는 입력을 위하여
  * `update_range()`, `query()`메서드를 기반으로 동작한다.
  * 나머지 부분은 일반적인 segment tree와 비슷하게 동작하는데,
  * lazy propagation을 위한 `update_lazy()`메서드를 작성 및 활용했다.


(BOJ10999


# (BOJ11585 속타는 저녁 메뉴

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/11585
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/11000/11500/11585.py)

## 문제 설명

* 문자열을 1회 회전하며 문자열 패턴을 찾는 문제
* 문자열을 1회 회전하는것은 같은 문자열을 2번 이어 붙여서 탐색하는 것으로 해결할 수 있다.
* 탐색하는 문자열은 처음 주어진 문자열의 특정 회전 중 하나이므로, 최종 탐색 위치만 잘 고민하면 된다.

## 문제 풀이

````python
def get_lps(N: int, target: list):
    lps = [0] * N
    idx = 1
    len_idx = 0
    while idx < N:
        if target[idx] == target[len_idx]:
            len_idx += 1
            lps[idx] = len_idx
            idx += 1
        else:
            if len_idx:
                len_idx = lps[len_idx - 1]
            else:
                idx += 1
    return lps
````

* 빠른 패턴 매칭을 위한 lps를 구하는 함수
* 각 인덱스마다 같은 접두어와 접미어를 찾아 저장한다.

````python
def kmp(N: int, roulette: list, target: list, lps: list):
    count = 0
    idx = target_idx = 0
    while idx < N * 2 - 1:
        if roulette[idx] == target[target_idx]:
            idx += 1
            target_idx += 1
        else:
            if target_idx:
                target_idx = lps[target_idx - 1]
            else:
                idx += 1
        if target_idx == N:
            count += 1
            target_idx = lps[target_idx - 1]
    return count
````

* KMP 연산 함수
* while문을 실행할 때, `idx < N * 2`라고 하면, 1개를 더 찾을수도 있으므로 범위를 찰 지정해야한다.
* 처음 if-else 문에서는 KMP 알고리즘을 적용했다.
  * 만약 탐색하는 문자열, 목표 문자열의 각 위치의 값이 같다면, 인덱스를 증가
  * 만약 다르다면 목표 문자열에 대해 이미 구해놓은 lps를 활용하여 탐색할 위치의 인덱스를 찾는다.
* 탐색 문자열을 찾았다면, 해당 인덱스를 반환하는 대신, 더 탐색하기 위해 목표 문자열의 탐색에 대한 인덱스만 수정한다.

````python
N = int(input())
roulette = list(input().strip().split())
target = list(input().strip().split())
if roulette == roulette[0] * N:
	print("1/1")
	exit()
lps = get_lps(N, target)
count = kmp(N, roulette + roulette, target, lps)
g = gcd(N, count)
print(f"{count // g}/{N // g}")
````

* 최종 코드는 다음과 같다.


(BOJ11585


# (BOJ11785 CCW

* tags : [(algorithm](../%28algorithm.md) - *(CCW*
* 문제 링크 : https://www.acmicpc.net/problem/11758
* 풀이 링크

## 문제 설명

* 가장 기본적인 CCW 문제
* 세 점을 순서대로 2개의 벡터로 생각할 수 있고,
  * 두 백터의 사이 각을 백터 외적으로 구할 수 있음

$$\vec{a}\times\vec{b} = (\vert\vec{a}\vert\vert\vec{b}\vert \sin \theta)\vec{n}, (0 \leq \theta \leq \pi) $$

* 사이각을 $\theta$라고 하면, sin값이 양수, 0, 음수에 따라 각도를 알아낼 수 있음

## 문제 풀이

````python
CCW = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)
print(0 if not CCW else 1 if CCW > 0 else -1)
````

* 세 점을 순서대로 (x1, y1), (x2, y2), (x3, y3)으로 받은 후
  * 두개의 백터로 나누어 생각,
  * 외적값을 구하는 방식을 이용하여 사이 각에 대한 sin값을 알아냄
  * sin값은 180도를 기준으로 양수, 0, 음수이므로 각도를 알아낼 수 있음


(BOJ11785


# (BOJ12844 XOR

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/12844
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/12000/12800/12844.py)

## 문제 설명

* lazy propagation을 필요하지만, 문제 해결을 위한 추가적인 문제 해결 전략이 필요하다.
* 전반적인 코드는 [(백준 10999 구간 합 구하기 2](%28BOJ10999.md)와 같다.
  * 차이점은 연산이 더하기가 아니라 XOR인 부분이다.
  * 이 글에서도 해당 부분만 다루어 문제 풀이를 작성할 것이다.

## 문제 풀이

* 처음에는 연산은 더하기에서 XOR로 변경했는데, 문제 해결이 잘 되지 않았다.
  * 여기서 XOR의 특징을 생각해보면 그 답을 알 수 있다.
  * XOR은 교환법칙이 성립하고,
  * 어떤 수와 0을 XOR하면 그 수가 나오게 되고, 같은 수를 XOR하면 0이 된다.
  * 그래서 lazy를 적용할 때, 같은 수가 몇 번 XOR 되는지 생각하면 된다.

````python
def update_lazy(self, node: int, start: int, end: int) -> None:
	if self.lazy[node]:
		if (end - start + 1) % 2:
			self.tree[node] ^= self.lazy[node]
		if start != end:
			self.lazy[node * 2] ^= self.lazy[node]
			self.lazy[node * 2 + 1] ^= self.lazy[node]
		self.lazy[node] = 0

def update_range(
	self, node: int, start: int, end: int, left: int, right: int, k: int
) -> None:
	self.update_lazy(node, start, end)
	if right < start or end < left:
		return
	if left <= start and end <= right:
		if (end - start + 1) % 2:
			self.tree[node] ^= k
		if start != end:
			self.lazy[node * 2] ^= k
			self.lazy[node * 2 + 1] ^= k
		return
	mid = self.mid(start, end)
	self.update_range(node * 2, start, mid, left, right, k)
	self.update_range(node * 2 + 1, mid + 1, end, left, right, k)
	self.tree[node] = self.tree[node * 2] ^ self.tree[node * 2 + 1]
````

* 다른 메서드는 같이 작성되어 있는데, 이 두 메서드만 일부 수정되었다.
* 위의 방식을 생각하여, 어떤 수가 XOR이 몇 번 적용되는지, 특히 홀수 번 적용될때만 특정 위치마다 값을 갱신하고, 아니면 넘어가는 방식으로 구현했다.


(BOJ12844


# (BOJ13258 복권 + 은행

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/13258
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/13000/13200/13258.py)

## 문제 설명

* 연속하여 확률을 계산하여 최종 기대값을 계산해야 한다.
* 계산 방법만 이해한다면 어렵지 않게 접근하여 해결할 수 있다.

## 문제 풀이

````python
def calc_next(now: float, win_prob: float, prize: int) -> float:
    win_money = now + prize
    return win_money * win_prob + now * (1 - win_prob)


if __name__ == "__main__":
    N = II()
    accounts = list(map(int, input().split()))
    J = II()
    C = II()
    for _ in range(C):
        total_accounts = sum(accounts)
        accounts = [calc_next(now, now / total_accounts, J) for now in accounts]
    print(accounts[0])
````

* `calc_next()`함수로 각 기댓값을 구하는 것을 C번 반복하여 해결한다.


(BOJ13258


# (BOJ1389 케빈 베이컨의 6단계 법칙

* tags : [(algorithm](../%28algorithm.md) - *(floyd-warshall*
* 문제 링크 :  https://www.acmicpc.net/problem/1389
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/1000/1300/1389.py)

## 문제 설명

* 플로이드 와샬 등을 활용하여 모든 점사이 가중치를 구하고, 그 중 최소를 출력해야한다.
  * BFS 등으로도 구할 수 있지만, 플로이드 와샬로 해결했다.

## 문제 풀이

````python
friends = [[0] * N for _ in range(N)]
for _ in range(M):
	a, b = MIIS()
	friends[a - 1][b - 1] = 1
	friends[b - 1][a - 1] = 1
````

* 친구 관계 행렬 구성
* 기본적으로 관계가 없으면 0, 아니면 몇 번 건너 가면 만날 수 있는지 기록

````python
for k in range(N):
	for i in range(N):
		for j in range(N):
			if i == j:
				continue
			if not friends[i][k] or not friends[k][j]:
				continue
			t = friends[i][k] + friends[k][j]
			if friends[i][j] and friends[i][j] <= t:
				continue
			friends[i][j] = t
			friends[j][i] = t
````

* 거쳐가는 점, 시작 점, 도착점을 순서대로 순회
* 시작점 == 도착점이면 넘어가고,
* 둘러가는 경우가 새롭게 친구가 생기거나 더 가까운 경우라면 갱신

````python
ans = [(sum(friends[i]), i + 1) for i in range(N)]
ans.sort()
print(ans[0][1])
````

* 출력을 위해 list confrehension을 활용했고,
  * 해당 배열 정렬 후 인덱스 출력


(BOJ1389


# (BOJ1459 걷기

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/1459
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/1000/1400/1459.py)
  * [Go](https://github.com/mintropy/PS/blob/master/BAEKJOON/Golang/1000/1400/1459.go)
  * [TypeScript](https://github.com/mintropy/PS/blob/master/BAEKJOON/typescript/1000/1400/1459.ts)

## 문제 설명

* 좌표 이동을 최단거리로 해야하는데, 주어진 조건에 따라 조건 분기를 잘 해야함
* 여기서 조건은 하나만 신경쓰면 되는데,
  * 대각선으로 가는게 빠를 수 있는 두가지 조건만 신경쓰면된다.
  * 첫 번째는 오른쪽, 위쪽으로 각각 한 번씩 이동하는 경우 대각선으로 한번만 가는게 더 빠른지
  * 두 번째는 오른쪽 또는 위쪽으로 두번 가는 것보다, 대각선으로 두 번 이동하는게 더 빠른지
  * 이 두가지 경우를 확인하면 된다.

## 문제 풀이

### Python

````python
X, Y, W, S = map(int, input().split())
min_val, max_val = min(X, Y), max(X, Y)
dist = 0
if S < W * 2:
	dist += min_val * S
	if S < W:
		dist += ((max_val - min_val) // 2) * 2 * S
		dist += ((max_val - min_val) % 2) * W
	else:
		dist += (max_val - min_val) * W
else:
	dist += (X + Y) * W
````

* 위에서 말한 조건에 따라 두가지를 분류하여 수를 확인
* 우선, 첫번째, 두번째 각각 경우를 얼마까지 실행할 수 있는지 확인하기 위해 X, Y 중 최댓값을 구한다.
  * 최솟값 기준으로 대각선으로 이동하는 횟수가 가로, 세로로 이동하는 횟수보다 적다.
    * (0, 0)에서 (3, 3)으로 이동한다고 할 때, 가로, 세로로 이동하면 총 6번 이동이 필요한데,
    * 대각선으로 이동하면 3번으로 가능하다
  * 두 번째 경우에서는, 대각선으로 최대한 이동한 후, 가로 또는 세로로 이동횟수를 구한다.
    * (0, 0)에서 (3, 5)로 이동한다고 할 때, (3, 3)까지는 위의 방법으로 이동
    * 이후 (3, 3)에서 (3, 5)로 이동하는 경우 위로 2번 이동할수도 있지만, 대각선으로 2번 이동하여 완료할수도 있음
    * 이 때, 대각선으로 이동하는 비용과 격자를 따라 이동하는 비용을 비교하면 됨

### Go

````go
X, Y, W, S := ArrayToNums(text)
dist := 0
if S < W*2 {
	var min, max int
	if X > Y {
		min, max = Y, X
	} else {
		min, max = X, Y
	}
	dist += min * S
	if S < W {
		dist += int((max-min)/2) * 2 * S
		dist += ((max - min) % 2) * W
	} else {
		dist += (max - min) * W
	}
} else {
	dist += (X + Y) * W
}
````

* 전반적인 풀이는 유사하나, min, max 함수가 없는 부분, 주어진 입력을 변환하는 부분만 신경을 씀
  * `fmt.Scanf()`를 쓰면 각 입력별 변수를 정수로 지정하여 해결할 수 있을 것 같은데, `bufio.NewScanner()`를 활용하는 경우 따로 방법을 찾지 못하여 각각 변경하여 활용

### TypeScript

````ts
const [X, Y, W, S] = input
const minVal: number = Math.min(X, Y)
const maxVal: number = Math.max(X, Y)

let dist: number = 0
if (S < W * 2) {
  dist += minVal * S
  if (S < W) {
    dist += Math.floor((maxVal - minVal) / 2) * 2 * S
    dist += ((maxVal - minVal) % 2) * W
  } else {
    dist += (maxVal - minVal) * W
  }
} else {
  dist += (X + Y) * W
}
````

* TS풀이에서는 두가지 정도 살펴볼면 좋을 것 같다.
* 첫 번째는 minVal, maxVal을 선언하는 부분인데,
  * 한 줄에 선언을 하니, Math를 여러번 불러온다고 경고문구가 떴다.
  * 해결하는 방법은 JS에 조금 더 익숙해져야 잘 다룰 수 있을 것 같아, 각각 선언하는 것으로 해결했다.
  * 검색결과 import나 require등을 활용해서 선언하면 된다는데, 잘 해결되지 않았다.
* 두 번째는 `parseInt()`함수를 활용해 실수에서 정수로 변환하려 했는데,
  * 해당 함수는 문자열을 입력으로 받아서 경고가 발생했다.
  * 대신 `Math.floor()`를 활용해서 해결했다.


(BOJ1459


# (BOJ1655 가운데를 말해요

* tags : [(algorithm](../%28algorithm.md) - *(heap*
* 문제 링크 : https://www.acmicpc.net/problem/1655
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/1000/1600/1655.py)

## 문제 설명

* 입력을 순서대로 받으며 전체 입력에서 중간값을 계속 출력해야 한다.
* 입력값을 계속 정렬한다면 아마 시간초과가 날 것으로 보인다.
  * 특히 시간 제한을 가진 문제라 더욱 그렇다.
* 그렇기 때문에 입력값들 중 중간값을 기준으로 작은 값, 큰 값을 구분하ㅓ여 가지고 있으면 좋다.
  * 그리고 지속적으로 값을 넣고 빼기 위하여 heap구조를 활용하면 편하게 처리할 수 있다.

## 문제 풀이

````python
N = II()
mid = II()
ans = f"{mid}\n"
small_val, large_val = [], []
````

* 풀이를 위한 초기 설정
* 처음 2개 값을 입력 받는다.
  * N은 입력의 개수이고, 주어진 입력 중 첫 번째 값은 mid값으로 둔다.
* 다음 중간값을 기준으로 더 작은 값, 큰 값을 저장할 heap을 만들어둔다.

````python
for i in range(1, N):
	k = II()
	if i % 2:
		if k < mid:
			heappush(large_val, mid)
			mid = -heappushpop(small_val, -k)
		else:
			heappush(large_val, k)
	else:
		if k > mid:
			heappush(small_val, -mid)
			mid = heappushpop(large_val, k)
		else:
			heappush(small_val, -k)
	ans += f"{mid}\n"
````

* 문제 풀이 코드 부분
* 우선, 총 N개의 입력이 주어지는데, 처음 한개 입력을 mid값으로 사용했으므로, N-1개 값만 입력을 받는다.
* 각 입력을 받고, 입력 받은 수의 갯수에 따라 경우의 수를 나누어 처리한다.
  * 만약 i가 홀수라면, small_val, large_val 두 개의 heap에 저장된 수의 갯수가 같다.
    * 이 경우, large_val에 1개 값이 더 저장되도록 한다.
  * i가 짝수라면 이미 large_val에 1개 값이 더 많이 저장되어 있다.
    * 그래서 small_val, large_val에 저장될 숫자의 갯수가 같아지도록 한다.


(BOJ1655


# (BOJ17088 등차수열 변환

* tags : [(algorithm](../%28algorithm.md) - *(brute force*
* 문제 링크 : https://www.acmicpc.net/problem/17088
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/17000/17000/17088.py)

## 문제 설명

* 등차수열을 구하는 점에서, 우선 공차(인접한 두 항의 차)가 정해진다면 쉽게 수열을 결정할 수 있다는 점을 생각할 수 있다.
* 여러가지 방법을 고민했는데, 첫번째 항과 두번째 항이 각각 그대로 사용, 1씩 더하거나 뺄 수 있고,
  * 총 9가지 경우의수만 탐색하면 된다.

## 문제 풀이

* 우선 수열 길이가 2이하이거나, 모두 같은 숫자로 이루어진 수열이면 0을 출력한다.

````python
for i in range(-1, 2, 1):
	for j in range(-1, 2, 1):
		tmp = abs(i) + abs(j)
		tmp_seq = seq[::]
		tmp_seq[0] += i
		tmp_seq[1] += j
		diff = tmp_seq[1] - tmp_seq[0]
````

* 이 부분은 총 9가지 경우의 수를 탐색하는 부분이다.
  * 첫 번째 항과 두 번째 항에 각 연산을 한 뒤 공차를 diff로 선언한다.

````python
for k in range(2, N):
	_diff = tmp_seq[k] - tmp_seq[k - 1]
	if _diff == diff:
		continue
	if _diff == diff + 1:
		tmp_seq[k] -= 1
		tmp += 1
	elif _diff == diff - 1:
		tmp_seq[k] += 1
		tmp += 1
	else:
		break
else:
	if ans == -1 or ans > tmp:
		ans = tmp
````

* 한번 더 for문을 순회하며, 공차 diff로 수열을 만들 수 있는지 확인한다.
* 각 위치별 값의 차이를 \_diff로 선언했고,
  * 공차와의 차이가 1이하일 때 해당하는 연산을 하고,
  * 아니라면 for문을 종료한다.
* 최초 ans값을 -1로 선언했는데, for문이 정상적으로 종료되면
  * ans값이 -1이거나 더 작은 값을 발견하면 갱신해준다.


(BOJ17088


# (BOJ17140 이차원 배열과 연산

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/17140
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/17000/17100/17140.py)

## 문제 설명

* 이차원 배열이 주어지고, 해당 배열에서 특정 위치의 값이 원하는 값이 될 때까지의 연산 횟수를 구하는 문제이다.
* 연산은 지금 배열의 행, 열 길이에 따라 자동적으로 결정된다.
  * 연산을 적용하는 위치는 행, 열의 길이에 따라 바뀌지만,
  * 연산은 같은 방식으로 진행된다.
* 행의 길이, 열의 길이, 행에 연산, 열에 연산 등 조금씩 햇갈릴 수 있는 부분이 있어 이 부분만 주의하면 될 것 같다.

## 문제 풀이

````python
r, c, k = MIIS()
r, c = r - 1, c - 1
seq = [[0] * 100 for _ in range(100)]
for i in range(3):
	x, y, z = MIIS()
	seq[i][0] = x
	seq[i][1] = y
	seq[i][2] = z
````

* 최대 100개 길이만 사용한다고 했고, 때에 따라 리스트를 조정하는 것 보다 100 * 100의 리스트를 먼저 생성하는 것이 더 효율적일 것이라 생각함
* 그 후 왼쪽 위 3 * 3 구역에 값을 입력
* 인덱스가 0이 아니라 1부터 시작하는 값을 찾으므로, r, c는 1씩 빼줌

````python
row, column = 3, 3
for count in range(101):
	if seq[r][c] == k:
		print(count)
		break
	if row >= column:
		for i in range(row):
			sort_row(i)
	else:
		for i in range(column):
			sort_column(i)
	count += 1
else:
	print(-1)
````

* 문제 풀이의 핵심 코드
* 우선 행의 길이, 열의 길이에 따라 연산을 적용하는 위치가 변경된다.
  * 그런데, 리스트를 동적으로 크기 조절하는 것이 아니라 100 * 100으로 고정했기 때문에 연산할 위치를 다시 탐색해야 하는 경우가 발생할 수 있다.
  * 그래서 지금 행, 열의 실질적 길이를 저장하기 위해 row, column 변수를 생성했다.
* 다음 for 문을 순회하며 탐색한다.
  * 처음에는 while문으로 구성했는데, 어짜피 탐색은 최대 100번까지만 하게 되어 for-else로 구성했다.
  * 문제에서 “100초가 지나도”라는 부분때문에 99초까지 탐색했는데 틀렸다는 결과가 나왔는데, 100초까지 탐색, 100초 초과는 -1 출력을 의미하는 것 같아서 위와 같이 구성했다.
* 만약 특정 위치 값이 일치하면 횟수를 출력, 종료하고, 아니라면 행, 열의 길이에 따라 연산을 수행한다.

````python
def sort_row(idx: int):
    global seq, row, column
    count_nums = {}
    for i in range(column):
        x = seq[idx][i]
        if not x:
            continue
        if x in count_nums:
            count_nums[x] += 1
        else:
            count_nums[x] = 1
    new_nums = sorted([(v, k) for k, v in count_nums.items()][:50])
    for i, (x, y) in enumerate(new_nums):
        seq[idx][i * 2] = y
        seq[idx][i * 2 + 1] = x
    for j in range(len(new_nums) * 2, 100):
        seq[idx][j] = 0
    if column < len(new_nums) * 2:
        column = len(new_nums) * 2


def sort_column(idx: int):
    global seq, row, column
    count_nums = {}
    for i in range(row):
        x = seq[i][idx]
        if not x:
            continue
        if x in count_nums:
            count_nums[x] += 1
        else:
            count_nums[x] = 1
    new_nums = sorted([(v, k) for k, v in count_nums.items()][:50])
    for i, (x, y) in enumerate(new_nums):
        seq[i * 2][idx] = y
        seq[i * 2 + 1][idx] = x
    for j in range(len(new_nums) * 2, 100):
        seq[j][idx] = 0
    if row < len(new_nums) * 2:
        row = len(new_nums) * 2
````

* 각 연산이 행 또는 열에 적용될 때 각 행, 열을 정렬하는 함수
  * 두 함수에서는 유사한 부분도 많지만, 결과적으로 값을 추출, 적용하는 위치가 달라 두 개의 함수로 분리했다.
* 우선 최대 row * column 만큼만 값이 있으므로 해당 부분을 탐색하여 각 값의 갯수를 기록한다.
  * 다음 new_nums에 위에서 저장한 값을 하나씩 불러와서 저장 및 정렬하고, 그 값들을 기록한다.
* 배열 길이가 짧아질수도 있기 때문에 나머지 부분은 0으로 표시하고,
* 최대 길이를 갱신한다.


(BOJ17140


# (BOJ17281 ⚾

* tags : [(algorithm](../%28algorithm.md) - *(brute force*
* 문제 링크 : https://www.acmicpc.net/problem/17281
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/17000/17200/17281.py)

## 문제 설명

* 야구 규칙을 따라 구현하는 문제
  * 모든 경우의 수를 탐색하는 브루트 포스가 필요하고,
  * 각 경우 탐색 과정도 몇가지 유의사항만 따르면 된다.

## 문제 풀이

````python
def make_turn(turn: tuple[int]) -> list[int]:
    turn = list(turn[:3]) + [0] + list(turn[3:])
    return turn


def simulate(N: int, hitters: list[list[int]], turn: list[int]) -> int:
    idx = score = 0
    for inning in range(N):
        out = 0
        first = second = third = 0
        while out < 3:
            hitter = turn[idx]
            point = hitters[inning][hitter]
            if point == 0:
                out += 1
            elif point == 1:
                score += third
                first, second, third = 1, first, second
            elif point == 2:
                score += second + third
                first, second, third = 0, 1, first
            elif point == 3:
                score += first + second + third
                first, second, third = 0, 0, 1
            elif point == 4:
                score += 1 + first + second + third
                first = second = third = 0
            idx = (idx + 1) % 9
    return score


if __name__ == "__main__":
    N = int(input())
    hitters = [list(map(int, input().split())) for _ in range(N)]
    max_score = 0
    for perm in permutations(range(1, 9), 8):
        score = simulate(N, hitters, make_turn(perm))
        if max_score < score:
            max_score = score
    print(max_score)
````

* `itertools.permuations()`를 활용하여 모든 경우의 수를 구하고,
  * 1번 타자가 4번째 순번에 오도록 조정한다.
* 구현 과정에서 각 이닝별 진행상황과 타자 번호 등을 잘 확인하면 된다.


(BOJ17281


# (BOJ1948

* tags : [(algorithm](../%28algorithm.md) - *(topological sort*
* 문제 링크 : https://www.acmicpc.net/problem/1948
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/1000/1900/1948.py)

## 문제 설명

* 기본적으로 최단 경로를 찾아야 하는 문제인데, 두가지를 더 고려해야 한다.
  * 최단 경로를 찾아야 하지만, 최대 시간을 구해야 하고,
  * 최대 시간이 걸리는 경로를 모두 찾아야 한다.
* 근데 여기서 조금 고민을 했는데, 문제에서 ‘이런 사람들이 지나는 도로의 수를 카운트 하여라’ 부분이 잘 이해가 가지 않았다.
  * 이 부분은 다음과 같이 설명된다.
  * 문제에서 요구하는 출발지에서 도착지까지 최대 시간을 구하고,
  * 해당 시간이 걸리는 모든 도로를 구한 다음,
  * 그 도로들을 중복 없이 세어주면 된다.
  * 예를 들어 1→2→3→5, 1→2→4→5 라는 두가지 경로가 똑같이 최대 시간으로 걸린다고 할 때, 도로의 수는 각 경로의 길이 3+3=6이 아니라, 각 도로의 수 5(1→2, 2→3, 2→4, 3→5, 4→5)를 출력해야 한다.

## 문제 풀이

* 풀이 코드는 크게 3가지 부분으로 구성되어 있다.
  * 경로 탐색을 위한 설정
  * 최단 경로 최대 시간 탐색
  * 도로의 수 찾기

````python
N = int(input())
M = int(input())
roads = [[] for _ in range(N + 1)]
in_roads = [0] * (N + 1)
for _ in range(M):
	s, e, t = MIIS()
	roads[s].append((e, t))
	in_roads[e] += 1
st, end = MIIS()
````

* 도로는 단방향이므로, 연결 리스트를 활용, 다음 도로를 저장하는 방식으로 구성했다.

````python
time = [0] * (N + 1)
parent = [[] for _ in range(N + 1)]
queue = deque([(st, 0)])
while queue:
	x, t = queue.popleft()
	for y, _t in roads[x]:
		in_roads[y] -= 1
		next_time = t + _t
		if time[y] == next_time:
			parent[y].append(x)
		if time[y] < next_time:
			time[y] = next_time
			parent[y] = [x]
		if not in_roads[y]:
			queue.append((y, time[y]))
````

* 경로 탐색은 위상 정렬을 활용했다.
* 도로의 수를 탐색하기 위해 parent리스트를 만들었고, 경로의 시간이 최대가 될 때 부모로 추가했다.

````python
roads_count = set()
queue = deque([end])
while queue:
	x = queue.popleft()
	for y in parent[x]:
		if (y, x) in roads_count:
			continue
		roads_count.add((y, x))
		if y != st:
			queue.append(y)
````

* 도로의 수를 탐색하기 위해 set을 활용했다.
  * 위에서 설명한 것 처럼, 최대 시간이 되는 모든 경로에 사용되는 도로들을 모아서 판단해야 하는데,  도로의 수를 단순하게 세어 가는 방식으로는 쉽지 않았다.
  * 그래서, 그러한 도로를 모두 set에 추가하여 갯수를 파악했다.
* 위에서 각 부모를 저장한 것을 활용했는데, 모든 부모를 탐색하는 것이 아니라, 최대 시간이 되는 경로만 탐색하므로, 따로 저장하고 활용했다.


(BOJ1948


# (BOJ1958 LCS3

* tags : [(algorithm](../%28algorithm.md) - *(LCS*
* 문제 링크 : https://www.acmicpc.net/problem/1958
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/1000/1900/1958.py)

## 문제 설명

* 여러 입력의 공통 LCS를 구하는 문제
* 처음에는 입력을 2개씩 순차적으로 LCS를 구하는 방식으로 생각했는데, 2개씩 비교하다보면 모든 입력을 고려하지 못하는 경우가 발생한다.
* 그래서 이 문제의 경우 3개의 입력을 한번에 확인하는 DP를 만들어 해결했다.

## 문제 풀이

````python
S1, S2, S3 = input().strip(), input().strip(), input().strip()
l1, l2, l3 = len(S1), len(S2), len(S3)
dp = [[[0] * (l3 + 1) for _ in range(l2 + 1)] for _ in range(l1 + 1)]
for i, x in enumerate(S1):
	for j, y in enumerate(S2):
		for k, z in enumerate(S3):
			if x == y == z:
				dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1
			else:
				dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
print(dp[l1 - 1][l2 - 1][l3 - 1])
````

* 우선 3개의 입력에 대하여 처리할 수 있는 DP리스트를 만든다.
* 2개의 입력에 대한 LCS를 실행하는 것 처럼 3개로 실행한다.
  * 세 입력을 순차적으로 순회하고,
  * 만약 특정 위치에서의 값이 같다면 LCS값을 업데이트 하고
  * 아니라면 최대값만 갱신한다.


(BOJ1958


# (BOJ20061 모노미노도미노 2

* tags : [(algorithm](../%28algorithm.md) - *(simulate*
* 문제 링크 : https://www.acmicpc.net/problem/20061
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/20000/20000/20061.py)

## 문제 설명

* 주어진 입력에 따라 구현하면 되는 문제
* 주어진 구조가 조금 독특하여 해당 구조를 탐색, 적용하는 것이 조금 번거로울 수 있다.
* 우선 블록이 주어지면, 두 방향으로 최대한 이동한 후, 테트리스 처럼 맞추어진 줄을 제거, 해당 방향으로 윗 블럭들을 당긴다.
* 그리고 특정 구간에 블록이 없도록 이동시켜주는 작업도 필요하다.

## 문제 풀이

````python
if __name__ == "__main__":
    board = [[0] * 10 for _ in range(10)]
    points = 0
    for _ in range(int(input())):
        t, x, y = map(int, input().split())
        if t == 1:
            blocks = ((x, y),)
        elif t == 2:
            blocks = ((x, y), (x, y + 1))
        elif t == 3:
            blocks = ((x, y), (x + 1, y))
        points += move_blocks(blocks)
    print(points)
    print(count_blocks())
````

* 우선 기본적인 풀이코드 구조는 다음과 같다.
* 게임 보드는 “ㄱ”모양 이지만, 해당 모양으로 자료구조를 선언하는것이 불편하기 때문에 10 * 10 크기로 선언했다.
* 게임을 진행하며 얻을 점수를 저장할 points 변수도 선언했다.
* 순서대로 입력 받으며 문제를 해결하는데, 기본적으로`move_blocks()`함수를 호출하여 해결한다.

````python
def move_blocks(blocks: Block) -> int:
    global board
    points = 0
    green_pos = move_single_block(blocks, True)
    blue_pos = move_single_block(blocks, False)
    points += push_blocks(green_pos, True)
    points += push_blocks(blue_pos, False)
    return points
````

* 각 순서를 진행하는 `move_blocks()`함수
* 여기서 `move_single_block()`함수와 `push_blocks()`함수를 호출하여 해결한다
  * `move_single_block()`함수는 처음 생성된 블록을 초록, 파랑 영역으로 보내는 함수이고, 
  * `push_blocks()`함수는 각 줄이 완성되어 점수를 낼 수 있는지, 비어 있는 줄 또는 존재할 수 없는 곳에 블록이 있는 경우 이동시켜주는 함수이다.

````python
def move_single_block(blocks: Block, is_green: bool) -> Block:
    def check_board(blocks: Block, is_green: bool) -> bool:
        for x, y in blocks:
            if is_green and x >= 10:
                return False
            elif not is_green and y >= 10:
                return False
        return True

    while True:
        if is_green:
            next_blocks = tuple((x + 1, y) for x, y in blocks)
        else:
            next_blocks = tuple((x, y + 1) for x, y in blocks)
        if not check_board(next_blocks, is_green):
            return blocks
        if not check_blocks(next_blocks):
            return blocks
        blocks = next_blocks


def check_blocks(blocks: Block) -> bool:
    global board
    for x, y in blocks:
        if board[x][y]:
            return False
    return True
````

* 각 블록을 이동시키는 함수들이다.
* 우선 `move_single_block()`이 호출되면, 블록을 이동하며 해당 위치에 블록을 둘 수 있는지 확인한다.
  * 이 과정은 다시 두가지로 나뉘는데, 
  * 첫 번째는 10 * 10 공간을 벗어나지 않는지 확인하고,
  * 다른 블록과 겹치지 않는지 확인한다.

````python
def push_blocks(blocks: Block, is_green: bool) -> int:
    global board
    points = 0
    for x, y in blocks:
        board[x][y] = 1
    for i in range(6, 10):
        if check_line(i, is_green):
            points += 1
            pull_lines(i, is_green)
    for i in range(4, 6):
        for j in range(4):
            if is_green:
                if board[i][j]:
                    pull_lines(9, True)
                    break
            else:
                if board[j][i]:
                    pull_lines(9, False)
                    break
    return points


def check_line(line_idx: int, is_green: bool) -> bool:
    global board
    for j in range(4):
        if is_green:
            if board[line_idx][j]:
                continue
            return False
        else:
            if board[j][line_idx]:
                continue
            return False
    for j in range(4):
        if is_green:
            board[line_idx][j] = 0
        else:
            board[j][line_idx] = 0
    return True


def pull_lines(line_idx: int, is_green: bool) -> None:
    global board
    for i in range(line_idx - 1, 2, -1):
        for j in range(4):
            if is_green:
                board[i + 1][j] = board[i][j]
            else:
                board[j][i + 1] = board[j][i]
````

* 블록을 이동하는 것도 크게 두가지로 구분되어 동작한다.
* 먼저 각 줄마다 점수를 획득할 수 있는지, 그렇다면 해당 줄의 블록들을 제거한다.
* 그 다음으로 블록이 있으면 안되는 공간에 있다면, 해당 블록을 원하는 구역으로 넣을 대 까지 이동시켜준다.


(BOJ20061


# (BOJ20149 선분 교차 3

* tags : [(algorithm](../%28algorithm.md) - *(CCW*
* 문제 링크 : https://www.acmicpc.net/problem/20149
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/20000/20100/20149.py)

## 문제 설명

* 이 글은 텍스트와 코드 기반으로 작성되어, 이해가 어려울 수 있음.
  * 추가적인 설명이 필요하다면 블로그글 참조 : [백준 20149 선분교차 3]()
* 문제는 매우 간단하다.
  * 두 선분의 끝점이 주어지고, 교차하는지 판별하면 된다.
* 우선, 선분 교차를 잘 이해하고 해결하기 위해 CCW과 관련한 지식이 필요하다.
  * 두 선분이 있을 때, 전혀 다른 위치이면 오히려 쉽게 판별할 수 있지만, 만약 두 선분이 일직선상에 있는 등의 경우를 판별할 때 편리하게 할 수 있다.
* 만약 선분위치를 분류하면 크게 3가지로 분류가 된다.
  * 하나의 직선 위에 있는 경우
  * 교차할 수 있는 위치
  * 교차할 수 없는 위치
* 그리고 각 경우를 잘 구분하여 문제를 해결한다.

## 문제 풀이

````python
x1, y1, x2, y2 = MIIS()
x3, y3, x4, y4 = MIIS()
ccw1 = ccw(x1, y1, x2, y2, x3, y3)
ccw2 = ccw(x1, y1, x2, y2, x4, y4)
ccw3 = ccw(x3, y3, x4, y4, x1, y1)
ccw4 = ccw(x3, y3, x4, y4, x2, y2)

tmp1, tmp2 = ccw1 * ccw2, ccw3 * ccw4
````

* 우선 총 주어진 4개의 점에 대한 ccw를 구하고,
  * 각각 선분 기준으로 구한 ccw끼리 곱한다.
  * 이렇게 하면, 하나의 선분 기준으로 다른 선분의 두 점의 위치를 파악할 수 있다.

````python
if not tmp1 and not tmp2:
	if (x1, y1) > (x2, y2):
		x1, y1, x2, y2 = x2, y2, x1, y1
	if (x3, y3) > (x4, y4):
		x3, y3, x4, y4 = x4, y4, x3, y3
	if (x1, y1) <= (x4, y4) and (x2, y2) >= (x3, y3):
		print(1)
		get_point((x1, y1), (x2, y2), (x3, y3), (x4, y4))
	else:
		print(0)
````

* 만약 tmp1, tmp2 값이 모두 0인경우는 두 선분이 하나의 직선 위에 있거나, 하나의 점을 공유하는 경우이다.
  * 이 때, 두 선분의 위치를 판별하기 위해 왼쪽 아래의 점, 오른쪽 위의 점으로 구분하고,
  * 선분이 교차하는 경우 1을 출력, 아니면 0을 출력한다.
  * 선분이 교차하는 경우 교점이 유일한지 확인한다. 해당 함수는 뒤에서 다시 다루겠다.

````python
if tmp1 <= 0 and tmp2 <= 0:
	print(1)
	get_point((x1, y1), (x2, y2), (x3, y3), (x4, y4))
else:
	print(0)
````

* 위의 경우가 아니라면, 선분이 교차하거나 교차하지 않는 경우다.
* 만약 선분이 교차하려면 tmp1, tmp2의 값 모두 0이하가 되야 하고,
  * 역시 1을 출력, 교점을 확인한다.

````python
def get_point(A: tuple, B: tuple, C: tuple, D: tuple):
    x1, y1 = A
    x2, y2 = B
    x3, y3 = C
    x4, y4 = D
    m = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
    if m:
        x = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / m
        y = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / m
        print(x, y)
    else:
        if B == C and A <= C:
            print(*B)
        elif A == D and C <= A:
            print(*A)
````

* 교점을 찾는 함수
* 도 선분을 직선으로 생각하여, 두 교점을 찾고 출력한다.

# 참조

* https://velog.io/@jini_eun/%EB%B0%B1%EC%A4%80-20149-%EC%84%A0%EB%B6%84-%EA%B5%90%EC%B0%A8-3-Java-Python
* https://cocoon1787.tistory.com/489


(BOJ20149


# (BOJ23286 허들 넘기

* tags : [(algorithm](../%28algorithm.md) - *(floyd-warshall*
* 문제 링크 : https://www.acmicpc.net/problem/23286
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/23000/23200/23286.py)

## 문제 설명

* 문제에서는 허들이라고 했지만, 그래프를 구성하는 간선의 최댓값을 최소화하는 문제이다.
* 생성된 그래프에서 플로이드와샬로 간단하게 해결했다.

## 문제 풀이

````python
N, M, T = MIIS()
hurdles = [[-1] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
	u, v, h = MIIS()
	hurdles[u][v] = h
for k in range(1, N + 1):
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			if hurdles[i][k] == -1 or hurdles[k][j] == -1:
				continue
			max_hurdle = max(hurdles[i][k], hurdles[k][j])
			if hurdles[i][j] == -1 or hurdles[i][j] > max_hurdle:
				hurdles[i][j] = max_hurdle
for _ in range(T):
	s, e = MIIS()
	print(hurdles[s][e])
````

* 코드가 길지 않아 전체 코드를 가져왔다.
* 각 간선은 방향이 있어 방향에 따라 저장했다.
* 거쳐가는 점, 출발 점, 도착 점을 순서대로 for문으로 순회하였고
  * 연결할 수 있고, 새로운 연결이거나, 허들 높이가 낮아지는 경우 최신화했다.
* 출력은 출발, 도착점 기준으로 바로 출력할 수 있기 때문에 짧은 코드로 해결할 수 있었다.


(BOJ23286


# (BOJ2445 별 찍기 - 8

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/2445
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/2000/2400/2445.py)
  * [Go](https://github.com/mintropy/PS/blob/master/BAEKJOON/go/2000/2400/2445.go)
  * [Node.js](https://github.com/mintropy/PS/blob/master/BAEKJOON/Node/2000/2400/2445.js)

## 문제 설명

* 규칙에 따라 출력하는 단순한 문제

## 문제 풀이

### Python

````python
N = int(input())
output = ""
for i in range(1, N + 1):
	output += "*" * i + " " * (N - i) + " " * (N - i) + "*" * i + "\n"
for i in range(N - 1, 0, -1):
	output += "*" * i + " " * (N - i) + " " * (N - i) + "*" * i + "\n"
print(output)
````

* 문자열 연산으로 간단하게 구현

### Go

````go
for i := 1; i <= N; i++ {
	for j := 0; j < i; j++ {
		wr.WriteByte('*')
	}
	for j := 0; j < N-i; j++ {
		wr.WriteByte(' ')
	}
	for j := 0; j < N-i; j++ {
		wr.WriteByte(' ')
	}
	for j := 0; j < i; j++ {
		wr.WriteByte('*')
	}
	wr.WriteByte('\n')
}
````

* Go의 문자열은 immutable
* 아마 슬라이스나 배열에 저장하고 출력하는 방법을 썼으면 줄마다 출력하지 않아도 됬을 것 같다.

### Node.js

````js

for (let i = 1; i <= N; i++) {
  for (let j = 0; j < i; j++) {
    output += "*"
  }
  for (let j = 0; j < N - i; j++) {
    output += " "
  }
  for (let j = 0; j < N - i; j++) {
    output += " "
  }
  for (let j = 0; j < i; j++) {
    output += "*"
  }
  output += "\n"
}
````

* Go와 유사하지만 문자열을 더해가며 마지막에 한번에 출력하는 방식으로 구현


(BOJ2445


# (BOJ25315 N수매화검법

* tags : [(algorithm](../%28algorithm.md) - *(CCW*
* 문제 링크 : https://www.acmicpc.net/problem/25315
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/25000/25300/25315.py)

## 문제 설명

* 입력되는 선분의 선분 교차를 판별하는데, 몇가지 조건을 더 만족해야 한다.
* 첫 번째는 조건이라 하기에는 애매할 수 있지만, 최대 2500개 선분 입력을 처리해야 하고, 서로 교차하는지 확인하기 위해 $O(N^2)$의 시간이 필요하다.
* 두 번째는 가중치가 있고, 가중치를 활용한 연산 결과가 가장 작게 나오는 것을 목표로 한다.
* 이 외에는 특별한 내용이 없기 때문에 CCW를 활용하여 간단하게 해결할 수 있지만, 시간 조건 등과 같은 부분은 고민을 해 봐야 한다.

## 문제 풀이

````python
Point = tuple[int]


def get_ccw(A: Point, B: Point, C: Point) -> int:
    ccw = (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])
    return 0 if not ccw else 1 if ccw > 0 else -1


if __name__ == "__main__":
    N = int(input())
    actions = []
    for _ in range(N):
        sx, sy, ex, ey, w = map(int, input().split())
        actions.append(((sx, sy), (ex, ey), w))
    actions.sort(key=lambda x: x[2])
    ans = 0
    for idx, (S1, E1, w1) in enumerate(actions):
        count = 1
        for i in range(idx + 1, N):
            S2, E2, _ = actions[i]
            tmp1 = get_ccw(S1, E1, S2) * get_ccw(S1, E1, E2)
            tmp2 = get_ccw(S2, E2, S1) * get_ccw(S2, E2, E1)
            if tmp1 < 0 and tmp2 < 0:
                count += 1
        ans += count * w1
    print(ans)
````

* 코드가 길지 않기 때문에 전체 코드를 먼저 가져왔다.
* 우선 CCW 계산을 위한 함수를 만들었다.
* 입력은 list confrehension으로 처리할 수 있지만, 각 점을 더 편하게 가져다 쓰기 위해 tuple 형태로 저장했다.
  * 입력은 가중치 오름차순으로 정렬했는데, 이는 결과값을 최소로 만들기 위해서다.
* 2개의 for문의 구성이 독특하다고 생각할 수 있는데, 이는 시간을 최소화하기 위해 구성한 부분이다.
  * 성능과 관련해서는 뒷 부분에서 다시 한 번 다루겠다.
  * 비교를 위한 하나의 선분을 선택하고, 다른 선분과의 교차여부를 판별한다.
  * 이 때, 문제에서 어느 세 점도 한 직선에 있지 않다는 조건이 있기 때문에, CCW값만 비교하여 교차 여부를 판별할 수 있다.

````python
for i in range(N):
	S1, E1, w1 = actions[i]
	count = 1
	for j in range(i + 1, N):
		S2, E2, w2 = actions[j]

for idx, (S1, E1, w1) in enumerate(actions):
	count = 1
	for _, (S2, E2, _) in enumerate(actions[idx + 1 :]):
````

* for문을 위의 두가지 방식으로도 구성해 보았다.
  * 우선 첫 번째 경우는 인덱스만 순회하고, 각 값을 가져오는 방식이고,
  * 두 번째는 enumerate만 사용하는 경우인데, if 조건문 대신 슬라이싱을 사용한 경우이다.
* 우선 성능은 가장 위에 작성된 코드, 인덱스만 순회하는 for문, enumerate만 사용하는 for문 순서이다.
  * enumerate가 일반적인 경우보다는 빠르지만, 슬라이싱이 포함되어 더 느리게 동작한것으로 보인다.


(BOJ25315


# (BOJ2594 놀이공원

* tags : [(algorithm](../%28algorithm.md) - *(sweeping*
* 문제 링크 : https://www.acmicpc.net/problem/2594
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/2000/2500/2594.py)

## 문제 설명

* 시간을 활용하는 문제
* 주어진 시간을 제외한 시간 중, 연속된 최고 시간을 선택한다.
* 아마 두가지 방법 정도가 있을 것 같은데,
  * 첫 번째는 주어지는 시간이 최대 60 * 10분이므로, 해당 길이 배열을 생성 후 확인 할 수 있고
  * 다른 방법은 시간을 정렬, 스위핑을 통하여 비어있는 시간 중 최대 시간을 뽑아낼 수 있다.
* 이 문제는 스위핑으로 해결했다.

## 문제 풀이

* 시간을 `HHMM`형식이 아니라 전부다 분으로 바꿨으면 더욱 편리하게 해결했을 것 같다.

````python
schedules = []
for _ in range(N):
	st, end = map(int, input().split())
	if st % 100 < 10:
		st = st - 100 + 50
	else:
		st -= 10
	if end % 100 >= 50:
		end = end + 100 - 50
	else:
		end += 10
	schedules.append((st, end))
schedules.sort()
````

* 일정을 하나씩 받으면서,
  * 주어진 문제에 따라 시작 시간 10분전부터, 종료시간 10분후까지 불가능하므로
  * 조건을 계산 한 후 일정표 리스트에 추가, 정렬한다.

````python
ans = 0
time = 1000
for st, end in schedules:
	if time < st:
		ans = max(ans, get_time_diff(time, st))
	if time < end:
		time = end
else:
	if time < 2200:
		ans = max(ans, get_time_diff(time, 2200))
````

* 스위핑 알고리즘은 간단하게 구현할 수 있다.
* 시작 시간 1000부터 시작하여
  * 일정의 시작, 끝시간을 하나씩 확인하고,
  * 지금 가리키고 있는 시간과 다음 시작 시간 사이 시간이 있다면 정답이 될 수 있는지 확인,
  * 지금 가리키고 있는 시간보다 다름 종료 시간이 더 늦다면 가리키는 시간을 변경한다.


(BOJ2594


O

# (BOJ2641 다각형 그리기

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/2641
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/2000/2600/2641.py)

## 문제 설명

* 구현을 통하여 각 모양들이 같은지 확인해야 하는 문제처럼 보이지만, 수열이 주어졌을 때,  해당수열의 변환으로 만들어질 수 있는지 확인하면 된다.
* 변환은 수열을 회전하며 확인하면 되는데, 반대 방향으로도 구현 가능한지 확인해야 한다.

## 문제 풀이

````python
length = II()
target = list(MIIS())
ans = []
for _ in range(II()):
	line = list(MIIS())
	if check(length, target, line):
		ans.append(line)
print(len(ans))
for line in ans:
	print(*line)
````

* 기본적인 문제 풀이 코드
* 목표 수열 target과 같은 다각형을 만들 수 있는 수열을 저장하는 ans 리스트를 선언
  * 입력을 한줄씩 받으며, 각 수열이 같은 다각형을 만들 수 있는지 확인한다.

````python
def check(length: int, target: list, line: list) -> bool:
    def get_reverse_line(line: list) -> list:
        reverse_table = {1: 3, 2: 4, 3: 1, 4: 2}
        line.reverse()
        for idx, x in enumerate(line):
            line[idx] = reverse_table[x]
        return line

    for _ in range(length):
        if target == line:
            return True
        line = line[1:] + [line[0]]
    line = get_reverse_line(line)
    for _ in range(length):
        if target == line:
            return True
        line = line[1:] + [line[0]]
    return False
````

* 각 다각형이 같은지 두가지 방향으로 확인한다.
  * 우선, 입력으로 주어진 방향으로 회전하며 확인하고,
  * 거꾸로 그려갔을 때 가능한지 확인한다.
* 거꾸로 그려갈 때는 이동 방향이 반대로 되기 때문에 `get_reverse_line()`함수를 활용하여 새로운 리스트를 생성한다.


(BOJ2641


# (BOJ3665 최종 순위

* tags : [(algorithm](../%28algorithm.md) - *(topological sort*
* 문제 링크 : https://www.acmicpc.net/problem/3655
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/3000/3600/3665.py)

## 문제 설명

* 루트로부터 자식이 1개만 존재하는 트리에서, 특정 점들의 상대적 위치가 변경되었을 때, 똑같이 루트로부터 자식이 1개만 존재하는 트리가 될 수 있는지 확인하는 문제이다.
* 모든 점들의 상대적 위치를 저장하고, 순서가 변경된 경우, 따로 저장하여 확인한다.

## 문제 풀이

````python
N = II()
grades = list(MIIS())
M = II()
changed_grades = set(tuple(MIIS()) for _ in range(M))

teams = [[] for _ in range(N + 1)]
teams_before = [0] * (N + 1)
for i in range(N):
	for j in range(i + 1, N):
		a, b = grades[i], grades[j]
		if (a, b) in changed_grades or (b, a) in changed_grades:
			a, b = b, a
		teams[a].append(b)
		teams_before[b] += 1
````

* 입력을 먼저 처리한다.
* teams에는 더 낮은 순위의 팀들을 저장하고, teams_before에는 더 높은 순위의 팀의 수를 저장한다.
* 모든 팀 사이 상대 순위를 저장하기 위한 for문 순회를 하고, 만약 두 팀 쌍의 순위 순서가 변경되었다면, 순서를 변경시켜 적용한다.

````python
queue = deque([])
for i in range(1, N + 1):
	if not teams_before[i]:
		queue.append((i))
if not queue:
	print("IMPOSSIBLE")
	continue
ans = []
while queue and len(ans) < N:
	if len(queue) >= 2:
		break
	x = queue.popleft()
	ans.append(x)
	for y in teams[x]:
		teams_before[y] -= 1
		if not teams_before[y]:
			queue.append(y)
		elif teams_before[y] < 0:
			break
	else:
		continue
	break
if len(ans) == N:
	print(*ans)
else:
	print("IMPOSSIBLE")
````

* 문제에서 원하는 ?가 나오는 결과는 존재하지 않을 것 같아 제외했다.
* 먼저 가장 높은 등수의 팀을 찾고, queue에 추가한다.
  * 이 문제는 항상 한 팀만 queue에 들어 있어야 하므로 stack을 쓰거나 하나의 변수만 활용해도 문제 없을 것으로 보인다.
  * 만약 queue에 여러 개의 값이 있다면 트리가 아니게 되어 순서를 판단할 수 없다.


(BOJ3665


# (BOJ4354 문자열 제곱

* tags : [(algorithm](../%28algorithm.md) - *(KMP*
* 문제 링크 : https://www.acmicpc.net/problem/4354
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/4000/4300/4354.py)

## 문제 설명

* 부분 문자열 중에서 부분 문자열의 반복만으로 원래 문자열을 만들수 있는지, 만들 수 있다면 부분 문자열의 최소 크기를 찾아야 하는 문제
* 문제에서는 문자열 제곱이라 표현했지만, 실제로는 문자열을 뒤에 이어 붙이는 연산을 원한다.
* solved.ac 난이도, KMP가 표시되어 있지만, Python일반적인 문자열 연산으로도 해결할 수 있다. 

## 문제 풀이

### KMP

````python
while True:
	seq = input().strip()
	if seq == ".":
		break
	len_seq = len(seq)
	idx = 0
	check = [0] * len_seq
	for i in range(1, len_seq):
		while idx and seq[idx] != seq[i]:
			idx = check[idx - 1]
		if seq[idx] == seq[i]:
			idx += 1
			check[i] = idx
	max_len = len_seq - check[-1]
	if len_seq % max_len:
		print(1)
	else:
		print(len_seq // max_len)
````

* KMP를 활용한 풀이
* 문자열 길이의 패턴 확인용 리스트와 패턴을 확인하기 위한 인덱스를 선언하고,
* 문자열을 처음부터 확인하며 접두어와 접미어가 같은 위치를 표시한다.
* 마지막 출력은 가능한 최대 길이를 구한 뒤, 정답을 출력한다.

### 문자열 연산

````python
while True:
	seq = input().strip()
	if seq == ".":
		break
	len_seq = len(seq)
	for i in range(1, len_seq + 1):
		if len_seq % i:
			continue
		target = seq[:i]
		if target * (len_seq // i) == seq:
			print(len_seq // i)
			break
````

* 앞에서부터 문자열 길이를 하나씩 늘려가며 해당 문자열의 반복만으로 문자열을 만들어 낼 수 있는지 확인한다.


(BOJ4354


# (BOJ5525 IOIOI

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/5525
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/5000/5500/5525.py)

## 문제 설명

* 문자열을 순회하며 특정 패턴을 찾는 문제
* 문자열 길이가 최대 1,000,000이므로 $O(N^2)$으로 탐색하면 시간초과가 날 것이다.
* 다행히도 패턴이 간단하여 $O(N)$탐색으로 가능하다
  * 우선 가장 긴 $P_N$문자열을 탐색하고,
  * 해당 문자열에서 n길이의 문자열의 갯수를 확인한다.

## 문제 풀이

````python
n, m = int(input()), int(input())
s = str(input().strip())

count = 0
left, right = -1, -1
idx = 0
while True:
	if idx == m:
		count += get_count(n, left, right)
		break
	if left == right:
		if s[idx] == "I":
			left = idx
		idx += 1
	else:
		if idx == m - 1:
			idx += 1
		elif s[idx : idx + 2] == "OI":
			right = idx + 1
			idx += 2
		else:
			count += get_count(n, left, right)
			left = right = idx - 1
print(count)
````

* 지금 탐색하는 idx와 탐색하는 $P_N$문자열 시작, 끝을 left, right로 두어 탐색한다.
  * 만약 지금 문자열을 탐색하는 상태가 아니고, I를 만다면 left를 표시한다.
  * 탐색중이고 OI를 만나면 idx, right를 이동하여 문자열을 확장한다.

````python
def get_count(N: int, left: int, right: int) -> int:
    o_count = (right - left) // 2
    if o_count < N:
        return 0
    return o_count - N + 1
````

* 특정 길이 문자열의 갯수는,
  * O의 갯수를 먼저 확인하고,
  * 가능한 문자열의 갯수를 반환한다.


(BOJ5525


# (BOJ6322 직각 삼각형의 두 변

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/6322
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/6000/6300/6322.py)
  * [Go](https://github.com/mintropy/PS/blob/master/BAEKJOON/Golang/6000/6300/6322.go)

## 문제 설명

* 삼각형의 두 변이 주어졌을 때, 나머지 한 변의 길이를 구해야 한다.
  * 다만, 각 변의 위치를 고정시켰기 때문에 많은 경우의 수를 탐색할 필요가 없고
  * 출력에만 주의를 기울이면 되는 문제이다.

## 문제 풀이

## Python

````python
triangle_num = 1
ans = []
while True:
	a, b, c = map(int, input().split())
	if a == b == c == 0:
		break
	tmp = f"Triangle #{triangle_num}\n"
	triangle_num += 1
	if c == -1:
		tmp += "c = %.3f\n" % ((a**2 + b**2) ** 0.5)
	elif a == -1:
		if b >= c:
			tmp += "Impossible.\n"
		else:
			tmp += "a = %.3f\n" % ((c**2 - b**2) ** 0.5)
	elif b == -1:
		if a >= c:
			tmp += "Impossible.\n"
		else:
			tmp += "b = %.3f\n" % ((c**2 - a**2) ** 0.5)
	ans.append(tmp)
print("\n".join(ans))
````

* ans리스트에 모든 정답을 넣은 후 한번에 출력했다.
* while문 반복하며 종료조건을 확인하고,
* 먼저 출력 첫줄과 입력 번호를 작업했다.
* 그 다음 입력을 주어진 조건에 따라 구분하여 확인하는데,
  * c를 구해야 한다면 다른 두 변의 제곱을 더한 후 제곱근을 출력하고,
  * a 또는 b를 구하는 경우
    * c가 최대 길이 변이 아니면 불가능하므로 Impossible. 출력
    * 아니라면 피타고라스 정리를 활용하여 출력한다.
  * 그리고 각 길이는 소수점 3자리까지 출력한다.

````python
print(f"a = {a: .3f}")
````

* 위의 코드에서 f-string과 문자열 포매팅을 복합적으로 사용했다.
* 처음에는 모든 출력을 위롸 같이 f-string으로 했는데, 출력 형태가 잘못되었다고 여러차례 오답을 받았다.
* 정확히 어떤 부분이 문제인지는 모르겠지만, 다른 풀이에서도 f-stirng을 사용 한 것을 찾지 못하여 문자열 포매팅 부분에서 추가적인 수정을 하지 않았다.

## Go

````go
end := [3]int{0, 0, 0}
triangleNum := 1
for {
	nums := nextInts()
	if nums == end {
		break
	}
	fmt.Fprintf(wr, "Triangle #%d\n", triangleNum)
	triangleNum++
	if nums[2] == -1 {
		fmt.Fprintf(wr, "c = %.3f\n", math.Sqrt(IntPow(nums[0])+IntPow(nums[1])))
	} else if nums[0] == -1 {
		if nums[1] >= nums[2] {
			fmt.Fprint(wr, "Impossible.\n")
		} else {
			fmt.Fprintf(wr, "a = %.3f\n", math.Sqrt(IntPow(nums[2])-IntPow(nums[1])))
		}
	} else if nums[1] == -1 {
		if nums[0] >= nums[2] {
			fmt.Fprint(wr, "Impossible.\n")
		} else {
			fmt.Fprintf(wr, "b = %.3f\n", math.Sqrt(IntPow(nums[2])-IntPow(nums[0])))
		}
	}
	fmt.Fprint(wr, "\n")
}
````

* for 문으로 무한 반복문을 구성하고, `fmt.Fprintf()`를 사용하여 문자열 포매팅 출력을 했다.

````go
func IntPow(x int) float64 {
	return float64(x * x)
}
````

* 제곱에는 위의 함수를 정의하여 활용했다.
  * 기본 정수형 제곱을 위한 함수가 없고,
  * 정수의 제곱을 실수로 활용해야 하기 때문에,
  * 정수를 받아 실수를 반환하는 함수로 만들었다.


(BOJ6322


# (BOJ6439 교차

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/6439
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/6000/6400/6439.py)

## 문제 설명

* 선분 교차 판별 문제인데, 사각형 내부에 있는지도 판별해야한다.
  * 선분 교차는 총 4번을 진행하면 되고
  * 사각형 내부에 있는지 확인할 때, 문제에서 지나가듯이 언급한 ‘변수명은 우연의 일치’ 부분을생각하며 풀어야 한다.

## 문제 풀이

````python
x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split())
A, B = (x1, y1), (x2, y2)
if A > B:
	A, B = B, A
X, Y, Z, W = (x3, y3), (x3, y4), (x4, y4), (x4, y3)
if check_inside(A, B, Y, W):
	print("T")
	continue
````

* 조금 다른 방식으로 풀어낼 수 있는데, 문제를 조금 착각하여 풀이가 그렇게 예쁘지는 않은 것 같다.
* 우선 선분의 왼쪽 아래, 오른쪽 위 점으로 각각 A, B로 선언했다.
* 그리고 사각형의 네 점을 구한뒤, 사각형 내부에 있는지 확인한다.

````python
def check_inside(A: Point, B: Point, LB: Point, RT: Point) -> bool:
    xl, xr = min(LB[0], RT[0]), max(LB[0], RT[0])
    yb, yt = min(LB[1], RT[1]), max(LB[1], RT[1])
    if xl <= A[0] <= xr and yb <= A[1] <= yt:
        if xl <= B[0] <= xr and yb <= B[1] <= yt:
            return True
    return False
````

* 사각형 내부에 선분이 있는지 확인하는 함수
* 여기서, 변수명은 우연의 일치라는 부분을 고려해야 하는데, bottom, top과 같은 변수가 사각형의 아래, 위의 부분은 나타내지 않을 수 있다.
  * 그래서 양 끝 두점을 가져와 x, y좌표 각각을 기준으로 왼쪽과 오른쪽, 위와 아래를 min, max함수로 구하고,
  * 선분의 두 끝점이 내부에 속하는지 확인한다.

````python
for C, D in ((Y, X), (Y, Z), (Z, W), (X, W)):
	if C > D:
		C, D = D, C
	if chceck_line(A, B, C, D):
		print("T")
		break
else:
	print("F")
````

* 선분 교차 판별을 위해서 for문을 순회하고
  * 만약 교차하는 경우를 발견하면 T출력 후 break, 
  * 아니면 for문을 모두 순회 후 F출력

````python
def chceck_line(A: Point, B: Point, C: Point, D: Point) -> bool:
    tmp1 = get_ccw(A, B, C) * get_ccw(A, B, D)
    tmp2 = get_ccw(C, D, A) * get_ccw(C, D, B)
    if not tmp1 and not tmp2:
        if A <= D and B >= C:
            return True
        return False
    if tmp1 <= 0 and tmp2 <= 0:
        return True
    return False
````

* 선분 교차 판별 함수는 다음과 같이 구했는데,
* 우선 ccw값들을 구하여 곱한 후 연산 준비를 하고,
  * 경우의 따라 분류하여 교차하는지 아닌지를 반환한다.


(BOJ6439


# (BOJ9019 DSLR

* tags : [(algorithm](../%28algorithm.md) - *(BFS*
* 문제 링크 : https://www.acmicpc.net/problem/9019
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/9000/9000/9019.py)

## 문제 설명

* 하나의 숫자에서 시작해서 주어진 연산에 따라 가장 적은 연산을 찾는다.
* 문제에서는 각 숫자로 연산 하는 것처럼 말하는데, 
  * 실제로는 4자리를 기준으로 연산해야 하는 듯 하다.
  * 만약 5를 연산하면 실제로는 0005를 기준으로 생각해야한다, 특히 L, R 연산일 때 그렇다.

## 문제 풀이

````python
A, B = map(int, input().split())
queue = deque([(A, "")])
check = [False] * 10001
while queue:
	x, now = queue.popleft()
	if x == B:
		print(now)
		break
	if check[x]:
		continue
	check[x] = True
	y = (x * 2) % 10000
	if not check[y]:
		queue.append((y, now + "D"))
	y = (x - 1) % 10000
	if not check[y]:
		queue.append((y, now + "S"))
	y = rotate_num(x, True)
	if not check[y]:
		queue.append((y, now + "L"))
	y = rotate_num(x, False)
	if not check[y]:
		queue.append((y, now + "R"))
````

* 두 수를 입력 받고,
  * A에서 시작하여 BFS로 탐색한다.
* D, L 연산은 크게 신경 쓸 필요 없지만, L, R 연산은 조금은 주의할 필요가 있다.

````python
def rotate_num(x: int, left: bool) -> int:
    x = str(x).zfill(4)
    if left:
        x = x[1:] + x[0]
    else:
        x = x[-1] + x[:-1]
    return int(x)
````

* L, R 연산은 위의 함수로 처리했고,
  * 문자열로 연산하여 처리했다.


(BOJ9019


# (백준 1045 도로

* tags :  [(algorithm](../%28algorithm.md) *(MSP*
* 문제 링크 : https://www.acmicpc.net/problem/1045
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/1000/1400/1045.py)

## 문제 설명

* 기본적으로 MSP를 찾아야 하는 문제
  * 추가적으로 원하는 수만큼 도로를 더 찾아야 한다.
* MSP를 구하는 다양한 방법 모두 적용할 수 있을 것 같고, union-find를 활용했다.
* 각 도로를 탐색하면서 연결하지 않은 도로는 따로 저장하여 원하는 수의 도로를 맞추기 위해 도로를 추가한다.

## 문제 풀이

````python
roads_sets = []
unused = []
parents = list(range(N))
for i in range(N):
	for j in range(i + 1, N):
		if roads[i][j] == "N":
			continue
		x, y = find_parent(parents, i), find_parent(parents, j)
		if x == y:
			unused.append((i, j))
			continue
		roads_sets.append((i, j))
		parents = union_parents(parents, x, y)
````

* 인접 행렬에서 도로를 찾고,  연결, 쓰지 않는 도로 저장까지 한번에 진행했다.
* `roads_sets`은 MSP를 만족하기 위한 도로를 저장했고, MSP를 만드는 조건에 맞지 않는 도로는 `unused`에 저장했다.
* 도로 탐색은 문제 조건에 따라 (A, B)일 때 A \< B인 조건으로 탐색했고,
  * 이후 union-find를 진행하며 union 조건에 맞으면 `roads_sets`에, 아니면 `unused`에 저장

````python
if len(roads_sets) < N - 1 or len(roads_sets + unused) < M:
	print(-1)
else:
	ans = [0] * N
	for x, y in roads_sets:
		ans[x] += 1
		ans[y] += 1
	for i in range(M - (N - 1)):
		x, y = unused[i]
		ans[x] += 1
		ans[y] += 1
````

* 모든 도시를 연결하지 못하거나, 도로의 개수가 M개가 안되면 -1을 출력
* 아니라면 우선 MSP를 이루는 도로를 추가하고,  사용하지 않는 도로들 중 먼저 저장한 것 순서대로 추가한다.
  * 문제 조건에서 도로의 우선순위를 만족시키기 위함.


(백준 1045 도로


# (백준 1075 나누기

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/1075
* 문제 풀이
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/1000/1000/1075.py)
  * [Go](https://github.com/mintropy/PS/blob/master/BAEKJOON/go/1000/1000/1075.go)
  * [Node](https://github.com/mintropy/PS/blob/master/BAEKJOON/Node/1000/1000/1075.js)

## 문제 설명

* 나누기 몫, 나머지 연산을 활용하는 문제

## 문제 풀이

````python
_N = (N // 100) * 100
if _N % F:
	print(str(_N + (F - _N % F))[-2:])
else:
	print("00")
````

* 수에서 뒤의 두자리, 즉 십의 자리와 일의 자리에만 관심이 있기 때문에 100으 나눈 몫을 구한 후 100을 곱한다.
* 이 때 F로 나누어 떨어지는 수를 구해야 하는데, 백의 자리는 바뀌면 안된다.
  * 따라서 위에서 구한 수, 즉 일의 자리수, 십의 자리 수만 변경되는 경우에서 최솟값을 찾아야 한다.
* 만약 N = 1000, F = 3이라고 하면, \_N = 1000이 되고
  * 1000 이상 3의 배수 중 최소 숫자는 1002가 된다.
  * 질문은 이 수를 어떻게 구할 것인가?
  * 1000을 3으로 나눈 나머지는 1이고, 이 말은 1000보다 큰 3의 배수를 얻기 위해서는 2를 더해주면 된다.
  * 이후 십의자리, 일의 자리를 출력.

````go
func main() {
	N, F := nextInt(), nextInt()
	_N := int(N/100) * 100
	if _N%F == 0 {
		fmt.Fprint(wr, "00")
	} else {
		ans := strconv.Itoa(_N + (F - _N%F))
		l := len(ans)
		fmt.Fprint(wr, ans[l-2:])
	}
}
````

* Python 코드와 차이점은 형변환을 위해 새로운 변수(ans)를 지정하는것과, 음수 인덱싱이 불가능하여 길이를 구한 뒤 슬라이싱 했다.

````js
const _N = parseInt(N / 100) * 100

if (_N % F) {
  const ans = String(_N + (F - _N % F))
  const l = ans.length
  console.log(ans.slice(l-2))
} else {
  console.log("00")
}
````

* Go와 풀이가 거의 유사하다.
* 다만 문자열 슬라이싱이 대괄호로 할 수 없고, `.slice()` 메서드를 활용해야한다.


(백준 1075 나누기


# (백준 12834 주간 미팅

* tags : [(algorithm](../%28algorithm.md) - *(BFS*
* 문제 링크 : https://www.acmicpc.net/problem/12834
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/12000/12800/12834.py)

## 문제 설명

* 각 참여자들이 두 지점까지의 최단 거리의 합의 합을 구해야한다.
  * 조금 풀어서 다시 설명하면,
  * 각 참여자 위치에서 두 지점까지의 최단 거리의 합을 구해야 하고,
  * 이 거리의 합을 모두 합하여 출력하면된다.
* 각 지점에서 시작해서 목적지 두 지점까지 거리를 구해도 되지만,
  * 탐색이 많아지면 많은 시간이 걸릴 수 있다.
* 대신, 목적지로 하는 두 지점에서 시작하여, 다른 모든 지점까지 거리를 구하고, 각 참여자는 두 위치까지 이미 구한 거리를 바로 가져와서 사용하면 된다.

## 문제 풀이

````Python

def search(V: int, start: int, roads: Road) -> list[int]:
    dist = [-1] * (V + 1)
    queue = deque([(start, 0)])
    while queue:
        x, d = queue.popleft()
        if -1 != dist[x] <= d:
            continue
        dist[x] = d
        for y, _d in roads[x]:
            if -1 == dist[y] or dist[y] > d + _d:
                queue.append((y, d + _d))
    return dist
````

* KIST와 씨알푸드에서 모든 점까지 위치를 구해야하는데, 완전히 같은 방식을 사용한다.
  * 그래서 BFS를 2회 실행하는 대신, 하나의 함수를 생성하고, `start`변수만 처리하여 구했다.
* 또한, 거리를 구할 수 없으면 -1이라 하였는데, 이후 if문을 통하여 처리하는 대신 거리를 -1로 초기화하여 구했다.
  * 함수 내부 두개의 if문에서 거리에 대한 조건이 조금 까다로워 지지만,
  * 추가적인 리스트 순회 또는 출력에서 if문을 사용하지 않아도 된다.
  * 메모리 측면에서는 조금 더 이점이 있을 것 같고, 시간은 비슷할것으로 보인다.

````python
ans = sum([from_kist[h] + from_ssial[h] for h in teammates])
````

* 출력 값은 한 줄로 빠르게 구했다.


(백준 12834 주간 미팅


# (백준 1417 국회의원 선거

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/1417
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/1000/1400/1417.py)
  * [Go](https://github.com/mintropy/PS/blob/master/BAEKJOON/go/1000/1400/1417.go)
  * [Node.js](https://github.com/mintropy/PS/blob/master/BAEKJOON/Node/1000/1400/1417.js)

## 문제 설명

* 우선순위 큐를 사용하면 더욱 쉽게 해결할 수 있을 것 같은데, Python을 제외한 언어로 풀어보기 위해 그리디하게 접근했다.

## 문제 풀이

* 기본적인 구조는 다음과 같다.
* 표는 최대 100표이므로, 101 길이 리스트를 만들어서 각 표를 받는 후보의 수를 기록한다.
* 이후 다솜이가 받은 표가 최대가 될 때까지, 다른 후보의 표를 1개씩 가져간다.

### Python

````python
votes = [0] * 101
for _ in range(N - 1):
	v = II()
	votes[v] += 1
````

* 101길이 배열에서 특정 표를 받은 후보들 만큼 표시한다.

````python
for i in range(100, 0, -1):
	if not votes[i]:
		continue
	while votes[i]:
		if dasom > i:
			break
		dasom += 1
		votes[i] -= 1
		votes[i - 1] += 1
		answer += 1
	if (not votes[i] and dasom >= i) or dasom > i:
		break
````

* 100표부터 1표까지 순서대로 확인한다.
  * 만약 해당 표만큼 받은 사람이 없다면 넘어간다.
  * 아니라면 1표씩 다솜이의 표로 옮기는 과정을 하는데,
    * i표 만큼 얻은 사람이 1명 줄면 i-1표를 얻은 사람을 늘리고,
    * 정답으로 하나 더한다.
* 다솜이의 표가 지속적으로 변하기 때문에 for문의 마지막마다 다솜이의 표를 확인하여 마무리한다.

### Go & Node

````go
dasom++
votes[i]--
votes[i-1]++
answer++
````

* 전체적인 코드는 같은데, `+=1` 대신 `++`연산으로 대체할 수 있는 부분 말고 거의 같다.


(백준 1417 국회의원 선거


# (백준 14428 수열과 쿼리 16

* tags : [(algorithm](../%28algorithm.md) - *(segment tree*
* 문제 링크 : https://www.acmicpc.net/problem/14428
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/14000/14428.py)

## 문제 설명

* 전형적인 세그먼트 트리 문제
* 각 구간별 최솟값의 **인덱스**를 저장하고, 쿼리의 구간의 최솟값 인덱스를 출력
  * 최솟값이 여러개인 경우, 가장 작은 인덱스를 출력

## 문제 풀이

````python
def init(self) -> None:
	self.find_idx(1, 1, self.N)
	for idx, x in enumerate(self.idx):
		self.tree[x] = idx
	self.init_tree()

def find_idx(self, node: int, left: int, right: int) -> None:
	if left >= right:
		self.idx[left] = node
		return
	mid = (left + right) // 2
	self.find_idx(node * 2, left, mid)
	self.find_idx(node * 2 + 1, mid + 1, right)

def init_tree(self) -> None:
	for i in range(len(self.tree) - 1, 0, -1):
		if i * 2 + 1 > len(self.tree):
			continue
		left = self.seq[self.tree[i * 2]]
		right = self.seq[self.tree[i * 2 + 1]]
		if not left * right:
			continue
		if left <= right:
			self.tree[i] = self.tree[i * 2]
		else:
			self.tree[i] = self.tree[i * 2 + 1]
````

* 세그먼트 트리 초기화
* `init()`메서드를 사용하여 초기화하고, `find_idx()`, `init_tree()`메서드 호출
  * `find_idx()`는 세그먼트 트리와 수열의 인덱스를 저장하여 더욱 빠르게 작동할 수 있도록 함
  * `init_tree()`를 사용하여 세그먼트 트리 초기화
* 초기화할 때, 값을 찾을 때, 갱신할 때 최솟값이 여러개이면 가장 작은 인덱스를 가져오는 부분을 주의하여 작성


(백준 14428 수열과 쿼리 16


# (백준 14725 개미굴

* tags : [(algorithm](../%28algorithm.md) - *(trie*
* 문제 링크 : https://www.acmicpc.net/problem/14725
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/14000/14700/14725.py)

## 문제 설명

* 각 점이 문자열로 이루어진 트리를 생성하고, 그 트리를 구조화하여 출력해야 한다.
* 하지만, 각 점을 이루는 문자열이 유일하지 않아 트라이 구조를 잘 만들어야 한다.

## 문제 풀이

````python
trie = defaultdict(set)
for _ in range(N):
	ants = input().strip().split()
	m = int(ants[0])
	parent = f"{ants[1]}"
	trie[""].add(parent)
	for i in range(m - 1):
		x, y = ants[1 + i], ants[2 + i]
		trie[parent].add(y)
		parent += f" {y}"
````

* 트라이 구조를 `defaultdict`으로 설정했다.
  * 각 문자열이 있는지 확인하는 조건문 등을 구현하는게 간단하지는 않을 것이라 생각했다.
  * 트라이 구조를 이루기 위해 부모로부터 각 노드를 연결하여  부모-자식 관계를 설정했다.

````python
def search(depth: int, parent: str) -> str:
    global trie
    if not trie[parent]:
        return ""
    ans = ""
    for x in sorted(trie[parent]):
        ans += f"{'-' * (2 * depth)}{x}\n"
        child = f"{x}" if not parent else f"{parent} {x}"
        ans += f"{search(depth + 1, child)}"
    return ans
````

* 탐색은 for문 또는 while문으로도 가능하지만, 백트레킹으로 했다.
  * key를 기반으로 자식을 오름차순 정렬하여 탐색했다.
  * 함수의 파라미터로 깊이를 가져감으로써, 출력 구조세어 대쉬의 수를 정하였다.


(백준 14725 개미굴


# (백준 16434 드래곤 앤 던전

* tags : [(algorithm](../%28algorithm.md) - *(binary search* - *(simulate*
* 문제 링크 : https://www.acmicpc.net/problem/16434
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/16000/16400/16434.py)

## 문제 설명

* 조금 독특한 매개변수 탐색 문제인데, 매개변수 탐색 과정을 활용하면 단순한 구현 방식으로 해결할 수 있다.
* 매개변수 탐색에서 최댓값 설정을 하며 몇 차례 틀렸는데, 최댓값 부분은 아직 잘 이해가지 않는다.

## 문제 풀이

### 매개변수 탐색

````python
def bin_search(H: int, dungeons: list[tuple[int]]) -> int:
    left, right = 0, 10**17
    ans = 0
    while left <= right:
        mid = (left + right) // 2
        if simulate(mid, H, dungeons):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return 
````

* right를 10^17으로 설정했을 때 통과했다.
  * 10^12 부터 10^16까지 순차적으로 계산해보았고, 10^17에서야 통과했다.
  * 정확한 계산은 잘 모르겠지만, 생각보다 큰 수로 설정해야 했다.

````python
def simulate(health: int, attack: int, dungeons: list[tuple[int]]) -> bool:
    max_health = health
    for t, a, h in dungeons:
        if t == 1:
            turn = h // attack if h % attack == 0 else h // attack + 1
            if health - a * (turn - 1) <= 0:
                break
            health -= a * (turn - 1)
        else:
            attack += a
            health = min(health + h, max_health)
    else:
        return True
    return False
````

* 가능한지 확인하기 위해, 체력을 기준으로 모든 턴을 실행하며 확인했다.

### 구현

````python
HP = 0
answer = 0
for _ in range(N):
	t, a, h = MIIS()
	if t == 1:
		turn = h // H if h % H == 0 else h // H + 1
		HP += a * (turn - 1)
		answer = max(answer, HP)
	else:
		H += a
		HP = max(HP - h, 0)
print(answer + 1)
````

* 바로 위의 `simulate()`함수를 확장하여, 필요한 체력을 역으로 계산하였고, 더욱 빠르고 편하게 정답을 구할 수 있다.


(백준 16434 드래곤 앤 던전


# (백준 2104 부분배열 고르기

* tags : [(algorithm](../%28algorithm.md) - *(segment tree*
* 문제 링크 : https://www.acmicpc.net/problem/2104
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/2000/2100/2104.py)

## 문제 설명

* 모든 구간을 확인하여 값을 도출해야하고, 각 구간별 합과 최솟값을 찾아야 한다.
* 당연히 완전 탐색 등의 방식은 시간초과가 나게 될 것이고, 다른 방식을 고민해야 한다.

## 문제 풀이

### segment tree

* 처음에는 세그먼트 트리를 활용해서 해결했다.
  * 세그먼트 트리는 합을 구성하는 트리, 최솟값의 인덱스를 가지는 트리 두개로 구성했다.

````python
def __init__(self, N: int, seq: list) -> None:
	self.N = N
	self.seq = [0] + seq
	self.sum_tree = [0] * (1 << ceil(log2(N) + 1))
	self.min_tree = [0] * (1 << ceil(log2(N) + 1))
	self.init(1, 1, N)

def init(self, node: int, start: int, end: int) -> None:
	if start == end:
		self.sum_tree[node] = self.seq[start]
		self.min_tree[node] = start
		return
	mid = (start + end) // 2
	self.init(node * 2, start, mid)
	self.init(node * 2 + 1, mid + 1, end)
	self.sum_tree[node] = self.sum_tree[node * 2] + self.sum_tree[node * 2 + 1]
	if self.seq[self.min_tree[node * 2]] < self.seq[self.min_tree[node * 2 + 1]]:
		self.min_tree[node] = self.min_tree[node * 2]
	else:
		self.min_tree[node] = self.min_tree[node * 2 + 1]
````

* 다음과 같이 클래스 초기화할 때 sum_tree, min_tree를 선언하고, `init()`메서드를 활용해서 트리를 초기화한다.
  * 한번에 두개의 트리를 모두 초기화하여 코드가 길어지는 문제가 있지만, 한 번의 탐색으로 가능해서 아마도 시간적인 이점이 있을 것 같다.

````python
def solve(self, start: int, end: int) -> int:
	if start == end:
		return self.seq[start] * self.seq[start]
	values = self.get_values(1, 1, self.N, start, end)
	if values[1] == -1:
		return 0
	sums = [
		values[0] * self.seq[values[1]],
		self.solve(start, values[1] - 1),
		self.solve(values[1] + 1, end),
	]
	return max(sums)
````

* 마지막으로 `solve()`메서드를 활용하여 해결한다.
  * 여기서는 분할 정복을 활용했는데, 각 구간별 최솟값 인덱스 위치를 찾고, 해당 인덱스 기준 왼쪽, 오른쪽으로 나누어 탐색했다.

### monotone stack

* 그런데 풀이를 제출하고 보니 새로운 방식의 풀이가 보였고, 모노톤 스택을 활용했다는것을 알게 되었다.
* 모노톤 스택은 하나의 배열을 O(N)의 시간 복잡도로 배열을 오름차순, 내림차순을 유지할 수 있다.

````python
def solution(seq: tuple) -> int:
    stack = []
    answer = 0
    now = 0
    for x in seq:
        left = now
        while stack and x < stack[-1][0]:
            y, left = stack.pop()
            answer = max(answer, y * (now - left))
        stack.append((x, left))
        now += x
    return max(answer, *(x * (now - left) for x, left in stack))
````

* 코드는 간단하지만, 이해하기에는 시간이 조금 걸렸고, 나름대로 나만의 코드로 녹이는데도 시간이 걸렸다.
* 우선 now값을 통하여 누적합을 구현했고, 구간합을 구하는데 사용했다.
* 만약 스택이 비어있으면 수열의 지금 값과 누적합을 저장한다.
* 스택이 비어있지 않은 경우, 다음을 확인하며 진행한다.
  * 스택의 top에 저장된 값을 확인하여, 오름차순 조건이 안된다면 top의 값을 pop한다. 이 때 저장된 값과 지금 누적합을 활용하면 구간 누적합, 최솟값을 알 수 있고, 정답을 갱신한다.


(백준 2104 부분배열 고르기


# (백준 2224 명제 증명

* tags : [(algorithm](../%28algorithm.md) - *(floyd-warshall*
* 문제 링크 : https://www.acmicpc.net/problem/2224
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/2000/2200/2224.py)

## 문제 설명

* 명제의 각 조건이 알파벳 대소문자로만 이루어져있고, 명제의 순서도 정해져있다.
* 이를 각 조건 총 52개를 점으로, 각 명제를 그래프에서 선분으로 해석할 수 있다.

## 문제 풀이

* 들어가기 앞서 입력으로 주어지는 알파벳을 더 쉽게 다루기 위한 함수 두개를 먼저 소개하겠다.

````python
def ascii_to_index(x: int) -> int:
    if x < 97:
        return x - 65
    return x - (97 - 26)

def index_to_alp(x: int) -> str:
    if x < 26:
        return chr(x + 65)
    return chr(x + 97 - 26)
````

* 첫 번째 함수는 주어질 수 있는 최대 52개 문자, A를 인덱스 0으로, a를 인덱스 26으로 지정하는 함수이다.
* 두 번째 함수는 인덱스 형태로 저장한것을 해당 알파벳으로 변환하는 함수이다.

````python
for k in range(52):
	for i in range(52):
		for j in range(52):
			if propositions[i][k] and propositions[k][j]:
				propositions[i][j] = True
````

* 이후 탐색은 평범한 플로이드 와샬로 진행했고

````python
ans = []
for i in range(52):
	for j in range(52):
		if i != j and propositions[i][j]:
			x, y = index_to_alp(i), index_to_alp(j)
			ans.append(f"{x} => {y}")
````

* 출력을 위해 다시 순회하며 값을 저장하는데, `p => p`꼴을 피하기 위한 조건문이 필수로 들어가야한다.


(백준 2224 명제 증명


# (백준 22860 폴더 정리 (small)

* tags : [(algorithm](../%28algorithm.md) - *(trie*
* 문제 링크 : https://www.acmicpc.net/problem/22860
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/22000/22800/22860.py)

## 문제 설명

* 폴더, 파일을 구조화하는 문제
  * 각 폴더별 하위 폴더의 파일에 대한 쿼리를 해결해야 한다.
* 각 폴더 이름이 중복으로 나오지 않아서 [(백준 14725 개미굴](%28%EB%B0%B1%EC%A4%80%2014725%20%EA%B0%9C%EB%AF%B8%EA%B5%B4.md) 문제와는 다르게 트라이 구조의 각 노드 값을 신경쓸 필요가 없다.
  * 하지만 파일 이름은 중복으로 나올 수 있다.
  * 파일은 각 노드를 이루지 않아서 크게 신경 쓸 필요는 없지만, 각 폴더가 포함한 파일을 중복없이 세기 위하여 set을 활용했다.

## 문제 풀이

* Python 풀이를 dataclass를 활용했다.
  * trie구조를 클래스로 구현할 수 있지만, dataclass를 적용해보기위해 조금 독특하게 구성해보았다.

````python
@dataclass
class Directory:
    parent: str
    files_count: int = 0
    files: set = field(default_factory=set)

    def get_different_files_count(self) -> int:
        return len(list(self.files))
````

* dataclass는 각 노드를 이루도록 구성했고,
  * 인자로 부모, 각 폴더 이하에 속한 파일의 종류와 파일의 수를 기록했다.
* 또한 파일 이름을 set에 저장해두어, 서로다른 파일의 수를 출력하기 위한 메서드도 작성했다.

````python
def add_folder(F: str, parent: str, child: str) -> None:
    global directory, folder_to_directory
    directory[child] = Directory(parent=parent)
    folder_to_directory[F] = child

def add_file(folder_name: str, file_name: str) -> None:
    global directory
    directory[folder_name].files.add(file_name)
    directory[folder_name].files_count += 1
````

* 폴더 구조, 파일 구조를 수정하는 함수는 다음과 같다.
  * 폴더의 경우, 자식 폴더에서 부모 폴더를 지정해준다.
  * 파일의 경우 파일 추가 및 파일의 수를 추가한다.

````python
for _ in range(N + M):
	P, F, C = input().strip().split()
	if P == "main":
		if C == "0":
			add_file(parent_directory, F)
			folder_to_directory[F] = parent_directory
		else:
			child_directory = f"{parent_directory}/{F}"
			add_folder(F, parent_directory, child_directory)
	else:
		if C == "0":
			files.append((P, F))
		else:
			folders.append((P, F))
````

* 이 방식의 풀이는 한가지 단점이 있는데,  main폴더부터 하위 폴더로 입력되는것을 기준으로 작성했었다.
* 따라서 main폴더에 속하는 폴더 또는 파일만 우선 처리했다.
  * 만약 속한다면, 위의 두 함수를 활용해서 폴더 및 파일을 추가한다.
* main폴더가 부모가 아니라면 files, folders라는 deque를 미리 생성해두었고, 폴더, 파일만 구분하여 저장했다.
  * 각 폴더 및 파일은 main이 부모일때와 유사하게 처리했다.

````python
def update_files(folder_name: str, file_name: str) -> None:
    global directory
    while folder_name != "main":
        parent = directory[folder_name].parent
        directory[parent].files.add(file_name)
        directory[parent].files_count += 1
        folder_name = parent
````

* 각 파일을 추가할때는 위의 함수를 활용했다.
  * 해당 파일의 부모를 불러가며 파일 추가 및 파일 개수를 더했다.


(백준 22860 폴더 정리 (small)


# (백준 2476 주사위 게임

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/2476
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/2000/2400/2476.py)
  * [Go](https://github.com/mintropy/PS/blob/master/BAEKJOON/go/2000/2400/2476.go)
  * [Node.js](https://github.com/mintropy/PS/blob/master/BAEKJOON/Node/2000/2400/2476.js)

## 문제 설명

* [백준 2480 주사위 세개](https://www.acmicpc.net/problem/2480)와 거의 같지만, for문, if문이 하나씩 더 추가된 문제
* for문을 순회하며 각 입력 3개가 주어졌을 때, 값을 계산하고
  * 얻은 값 중에서 최댓값을 출력

## 문제 풀이

* 언어별 차이로  최댓값 구하기 정도만 살펴보면 좋을 것 같다.
* Python에서는 내장함수 `max()`를 활용하여 구할 수 있다.

````go
func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}
func main() {
	tmp = 100 * max(a, max(b, c))
}
````

* Go는 정수에 대하여 최댓값 함수가 있지만, 정수일때는 따로 함수를 만들어 구현하는것이 편하다.
* Node는 `Math.max()`를 활용해서 Python과 유사하게 구할 수 있다


(백준 2476 주사위 게임


# (백준 2613 숫자구슬

* tags : [(algorithm](../%28algorithm.md) - *(binary search*
* 문제 링크 : https://www.acmicpc.net/problem/2613
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/2000/2600/2613.py)

## 문제 설명

* 하나의 구간을 특정 갯수로 분할하는 문제
* 구간별 최소합을 구해야하는데, 그 범위가 넓어서 이분탐색을 활용해야한다.
* 그리고 두가지 유의사항이 있는데,
  * 각 구간에 넣을 수 있는 구슬 숫자와 합을 잘 확인해야 하고,
  * 모든 구간에 하나 이상의 구슬이 들어가야 한다.

## 문제 풀이

````python
left, right = 0, sum(beads)
max_bead = max(beads)
ans = right
beads_count = []
while left <= right:
	mid = (left + right) // 2
	if mid < max_bead:
		left = mid + 1
		continue
	counts = get_beads_counts(M, mid, beads)
	if counts:
		ans = mid
		beads_count = counts[::]
		right = mid - 1
	else:
		left = mid + 1
````

* 기본적인 이분탐색 구성은 다음과 같이 했다.
  * 우선, left값을 `max(beads)`로 설정했으면 더욱 좋았을 듯 하다.
* left, right값을 기준으로 mid값을 설정, 해당 갯수를 각 구간의 최솟값으로 설정할 수 있는지 확인한다.
* mid값으로 각 구간을 분할할 수 있는지는 아래와 같이 확인한다.

````python
counts = [0] * divide
idx = count = 0
sum_now = 0
for x in beads:
	if sum_now + x > max_sum:
		counts[idx] = count
		idx += 1
		count = 0
		sum_now = 0
	if idx == divide:
		return []
	sum_now += x
	count += 1
counts[idx] = count
left = idx
idx += 1
````

* 우선 원하는 구간으로 나누는 후, 앞에서부터 최대한 채워넣는다.
  * 구슬의 값을 하나씩 확인하며 구간합을 구하고, 
  * 구간합이 원하는 값 mid보다 커지기 전에 각 구간에 구슬 갯수를 입력한다.
  * 모두 순회하고 남은 값도 처리한다.

````python
while idx < divide:
	if counts[left] > 1:
		counts[left] -= 1
		counts[idx] += 1
		idx += 1
	else:
		left -= 1
````

* 각 구간에 구슬이 하나 이상 있어야 하는 조건을 해결하기 위해 이 부분을 작성했다.
  * 비어있는 위치마다 하나씩 구슬을 뒤로 밀어주는 방식으로 해결했다.


(백준 2613 숫자구슬


# (백준 2693 N번째 큰 수

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/2693
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/2000/2600/2693.py)
  * [Go](https://github.com/mintropy/PS/blob/master/BAEKJOON/go/2000/2600/2693.go)
  * [Node.js](https://github.com/mintropy/PS/blob/master/BAEKJOON/Node/2000/2600/2693.js)

## 문제 설명

* 정렬만 하면 되는 아주 간단한 문제이지만, Python만큼 정렬이 편리한 언어가 많지 않아 단순한 문제임에도 많이 고민했다.

## 문제 풀이

### Python

````python
for _ in range(int(input())):
	seq = sorted(map(int, input().split()))
	print(seq[7])
````

* 가장 간단하면서도, 가장 아름답게 표현할 수 있다고 생각한다.

### Go

````go
N := nextInt()
for i := 0; i < N; i++ {
	var seq []int
	for j := 0; j < 10; j++ {
		seq = append(seq, nextInt())
	}
	sort.Ints(seq)
	fmt.Fprintln(wr, seq[7])
}
````

* 정렬하는 방식을 다양하게 찾아보고 적용하는데 조금 시간이 걸렸다.
* `sort`에서 함수들을 제공하지만, 정렬 방식이나, 배열의 구성에 따라 다른 함수들도 제공되는 것 같다.

### Node.js

````js
const N = parseInt(input[0])
for (let i = 1; i <= N; i++) {
  let seq = input[i].split(" ").map(x => parseInt(x))
  seq.sort(function(x, y){return x - y})
  console.log(seq[7])
}
````

* 이 문제를 풀다가 JS의 정렬이 문자열 기준으로 되는 것을 다시 떠올렸다.
* 그래서 sort가 정수에도 작동되도록 작성하여 해결했다.


(백준 2693 N번째 큰 수


# (백준 2752 세수정렬

* tags : [(algorithm](../%28algorithm.md)
* 문제 링크 : https://www.acmicpc.net/problem/2752
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/2000/2700/2752.py)
  * [Go](https://github.com/mintropy/PS/blob/master/BAEKJOON/go/2000/2700/2752.go)
  * [Node.js](https://github.com/mintropy/PS/blob/master/BAEKJOON/Node/2000/2700/2752.js)

## 문제 설명

* 입력으로 주어진 세 숫자를 정렬 후 출력
  * 숫자가 3개만 주어지므로 if문만으로도 충분히 가능하지만, 정렬 함수를 활용했다.

## 문제 풀이

### Python

````python
print(*sorted(map(int, input().split())))
````

* 한줄의 매우 간결할 코드로 해결할 수 있음

### Go

````go
sort.Ints(nums)
for _, x := range nums {
	fmt.Fprint(wr, x, " ")
}
````

* `sort.Ints()`를 사용해서 정렬 후 출력

### Node.js

````js
let seq = input.split(" ").map(x => parseInt(x)).sort(function(x, y){return x - y})

console.log(seq.join(" "))
````

* 코드 길이나 편리함으로 생각하면 Python과 Go 중간쯤 느낌
  * `split().map()`을 활용해서 입력을 숫자 배열로 변경, 이후 `sort()`를 활용해서 정렬


(백준 2752 세수정렬


# (백준 4179 불!

* tags : [(algorithm](../%28algorithm.md) - *(BFS*
* 문제 링크 : https://www.acmicpc.net/problem/4179
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/4000/4100/4179.py)

## 문제 설명

* 불이 번지는 것, 지훈이가 이동하는 것을 동시에 처리하는 조금 번거로운 BFS문제
* 여기서, 불이 번지는 것을 먼저 처리하고, 지훈이의 이동은 불과 벽에 따라 정해지므로 이 순서만 생각하면 조금 쉽게 해결할 수 있다.

## 문제 풀이

````python
while fires:
	time, x, y = fires.popleft()
	if fire_time[x][y] >= 0:
		continue
	fire_time[x][y] = time
	for d in range(4):
		nx, ny = x + dx[d], y + dy[d]
		if 0 <= nx < R and 0 <= ny < C:
			if maze[nx][ny] != "#":
				fires.append((time + 1, nx, ny))
````

* 우선 불이 번지는 과정을 먼저 진행했다. 물론 불이 번지는것과 지훈이의 이동을 동시에 진행해도 좋지만, 이 방식이 조금은 편할 것 같아서 선택했다.
* 불은 각 위치별 어느 시간에 도착하는지 표시했다.

````python
while queue:
	time, x, y = queue.popleft()
	if x < 0 or x >= R or y < 0 or y >= C:
		ans = time
		break
	if -1 != fire_time[x][y] <= time or visited[x][y]:
		continue
	visited[x][y] = True
	for d in range(4):
		nx, ny = x + dx[d], y + dy[d]
		if 0 <= nx < R and 0 <= ny < C:
			if not visited[nx][ny] and maze[nx][ny] != "#":
				queue.append((time + 1, nx, ny))
		else:
			queue.append((time + 1, nx, ny))
````

* 지훈이의 이동은 세가지 조건을 확인하며 진행한다.
  * 첫 번째는 벽으로 이동할 수 없다.
  * 두 번째는 각 위치별 이동시간이 불이 번지기 전이여야 한다.
  * 세 번째는 범위를 벗어난 경우 탈출 성공으로 확인한다.
* 물론, 각 위치에서 방문확인을 해야 시간초과를 피할 수 있다.


(백준 4179 불!


# (백준 5547 일루미네이션

* tags : [(algorithm](../%28algorithm.md) - *(BFS*
* 문제 링크 : https://www.acmicpc.net/problem/5547
* 풀이 링크
  * [Python](https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/5000/5500/5547.py)

## 문제 설명

* BFS로 해결할 수 있는 문제이지만,  일반적인 사각형이 아니라 육각형 구조라서 고려해야할 부분이 있다.
* 또한, 모서리의 총 길이를 구해야 하는데,  각각의 6각형과 다른 6각형들의 위치에 따라 잘 처리해야 한다.

## 문제 풀이

````python
delta = [
	[(-1, 0), (0, 1), (1, 0), (1, -1), (0, -1), (-1, -1)],
	[(-1, 1), (0, 1), (1, 1), (1, 0), (0, -1), (-1, 0)],
]
````

* 우선 육각형 탐색은 다음과 같이 설정했다.
  * 두 개의 리스르토 구성한 것은 위치에 따라 탐색 방식이 조금씩 달라질 수 있기 때문이다.

````python
walls = (
	[[0] * (W + 2)] + [[0] + list(MIIS()) + [0] for _ in range(H)] + [[0] * (W + 2)]
)
````

* 탐색은 0으로 패딩을 하고, 건물이 아닌 부분을 탐색하며 건물과 만나는 부분만큼 벽의 개수를 더하였다.

````python
def count_walls(x: int, y: int) -> int:
    global walls, delta
    count = 0
    for dx, dy in delta[x % 2]:
        nx, ny = x + dx, y + dy
        if 0 <= nx <= H + 1 and 0 <= ny <= W + 1:
            if walls[nx][ny]:
                count += 1
    return count
````

* 비어 있는 공간일 때 주변에 건물이 있는지 확인하는 함수


(백준 5547 일루미네이션

(백준 1045 도로

(백준 1075 나누기

(백준 12834 주간 미팅

(백준 1417 국회의원 선거

(백준 14428 수열과 쿼리 16

(백준 14725 개미굴

(백준 16434 드래곤 앤 던전

(백준 2104 부분배열 고르기

(백준 2224 명제 증명

(백준 22860 폴더 정리 (small)

(백준 2476 주사위 게임

(백준 2613 숫자구슬

(백준 2693 N번째 큰 수

(백준 2752 세수정렬

(백준 4179 불!

(백준 5547 일루미네이션


# (디자인패턴 - 옵저버 패턴

* tags : [(디자인패턴](../%28%EB%94%94%EC%9E%90%EC%9D%B8%ED%8C%A8%ED%84%B4.md)
* links : [블로그 - 옵저버 패턴]()

## 옵저버 패턴

* 한 객체의 상태가 바귀면 그 객체를 의존하는 다른 객체에 연락이 가고, 자동으로 내용이 갱신되는 일대다 의존성 정의
* 어떤 주제와 이를 듣고 싶은 옵저버가 있을 때,
  * 주제가 변경될 때마다 옵저버에게 정보를 전달하고,
  * 정보가 변경된 것을 감지하면 옵저버는 주어진 행동을 함
* 주제는 일반적으로 등록, 제거 메서드를 가짐

## 코드

````python
import abc

class Subject:
    __metaclass__ = abc.ABCMeta

    @abc.abstractmethod
    def register_observer(self):
        pass

    @abc.abstractmethod
    def remove_observer(self):
        pass

    @abc.abstractmethod
    def notify_observer(self):
        pass

class Observer:
    __metaclass__ = abc.ABCMeta

    @abc.abstractmethod
    def update(self):
        pass
````

* abc를 상속받아서 주제와 옵저버 생성

````python
class WeatherData(Subject):
    def __init__(self):
        self.observers = []
        self.temperature = 0
        self.humidity = 0
        self.pressure = 0

    def register_observer(self, observer):
        self.observers.append(observer)

    def remove_observer(self, observer):
        self.observers.remove(observer)

    def notify_observer(self):
        for observer in self.observers:
            observer.update(self.temperature, self.humidity, self.pressure)

    def get_temperature(self):
        return self.temperature

    def get_humidity(self):
        return self.humidity

    def get_pressure(self):
        return self.pressure

    def measurements_changed(self):
        self.notify_observer()

    def set_measurements(self, temperature, humidity, pressure):
        self.temperature = temperature
        self.humidity = humidity
        self.pressure = pressure
        self.measurements_changed()
````

* 날씨 데이터를 주제 클래스를 상속받아서 생성

````python
class CurrentCondition(Observer):
    def __init__(self, subject):
        self.subject = subject
        self.subject.register_observer(self)

    def update(self, temperature, humidity, pressure):
        self.temperature = temperature
        self.humidity = humidity
        self.pressure = pressure
        self.display()

    def remove(self):
        self.subject.remove_observer(self)

    def display(self):
        print(F"Currnet condition temp: {self.temperature} hum: {self.humidity} pressure: {self.pressure}")

class StaticsDisplay(Observer):
    def __init__(self, subject):
        self.subject = subject
        self.subject.register_observer(self)

    def update(self, temperature, humidity, pressure):
        self.temperature = temperature
        self.humidity = humidity
        self.pressure = pressure
        self.display()

    def remove(self):
        self.subject.remove_observer(self)

    def display(self):
        print(F"Statics display temp: {self.temperature} hum: {self.humidity} pressure: {self.pressure}")
````

* 옵저버 생성

````python
weather_data = WeatherData()
current_condition = CurrentCondition(weather_data)
statics_display = StaticsDisplay(weather_data)

weather_data.set_measurements(10, 50, 30)
# Currnet condition temp: 10 hum: 50 pressure: 30
# Statics display temp: 10 hum: 50 pressure: 30

weather_data.set_measurements(20, 60, 40)
# Currnet condition temp: 20 hum: 60 pressure: 40
# Statics display temp: 20 hum: 60 pressure: 40

statics_display.remove()
weather_data.set_measurements(15, 30, 60)
# Currnet condition temp: 15 hum: 30 pressure: 60
````

* 각 객체를 생성하여 실행
* 지금 날씨, 통계가 모두 있을 때(또는 등록할 때), 날씨 데이터가 변경되면 해당하는 작업을 함
* 옵저버를 제거하면, 추가적인 행동을 하지 않음

# 참조


(디자인패턴 - 옵저버 패턴


# (디자인패턴 - 전략패턴

* tags : [(디자인패턴](../%28%EB%94%94%EC%9E%90%EC%9D%B8%ED%8C%A8%ED%84%B4.md)
* links : [블로그 - 전략 패턴](https://mintropy.tistory.com/61)

## 전략 패턴

* 전략 패턴(strategy pattern) 또는 정책 패턴(policy pattern)
* 전략 패턴은 실행 중에 알고리즘을 선택할 수 있게 하는 디자인 패턴으로 다음의 특징을 가짐
  * 특정한 알고리즘을 정의하고
  * 각 알고리즘을 캡슐화
  * 해당 계열 안에서 상호 교체가 가능하도록 함
* 위와 같은 특징을 구현하기 위해 다음 세가지 요소로 구성
  * 전략 메서드를 가진 전략 객체
  * 전략 객체를 사용하는 컨텍스트
  * 전략 객체를 생성해 컨텍스트를 주입하는 클라이언트
* 전략은 알고리즘을 사용하는 클라이언트와 독립적으로 다양하게 만들 수 있음

## 코드

````python
import abc

class Duck:
	__metaclass__ = abc.ABCMeta

	@abc.abstractmethod
	def display(self):
		pass

	def perform_fly(self):
		self.fly_behavior.fly()

	def perfrom_quack(self):
		self.quack_behavior.quack()
````

* Duck 클래스를 생성, 상세 행동은 구현하지 않음

````python
class FlyBehavior:
	__metaclass__ = abc.ABCMeta

	@abc.abstractmethod
	def fly(self):
		pass

class FlyWithWings(FlyBehavior):
	def fly(self):
		print("Fly with wings")

class FlyNoWay(FlyBehavior):
	def fly(self):
		print("Fly no way")

class QuackBehavior:
	__metaclass__ = abc.ABCMeta

	@abc.abstractmethod
	def quack(self):
		pass

class Quack(QuackBehavior):
	def quack(self):
		print("Quack Quack")

class MuteQuack(QuackBehavior):
	def quack(self):
		print("Mute...")
````

* 상세 행위는 다음과 같이 정의

````python
class MallardDuck(Duck):
	def __init__(self):
		self.fly_behavior = FlyNoWay()
		self.quack_behavior = Quack()

	def display(self):
		print("Mallard Duck")
````

* 새로운 오리를 생성할 때, Duck을 상속받고, 추가적인 행동을 정의하여 사용할 수 있음

# 참조

* [Wikipedia - 전략 패턴](https://ko.wikipedia.org/wiki/%EC%A0%84%EB%9E%B5_%ED%8C%A8%ED%84%B4)


mintchoco

(BOJ11785 CCW

문제 설명

문제 풀이