Intermediate 1/3

{5,6}0X: Graph, BFS + {7,8}0X: Greedy, Divde-and-Conquer, Binary Search

https://code.plus/course/43

2024.06.12 - Baekjoon 16197 두 동전

PyPy3 {1005580 KB, 3296ms} 통과 / Python3 시간초과
시간 줄이는 방법? ---> visited=set() 활용!

2024.06.12 - Baekjoon 16197 두 동전

visited = set()으로 동전 위치들의 state를 기록.

PyPy3 {113168 KB, 140ms} 통과
Python3 {34164KB, 68ms} 통과

2024.06.11 - Baekjoon 1202 보석 도둑

최대힙을 활용하여 풀이
Python3 {117840KB, 1392ms}, PyPy3 {180032KB, 1112ms} 로 통과

2024.06.11 - Baekjoon 1062 가르침

데이터 길이가 작아서 대충 짰음.
set을 활용

2024.06.10 - Baekjoon 2109 순회강연 <heapq, 우선순위 큐의 동작원리>

heap := 완전 이진트리의 일종으로, 여러 값 중 최대/최소 값을 빠르게 찾기 위해 만들어진 반정렬 상태. O(logn)
https://wikidocs.net/194445
https://velog.io/@jeunghun2/Python-heapq-%EB%AA%A8%EB%93%88

2024.06.10 - <heapq 사용예시>

Python에서 heapq는 최소힙
O(logn)으로 자동정렬해주는 큐. (이진트리이므로 O(log_2(n))
list 의 제일 앞에 최솟값이 등장 heapq.heappop(h)로 최솟값을 제거할 수 있다.

2024.06.10 - Baekjoon 2109 순회강연

1순위) pay 내림차순, 2순위) 날짜 오름차순으로 정렬하고 시작하는 코드도 있음.
https://thought-process-ing.tistory.com/276

2024.06.10 - Baekjoon 2109 순회강연

heapq, 우선순위 큐가 뭔가? Greedy Algorithm에 등장하는 이유?
O(logn)으로 자동정렬해주는 큐.
Python "import heapq" 는 최소힙을 제공한다.
최대힙을 구현하고 싶으면, 튜플 방식으로 부호를 변경하여 넣는다. (-x,x)
heapq.heappop(heap)을 하면 튜플 형태로 최소값이 출력된다.

https://growth-coder.tistory.com/128

2024.06.10 - Baekjoon 2109 순회강연 <heapq 사용유무 성능비교>

Python3에서 PyPy3 보다 60ms < 176ms heapq를 사용했을 때 더 빠른 시간복잡도를 가진 것은 의외. O0o
heapq를 쓰지 않았을 때는 {PyPy3, 292ms} 만 통과 {Python3, 43% 시간초과}
heapq를 썼을 때는 {PyPy3 176ms}, {Python3, 60ms} 로 통과.
내 첫 풀이가 heapq를 쓰지 않고 통과한 것이 오히려 주목할만한 부분이라는 생각.
heapq를 쓰면 코드가 짧아지고, 시간속도도 빨라짐. Baekjoon 보석도둑 문제에 find_index함수를 이분탐색을 통해 진행하려 했는데, O(logn)이라는 점에서 비슷한 아이디어를 떠올린 것으로 생각됨.

2024.06.10 - Baekjoon 2109 순회강연

1순위) 날짜 오름차순, 2순위) pay 내림차순으로 정렬
(1) 가장 멀리 추가할 수 있는 날짜가 비어있다면 추가한다.
(2) 이전 날짜에 추가할 수 있거나 바꾸어서 pay가 증가한다면 추가한다.
PyPy3 {111804KB, 292ms} 통과 (Python3 43% 시간초과)

인터넷을 보니 heapq라는 우선순위 큐를 보통 활용하는 듯함. -> 공부

2024.06.10 - Baekjoon 2109 순회강연

Q. Python, import heapq, 최소힙을 사용하면 편한 이유?
A. 현재 stack에 쌓여있는 여러 값들 중에서 "최솟값"을 제거하는 것이 목표이기 때문에.

2024.06.09 - Baekjoon 1931 회의실

회의를 tuple로 입력받아 빨리 끝나는 순으로 정렬.
Greedy하게 추가. {51900KB, 244ms}

2024.06.10 - Baekjoon 1202 보석 도둑

visited[j]를 사용해도 3%에서 시간초과

2024.06.06 - Baekjoon 16928 뱀과 사다리 게임

단순한 BFS 문제
시간단축을 위해 코드 작성 전부터 뱀과 사다리를 hash map 함수인 dictionary 자료형으로 구성을 계획했음. (list로 구성하면 느릴 것이므로)
{34072KB, 68ms} 로 통과! 제한은 {512MB, 1초}

2024.06.07 - Baekjoon 2580 스도쿠

Python3/PyPy3 모두 시간초과

2024.06.05 - Baekjoon 1517 버블 소트 (swap 횟수)

merge_sort O(nlogn) 이 bubble_sort O(n^2) 보다 시간은 빠르고, 메모리는 많이 사용하는 점을 활용.
merge_sort 와 bubble_sort의 swap 횟수가 대응되는 부분을 찾아서, global 변수 swap에 더한 후 출력. 왼쪽과 오른쪽 원소 크기가 같으면 swap하지 않음에 주의.

2024.06.05 - Baekjoon 1517 버블 소트 (swap 횟수)

{89984KB, 2344ms}로 통과,

2024.06.05 - Baekjoon 1517 버블 소트 (swap 횟수)

실제로 Bubble Sort를 Merge Sort로 푸는 문제가 내가 푼 첫 플레티넘 문제였던 것을 통해서, 공부하고 풀만한 문제였다는 결론.

2024.06.04 - Baekjoon 1517 버블소트 - 메모리/시간 확인 결과.

PyPy3의 사용이 메모리는 2배, 시간은 1/3배. - memory/time trade-off

2024.06.04 - Baekjoon 1517 버블소트

tuple을 list에 추가해서 tuple 원소 대소비교를 사전순으로 자연스럽게 하는 것도 = idea 1) to implement idea 2)
tuple = (element, index) 후에 정렬된 list에서 index를 자연스럽게 뺄셈. Bubble sort가 진행된 횟수 = 리스트 내 원소가 최대 왼쪽으로 이동한 위치차이 = idea 2)
Merge Sort로 푼 결과를 Bubble Sort의 횟수 역추정에 사용 = idea 2)
import sys, input = sys.stdin.readline 없으면 시간초과.
3달만에 풀었음.

2024.06.04 - Baekjoon 1517 Bubble Sort (vs Merge Sort)

분할정복을 활용한 Merge Sort Python 구현에 참고한 블로그
폰노이만이 개발한 기법이라고 하니, 내가 생각하는데 오래걸린 것, 힌트를 구한 것도 꽤 당연하게 받아들여짐. 문제 정답률이 약 30.1% 로 높아서 오히려 놀람. (python 내장 sort를 사용하겠다고 마음먹었다면 역추정 아이디어를 떠올리기 비교적 쉽긴 함.)
https://codingsmu.tistory.com/133

2024.06.04 - Baekjoon 1517 버블소트 (정렬, 분할정복)

시간초과문제를 어떻게 해결해야 하는지 잘모르겠어서 검색을 통해서 sort를 좀 공부하고 해결하기로 함.

> 백준의 힌트들은 내장 sort함수를 그대로 사용한 결과를 바탕으로 역추정하는 알고리즘을 제안.

python 내장함수는 timsort = insert sort + merge sort 를 합한 hybrid stable sorting algorithm이라고 함.
분할정복 태그에 포함된 힌트 의미는 시간복잡도가 Merge Sort = O(nlogn) < O(n^2) = Bubble Sort 를 사용해서 결과를 통해 역추정하라는 뜻으로 추정.

> 문제에 C+로 제공된 Bubble Sort O(n^2)을 구조를 그대로 따라갈 생각만 해서, 다른 Sort Algorithm을 적용하여 풀 것은 전혀 예상 못했음.

sorting 비교표에서 확인할 수 있듯이 sort에서도 시간복잡도 vs 메모리사용 trade-off는 항상 존재.
https://velog.io/@toezilla/1D1Q-%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9D%98-sort-%EB%82%B4%EC%9E%A5%ED%95%A8%EC%88%98%EB%8A%94-%EC%96%B4%EB%96%A4-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%A0%EA%B9%8C

2024.06.03 - Baekjoon 2110 공유기 설치

이분탐색을 적용하기 전에, 첫집에 항상 공유기를 설치할까?에 대해 고민했는데, 두 공유기 사이 거리를 항상 크게 설치하는 것이 목표이므로 수학적으로 항상 설치하는 것이 이득.

1) 첫집이 설치되어 있다 > O

2) 첫집이 설치 X - 첫집으로 옮긴다. > 더멀리 거리가 만들어짐 > O

2024.06.03 - Baekjoon 2110 공유기 설치

Python3로는 시간초과 -> PyPy3가 예상보다 너무 빨리 통과해서, # import sys # input = sys.stdin.readline 추가해서 Python3 실행하니까 통과.

> import sys활용해서, Python3 {38848KB, 316ms}로 메모리도 아끼고 빠르게 통과.

input 길이가 N = 200,000 으로 길어서 21%에서 Python3로 시간초과가 있었던 것을 해결!
PyPy3 {118308 KB, 244ms} 로 제한시간 2초보다 빠르게 통과.

2024.05.31 - Baekjoon 2343 기타 레슨

간단한 자연수값 이분탐색
자연수값 +1, -1 차이에서 마지막 출력값 선택을 하나로 압축하는 방법이 있는지?

(1) while low<=high (2) mid = (high+low)//2 + 1 등등 시도해보았으나, 예외처리에 실패.

(2) mid + 1, mid -1 은 이분탐색이 아니라서 시간초과.

{42204KB, 156ms} 로 통과

2024.05.31 - Baekjoon 2343 기타 레슨

맞힌 사람 기능을 통해 Python3에서 확인했는데,
최솟값을 찾는 자연수값 이분탐색의 경우,

(1) high =mid, low = mid 가 아니라,

(2) high = mid -1, low= mid +1 로 바꾸어 항상 low>high가 되는 상황을 만드는 잡기술 존재.

while low <= high 조건을 가지고 마지막에는 print(low)만 하면 됨.
{42204KB, 172ms}로 의미는 없지만 살짝 느리게 통과.

2024.05.28 - Baekjoon 1987 알파벳 (함수명이 dfs이지만, BFS 알고리즘)

Python3 로도 풀어낸 사람들의 아이디어 (1) BFS + (2) 알파벳 갯수는 26개
max_count = 26이라면 숫자가 등장하면, 알파벳 갯수가 26개이므로 최대 upper bound 출력값이라서 그대로 출력하는 코드가 시간 단축..!
잡기술 같기도 하고, 시간단축을 위한 최적화라고 생각되기도 함.
여튼 항상 문제에 특정 (값의 범위, 시간, 메모리, 데이터의 형태 등등...)된 특정한 좋은 방법이 항상 존재한다는 생각도 듦. 공자의 사자성어 속담으로는 "할계우도. 닭을 잡는 데 어찌 소 잡는 칼을 쓰겠는가?"

2024.05.28 - Baekjoon 1987 알파벳 BFS

Python3 시간초과/ PyPy3 메모리초과

2024.05.28 - Baekjoon 1987 알파벳 DFS

Python3 시간초과/ PyPy3 {156468KB, 6980ms} 통과
DFS가 state 정의에 더 깔끔한 코드.

2024.05.27 - Baekjoon 2873 롤러코스터 - 중간 과정 생각 (?)

2024.05.24 - Baekjoon 12970 AB

[1] 제일 오른쪽에 있는 'A'를 왼쪽으로 가져간다.

[2] 제일 왼쪽에 이미 도착해있다면, 오른쪽에 'A'를 새로 추가하고 [1] 반복.

을 통해서 AB 갯수를 "한개"씩 늘려갈 수 있다는 사실을 수학적으로 발견.

AB 갯수를 +1씩 늘려가는 방식이 전체 숫자를 탐색하기 위해 중요하다고 판단했음.

[3] 최대 갯수를 미분을 통해서 구하고 N= even or odd로 나누어서 출력.

2초 제한 문제를 {31120KB, 48ms}에 해결 =). 한번 시도.

2024.05.24 - Baekjoon 12970 AB 풀이 과정.

2024.05.23 - Baekjoon DSLR (1/2)

visited list가 있는 bfs로 접근
시간제한이 6초로 꽤 긴 편
visited list가 있는 bfs로 접근
PyPy3 {219556KB, 15800ms}로 통과.
Python3로는 시간초과

2024.05.23 - Baekjoon DSLR (2/2)

string 대신 정수를 다루도록 함수롤 구성해도 Python3에서는 시간초과 =| (PyPy3 기준 15800ms > 6076ms 로 약 1/2배로 단축되기는 함)
검색해보니 Python3로는 푼 사람이 매우 적은 문제 =|
백준 "맞힌 사람" 기능을 통해 다른 사람들의 코드를 볼 수 있는 것을 처음알게 되었는데, Python3로 해결한 사람들은 양방향 BFS 탐색으로 해결.
양방향 BFS 란? A에서 BFS 트리 하나, B에서 BFS 트리 하나를 생성하여 만나면 멈추는 방식. 단방향 BFS를 문법처럼 외우고 있었는데, 이렇게 구현할 수도 있구나 싶어서 놀랐음 O0o.

2024.05.14 - Baekjoon 1654 랜선 자르기

{31120KB, 456ms} 로 통과
쉬운 자연수 이분탐색 문제

2024.05.18 - Baekjoon 1300 - K번째 수

list.sort()로 하면 메모리 초과
{31120KB, 768ms}로 통과
어떤 수가 주어졌을 때, 현재 수의 위치를 판단하는 것을 각 행마다 나눗셈연산을 통해 판단
lower = upper 가 될 때까지 이분탐색

2024.05.13 - Baekjoon 2805 나무자르기 (self discussion)

자료형을 list 대신 counter를 사용하면, 알고리즘은 동일한데 소요 시간은 4772ms (통과 못함) > 396ms (통과함, 1/10) 이 되는 것을 확인했다.
자료형은 데이터 처리 속도에 정말 중요하다!
https://develop247.tistory.com/361

2024.05.13 - Baekjoon 2805 나무자르기 (Python 3 시간초과)

36%에서 시간초과

2024.05.13 - Baekjoon 2805 나무자르기 (PyPy3로 통과)

import sys, input = sys.readline (입출력 빠른 코드 추가)
while문을 함수화 (지역함수는 빠르게 처리)

두가지를 시도했으나, Python 3에는 통과하지 않아서.

PyPy3 로 실행 후 통과 (메모리를 많이쓰고, 시간 단축)

{266068 KB, 896ms} < 제한 시간인 1000ms에 거의 딱 맞아서 Python3로는 통과하기 쉽지 않았던 것으로 판단.

[1] 내 알고리즘처럼 값을 반으로 나눈 후, 정수 값을 택하는 대신

[2] H를 정수값으로 +1, -1 위치로 이분탐색하는 것으로 알고리즘을 작성하면, 약간 더 빠르게 진행되어 통과하는 것을 다른 코드들을 통해서 확인.

[3] list 대신 counter 자료형을 사용하면 더 빠르게 (10배 단축) 데이터 처리가 가능한 것을 확인!

https://develop247.tistory.com/361

2024.05.11 - 백준 11664 선분과 점

쉬운 이분탐색 문제, {31252 KB, 40 ms} 로 통과.

2024.05.12 - 백준1790 수 이어 쓰기 2

간단한 수학 문제, but 정답률 30.984%.
메모리 제한 64MB, N <= 100,00,000 이므로 str을 이어쓴 num을 생성한 후에 num[k-1] 을 출력하기보다는, 자릿수 연산을 통해서 마지막에 어떤 수에 몇번째 자리를 출력해야하는지 확인. {31120KB, 40ms}로 통과.
쉬운 나머지 연산 문자라고 생각하고 풀었는데, 이분 탐색을 어떻게 적용하는지? 궁금해서 구글링해보았음. 이분탐색 알고리즘의 목표도 동일하게 마지막에 k번째 자릿수를 포함하는 숫자를 구하는 것이 목표였음.
https://instories.tistory.com/210
내 코드는 좀 더 DP 관점이고, 주석을 빼면 짧고 간결한 코드로 생각됨.

2024.05.10 - 백준 2263: 트리의 순회

아직 푸는 법 잘 모르겠음.

2024.05.10 - 백준 2022 사다리

쉬운 이분 탐색 문제

2024.05.02 - Baekjoon 1891 사분면

4분면 위치 표시를 일반적인 행렬 인덱스 위치로 만드는 함수와 역함수를 정의
일반적인 행렬 인덱스 위치에서 옮긴 후, 범위 안에 존재하면, 역함수를 적용. mod 연산을 통해서 쉽게 접근.
※ 4분면의 숫자가 수학에서 정의와 다르고 dx, dy의 정의에서 +/- 부호에만 주의하면 쉬운 문제
2초, 128MB인 문제, {31120KB, 40ms}로 통과!

2024.05.02 - Baekjoon 1891 사분면 문제 이해 및 풀이 아이디어

BFS나 DFS와 비교했을 때, <분할정복> 문제들은 어느정도 정해진 문법을 적용하기 보다는, 단어 그대로 분할적으로 문제를 해결해나가는 함수를 다양한 방법으로 구성하는 것이 목표라는 것이 개인적인 결론.
개인적으로 <Baekjoon 1891 사분면>은 문제 정답률 30% (G4) 에 비해서는 많이 쉽지 않나 싶었는데, 생각보다 푼 사람 수가 적고 (1000명 미만) 평균 시도율도 높아서 의외였음.
개인적으로 제일 어려웠거나 번잡했던 문제는 반례들을 많이 고려해야했던 후위표기식 문제 (G2). 백준에서 제공하는 난이도와 개인체감이 다를 수도 있는 것 같음. 내가 푼 문제별 난이도를 대략 보았을 때 보통은 비슷비슷.

2024.04.25 - Baekjoon 1074 - Z

2x2 block에서 사이즈를 키우는 재귀적 방식으로 접근

시간 초과

2024.04.25 - Baekjoon 1074 - Z

offset idea는 유지하고 index 연산만 활용
시간 초과 해결 {31120KB, 44ms}
경험상 0.5초 문제들은 무조건 숫자 연산 (index)만 활용해야 시간초과 이슈를 해결할 수 있음.

2024.04.25 - Baekjoon 2488 별찍기 - 11

규칙 찾기, 재귀적
단위 block을 키워나가는 방식으로 접근.
인터넷의 다른 코드들 (좌표 활용, dfs) 코드들 보다 내코드가 훨씬 직관적이고 짧음.

2024.04.05 - Baekjoon 11652 카드

Hash, Python dictionary 자료 구조형을 사용하는 단순한 문제
import sys 사용유무에 따라 사용하면 148ms로 통과 vs 사용하지 않으면 4032ms로 통과.

2024.04.04 - Baekjoon 1783 병든 나이트

BFS 로 접근시, N과 M 값이 시간 2초 내에 해결 불가능.
조건을 나누어서 수식으로 바로 계산. 약간의 greedy algorithm

2024.03.30 - Baekjoon 11729 - 하노이의 탑

최소 이동 횟수는 2^n -1, n: 원판의 갯수.
N-1 개의 원판을 최종 목표가 아닌 원판에 옮기고, 제일 아래의 원판을 최종 목표에 옮기고,

그대음 N-1개의 원판을 최종 목표에 옮기는 재귀 구성.

4개의 막대, 5개의 막대의 경우? 를 생각하면 현재 코드는 굉장히 특수한 경우.
고등학교 때 배웠던 문제인데, 분할정복의 이해를 위해서 일반 코드들을 참고하여 공부하고 풀었음.

꽤 어려운 문제라고 생각하는데, 정답률이 50%를 넘어가서 놀람.

2024.04.03 - Baekjoon 15736 청기 백기

메모리 초과/시간 초과
수학을 통해 한줄로 해결

2024.03.27 - Baekjoon 2447 별찍기 - 10; 인터넷 풀이 https://interrobang.tistory.com/91

star_unit = draw(scale//3) 이라는 재귀 함수를 for 의 in 인자로 활용하여 코드 길이를 줄인 것이 인상 깊어서 메모.

2024.03.17 - Baekjoon 11728

그냥 A 와 B를 합쳐서 .sort() 사용
A 와 B를 각각 합치기 전에 정렬되어 있으므로, 중앙에 끼워넣는 형식이 분할정복 방식이었을 듯함.

2024.03.27 - Baekjoon 2447 별찍기 - 10

재귀, 분할 정복을 사용하여 해결. 자료구조는 2차원 list 활용.
list 자체를 계속호출하면 메모리 초과가 되므로, list의 인덱스를 분할정복에 사용.
{69452KB, 1112ms}로 통과

2024.03.16 - Baekjoon 1780, 재귀함수로 접근

시간초과
count 함수를 비효율

2024.03.16 - Baekjoon 1780, 분할정복으로 접근

count 함수 대신, check_same 함수를 정의
sub_arr를 생성하는 대신, 오직 index로만 확인.

2024.03.15 - Baekjoon 12919, A와 B 2

기존 'Baekjoon 12904 A와 B' 와는 다르게, 문자열의 끝이 A or B 이느냐에 따라, 1:1 대응으로 풀 수 는 없음.
BFS que를 통해 T-->S로 역으로 확인하되 확인하되, 생성되는 문자의 길이가 입력문자 S의 길이보다 작아지면 종료.
{34052KB, 68ms}로 통과.

2024.03.10 - Baekjoon 1744 수 묶기 (greedy)

0 을 추가하거나, 있다면 index_zero를 찾고
index_zero를 기준으로 greedy하게 합하기.

이 때 수열이 짝수/홀수에 주의.

n+1 > n*1 에 주의.

2024.03.12 - Baekjoon 12886 돌 그룹

A,B,C 를 오름차순으로 정렬한 것을 state로 BFS 활용.
A,B,C 의 visited 방문을 set()으로 정의하여 빠르게 확인.
처음에 돌의 갯수가 3의 배수가 아니면, 같은 갯수로 삼등분이 불가능하므로, 우선 print(0)을 출력!

2024.02.29 - Baekjoon 10610, 30

30의 배수 중에서 "제일 큰 수"를 만드는 문제
3의 배수는 필요충분 조건으로 모든 자리수의 합이 3의 배수, 10의 배수는 필요충분 조건으로 1의 자리가 0 임을 활용.
0이 있다면, 해당 0 외에 다른 수들은 내림차순 정렬하고, 일의 자리에 0을 추가하는 것으로 끝.

2024.03.09 - Baekjoon 14395 4연산

visited를 set으로 만들어 메모리 초과 해결. list [0]*10**9 은 메모리 용량 초과.
isPossible(s,t)를 먼저 체크하여 t=0 or 2**even, s**even인지 log를 통해 확인하고, bfs를 동작시키는 방식으로 접근했었으나, BFS의 동작속도만으로도 feasibility check 없이 충분히 주어진 시간 내에 해능하여 (s+s, s*s 가 빠르게 증가하므로) 조건함수 isPossible(s,t)는 생략.

2024.02.28 - Baekjoon 12904 A와 B

간단한 greedy 문제, 문제의 complexity를 계산한 후에 역연산으로 접근.

2024.02.26 - Baekjoon 2875 대회 or 인턴, 조건이 있는 BFS 문제 형식으로 탐색

인턴에 참가할 성별 1명을 정할 때, (여자2, 남자1) 팀을 구성하는 것을 만족하기 위해서,

1) 여자 > 2*남자 인 상황이면, 여자 -1

2) 여자 <= 2*남자 인 상황이면, 남자 -1

인턴십에 참가할 인원을 모두 결정했으면, K=0이 되면서, 종료. greedy algorithm의 이해를 위해 인터넷에 올려젹 있는 다른 문제풀이들의 구조를 확인했을 때, 인터넷 풀이는 team 을 구성하는데 greedy하게 접근해다면, 내 풀이는 Internship 을 줄이는데 greedy하게 접근함. 내 풀이가 몇몇 인터넷의 조건문들 보다 훨씬 직관적이고 간결한 풀이.

34016KB, 60ms 로 통과.

2024.02.26 - Baekjoon 2875 대회 or 인턴, 인터넷 풀이.

https://hseungyeon.tistory.com/193
여자 2명, 남자 1명을 빼면서 team을 greedy 하게 증가시키고,
적절한 탈출 조건을 통해서 while문을 탈출.

아직까지 DFS. BFS와 달리, greedy algorithm이 정확하게 어떤 형식인지는 모르겠음. 내 풀이는 intership 수를 한명씩 줄여나가는 방식으로 생각하여, 마찬가지로 굉장히 직관적.

2024.02.25 - Baekjoon 14502 연구소

벽을 3개 세우는 것에 greedy한 방법이 있는지 고민해보았는데, 모든 경우의 수에 적합한 방법은 확신이 들지않아 Brute-force로 접근.

빈 칸에 벽 3개를 세우는 것은 python itertools를 사용. itertools를 사용하지 않거나 C 언어로는 어떻게 풀었을까 잠깐 고민해보았는데, Back-tracking 재귀함수로 벽 3개 세우는 것을 모두 탐색할 수 있었음. 즉 BFS+DFS 혼합 문제로도 생각되는 문제였음. 나는 BFS + itertools로 해결.