dbfs

빈출 문제를 반복 학습하자. 그런 문제를 하나 정하면 되는데 이코테 책 실전 문제에 나온 예제보다 좀더 어려운 백준 문제 정도 수준이면 된다

-: 못푼 문제 / 못풀고 답지 본 문제

 

*[bfs dfs 문제 구분]

https://haams704.tistory.com/75

https://foameraserblue.tistory.com/188?category=481823 

 

 

- ⭐️⭐️⭐️리트코드 2115: https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/

난 이 문제로 적잖은 충격을 먹었음... 이런 문제가 바로 dfs/bfs 구나... 사실 대다수 사람들이 이걸 위상 정렬로 풀었음. 근데 난 그거 모르니까 일단 그 풀이는 다음에 공부한다

난 이런 스탈 문제를 그동안 여러번 봤단말야? 그때마다 난 파이썬딕셔너리 사용하고 메모리 낭비를 많이 한다고 생각했지

이렇게 흡사 음... 해시 테이블? 해시셋? 해시트리? 구조 생각나는 애들이 바로 DFS BFS 로 바꿔푸는 애들이다.

다시 풀 때마다 못 풀고, 풀이를 보면 내 생각을 훨 뛰어넘는... 백준 골1쯤 돼보이는 난이도라 절대 쉬운 문제 아니라고 생각함

 

23년 9월 이후 6개월만에? 재도전. 복습은 한 적 있음. 본질로 접근해보자.

지금 이 구조를 그림 그래프로 치환해 그린다 생각해보자. 그럼 이건 어떤 특성을 갖는 그래프인가? 보통 실버 난이도에서 볼 법한 그래프와 어떤 차이 특성을 갖는가? 이렇게 접근해 봐라.

푸드가 재료가 될 수도 있기 때문에 (우리 서비스에서도 겪은 문제..) 둘의 경계가 희미해진 상황. 이들을 모두 노드라고 하자.

이 중 확실하게 존재 가능하거나 이미 존재하는 애들은 supplies에 포함되고, 음.. 얘는 검사 대상이 되는 갑의 위치.

그럼 이게 인접, 연결성으로 치면 .. 어떻게 되는 것이냐의 문제였던 건데, 원래부터 supplies에 있던 애들은 간선이 많은 노드가 되는 거고,

foods 안에 있는 애들은.. 얘네도 supplies의 일종이니까, 단지 원조 supplies 들 보단 간선이 적은 상황.

그럼.. 노드=supplies인데, 얘네는.. 수시로 노드가 추가 되는 그래프 구조인 거네?  그리고 이게 일종의 포함 관계랑 비슷한거라, 사실상 방향성 그래프라고 보는게 맞을 듯. 그럼 사이클이 존재할 수 있는 애들인가? 라 하면, 음...
아님 뭐, 트리인가? => 트리는 한 노드에서 다른 노드로 가는 경로가 유일합니다. => 이게 그래프와의 차이!

 

아 백트래킹 필요해...

 

 

 

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

⬆︎ 이거 풀고 충격먹어서 지금 유형 집중 훈련 하고 있는데, 그러면서 풀게된 것 중 하나. 근데 문제가 문제가 아니고 다른 사람들 풀이가 대박임... 

이거 중요한 이유가 어... 생각해보니 라인 핀테크 3번 문제랑 비슷한 것 같 한 노드로부터의 거리를 이용한단 점에서...

아 그럼 지금 보고있는 이 풀이들이 뭐 종만북에 나온다던지, 아님 dfs bfs 가 아닌 노드까지의 거리 관련한 다른 아이디어 통해서 풀수 있는 문제이기도 하다는 뜻이지 않을까...

근데 하도 오랜만에 봐서 그런지 몰라도 다시 보니까 영 이해가 안됨(다른 사람들 풀이가)... 지금도 이해 안된다 오랜만의 문제가 아니다. 무슨 발상인지 진짜 모르겠다. 얘만 계속 보고있는다고 해결되기보단 이건.. 다른 문제들 많이 봐야 이해가 갈 듯한...? 이건 백준님 강의 본다고 되는 거 아니잖슴.. 아님 실행시켜보면 좀 이해하려나?

 

 

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

브루트포스에 bfs 를 곁들인. 리모컨 문제와 흡사하다. 공통점은 브루트포스라는 점을 떠올리기 쉽지 않다는 점. 이정도로 복잡한 알고리즘 로직을 요하는 데다 N 최대 크기가 그것밖에 안된다는 것은... ㅇㅋ? 브루트포스인거 사실 힌트보고 알았지 그거 아녔으면 몰랐음 절대...

그럼에도 왜 브루트포슨지 생각해보려 함. 사실 완전한 브루트포스 아니고, 백트래킹으로 일정 조건 충족 안하면 바로 탐색 관두고 그런 식으로 하지 않을까? 이거 푸는 사람들은 뭔가 절차를.. 어떤 부분들에서 순회하고, ... 같은 식으로 밟았을 것 같음.

 

 

리트코드 2146: https://leetcode.com/contest/biweekly-contest-70/problems/k-highest-ranked-items-within-a-price-range/

시간 지나고 다시 풀어봄. 시간 초과. 뭔가 중복 카운트 혹은 비효율적 연산이 있기 때문인 건 알지만 그게 힙과 큐를 함께 쓸 필요가 없기 때문일 것으론 차마 예상치 못함. 또 힙 안쓰고 큐&set 조합으로 푸는 방법도 존재. 이건 파이썬 dbfs 정석 풀이를 기억한다면.. 당연했을.. 다음에 한 번만 더 풀어보면 정답 나오지 않을까 함.

힙 풀이 보면서 내가 놓친 부분 뭔지 보니까, 노드와 노드 간 distance가 점수 매길 때 최우선순위이기 때문에, 시작점에서 가장 가까운 노드부터 말그대로 음...이게 bfs라 봐야하나... 이렇게 탐색하면서 큐에 넣고, 꺼내서 pricing 검사 한 뒤 x, y 좌표 알아서 answer 배열에 넣어 만들면 더는 정렬이 필요 없는 답이 된다는 점. 이걸 놓쳤음. 결국 정렬이 오버 연산이었고, 숫자 범위가 10에 5승이고 내가 계산한 시간 복잡도인 O(n+nlgn)에서는 초당 10억 단위에 안걸리는데 왜 시간 초과가 났는지는 나도 모르겠음. 음... 3, 4 순위인 좌표는 사실상 있으나 마나 한 조건이었다는 점이 내가 놓친 부분이다.

 

와 대박. 23년 9월 6일에는 풀었다. 거리가 동일한 점들이 무엇 무엇인지 보고, dx, dy 기반으로 탐색할 때 탐색 순서를 의도적으로 신경쓰면 노드 점수 부여 중 3,4번째인 x,y 좌표는 전혀 신경쓰지 않아도 된다!

 

 

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

나는 분명 비슷한 문제를 풀었었다 뱀문제... 이거 바로 위위에 있는거 말이다. 즉 이 문제를 푸는 정석 풀이도 이런 식이다 - 장애물 3개를 (수학적) 조합으로 뽑고, 가능한지 안한지를 dbfs 를 통해 푸는 것... 근데 내가 이번엔 유형 분류 아예 안보고 풀었더니 아니 음 그래프 탐색이란 면에서 dbfs 일줄 예상은 좀 했지만 그게 비효율적이라 느꼈던 것 그래서 collection 라이브러리에 있는 온갖 것을 다 import 해서 풀었더니 웬걸... pypy3 정답 코드 454개 중 실행시간 기준 전체 6등을 한거다...! 이때 보니까 나처럼 푼 사람은 한명도 없더라(원래 백준은 그런 파이썬 풀이는 잘 안나온다)... 그래서 이런일 처음이라 넘 행복했고 그 코드는 따로 블로그 포스트 작성할 예정

 

그러나 세월 지나고 이제 더 빠른 애들 많이 나옴... 풀이 복붙해둠

 

 

- 14888: https://www.acmicpc.net/problem/14888

교훈 1. 일일이 다 따져서 풀어야 하는 문제라는 걸 책으로 풀이를 보고 나서야 알게됐다. 그전까진 그냥 머리써서 풀어야 하는 문제인줄로 알았다. 그래서 dbfs 로 풀거나 순열조합으로 풀어야 하는데 책에 중복순열로 풀수있다고 하길래 그말 믿고 따져봤는데 이건 영 아닌거다... 알고보니 그냥 순열이고 그중 중복을 제거해야 하는 것이었음

교훈 2. 문제는 그렇게 풀면 시간 거의 10배가까이차이나고 dbfs가 훨씬 빠름

따라서 이 문제의 총 교훈은 1 머리써서 푸는거 아니고 다 따져서 푸는 문제다    2 dbfs 가 구현/완탐 보다 빠르다.

 

 

- 16234: https://www.acmicpc.net/problem/16234

정말 거의 다 풀었는데... 예제는 다 통과하는데 제출하면 틀림. 사실 이 한바퀴 돌때까지의 T/F 처리, 그때 한번에 일어나는 인구이동을 하나로 취급하게 만드는 코드 부분이 어려웠다. 종료 조건도 어렵고 해서 음... 원래 계속 풀어보려 했는데 단톡에서 이렇게 하는게 너무 안좋다고 해서 그냥 포기하고 답지 보고 공부했는데 근데도 잘 모르겠... 그래서 그냥 나중에 시간 지나고 다시 풀어보는게 낫겠다 싶음

...... 그래서 다시 풀어봤는데, bfs로 로직 개선해야한다는 것만큼은 확실해서 그거 중심으로 기존 제출한 코드를 수정하는 방향으로 다시 풀었더니 이번엔 정답은 맞다만 시간초과... 몇가지 원인을 찾아서 아주 조금 성능 끌어올리긴 했지만 나머진 더이상 몰겠다 싶을 때 다른 풀이 봐서 공부함. 종료조건하고 음 자잘한 것들 고쳐서 그냥 이해보단... 보고 성능 저하원인 되는 부분만 베껴 고쳐서 제출해서 정답 나오게 해서 찐이 아님. 음 이 문제의 어려운 점은 자잘한 코드 한 줄 로직을 어느 위치에 배치할지 정하는게 매우 어렵다는 것임 이를테면 True 로 바꾸는건 어디서, flag 트루는 어디서, 새로운 visit 리스트 초기화는 어디서... 등. 거기다 시간 복잡도 분석도 매우 어렵삼.

백준 맞히고 나서 1등 풀이봤는데 3달 전 풀이밖에 안되는데 당최뭔소린지 디버거 걸고 해도 이해 1도 안됨... 숨막힐정도로 기막힌 풀이란건 알겠는데... 2등 풀이는 공부하다 말았음 지겨워서

 

 

- 2580: https://www.acmicpc.net/problem/2580

일단 옛날에 못풀어서 재도전한 문제. dfs + 백트래킹 아이디어라고 나는 예나 지금이나 생각했는데 이게 완전탐색 분류에서 발견한 문제인 것도 기억해서... 후자일경우 모든 경우의수 다 넣어서 풀어보는 문제인거 기억했는데 그걸 코드로 어케 구현할지를 모르겠더라고. 아니 빈칸이 많을텐데 거기에 진짜로 1~9 다넣는건 아니고 후보군 추려서 넣는 방식이라고 생각해서 그걸 생각하고 있었음. 풀이 보니까 정답은 "둘다 맞았음". 말인 즉 2개 합쳐져 있는 문제라는 것임. 완탐 dfs 백트래킹 다 하는거고 그걸 어떻게 구현할 것인가에서 나는 막힌거임. 뭣보다 dfs 로 백트래킹 하면 스택트레이스오버 에러 날까봐 무서워서 암것도 못하겠더라고...

내 풀이를 생각해보면 음 섬세하긴 하지만 너무 복잡함 사실 그렇게 복잡하게[ 풀리는 알고리즘문제나 수능문제는 없기땜에 사실 거기서부터 이미 실패 시그널 감지하긴 했음. 근데 또 이게 성공하면 실행시간이 엄청 작게 나올것같아서 매달렸지... 나는 가로세로3*3 모두 1~9 집합 갖게 만들었고 교집합 가지게 해서 후보군 추리고 힙 써서 빈칸들 중 가장 많은 정보 갖고있는 칸부터 뽑아서 정보 추론하게 만들고 뭐 그런식이었음. 근데 이런 경우 생기면 어케 되는거지? 하는 그 '경우'에 해당하는것들이 몹시 많아서...

결론은 다음에 또 다시 재도전 해서 풀어라.

 

 

1707: 이분그래프 문제. 어렵지 않은 거였고 세월 지나서 블로그 적당히 참고해서 푸니까 풀린다. flag 1,2 번으로 분류한단 아이디어 및 내가 마지막에 겨우 생각해낸 반례(내가 작성한 코드에 써둠) 까지만 기억하자!

 

 

- 1987 https://www.acmicpc.net/problem/1987

굉장한 교훈을 얻은 문제다.

1. defaultdict 의 value 값 검사 및 값 변경/대입보다 set의 탐색, 삽입, 삭제가 더 빠르다... 믿을 수가 없어!

2. 아래 두 코드 비교

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(4):
	nx = x + dx[i]
	ny = y + dy[i]
	if 0 <= nx < r and 0 <= ny < c and not maps[nx][ny] in alphas:

dxy = [(1,0), (0,1), (-1,0), (0,-1)]
for dx, dy in dxy:
	if 0<=x+dx<R and 0<=y+dy<C and not road[x+dx][y+dy] in alphabet:

위 코드는 다른 풀이들에서 자주 보던 거고, 아래는 내가 즐겨쓰던 방법이잖아? 근데 저러면 덧셈 연산이 많아지면서 시간 효율이 떨어진다.

그래서 위처럼 푸는거다. 골드쯤 되면 이런 사소한 것도 시간에 영향을 미친다... 😱

 

결론적으로 나는 어떻게 해도 시간 초과가 뜨길래 이 링크 (https://sorryhyeon.tistory.com/34#2.%20%EC%BD%94%EB%93%9C) 를 참고해서 flag&if 부분 일부 수정하고, 셋으로 바꿔서 했는데... 그렇게 해도 시간 초과 나길래 그냥 링크의 코드 복붙해서 제출한 뒤 최상위권 풀이를 공부했다.

3. 최상위권 풀이는 하나같이 ①ASCII 코드를 활용한다 (아는데도 맨날 까먹으니 확실하게 기억하고 가자 이번에)   ②비트마스킹!!!

'python 비트마스크' 라 구글 검색하면 포스트 많이 나오고 내용 다 비슷. 난 요거(https://velog.io/@1998yuki0331/Python-%EB%B9%84%ED%8A%B8-%EB%A7%88%EC%8A%A4%ED%82%B9-%EC%A0%95%EB%A6%AC) 봤음

그럼 1987_1 풀이가 이해됨. 위 링크 설명에 나온 대로 1<<(원하는 숫자) 는 (원하는 숫자) 번째에 1이 표기된 이진수 데이터를 얻기 위함이고(10, 100, 1000 ... 처럼 원하는 숫자 횟수만큼 옮기는 것이다) , 이걸 원하는 다른 숫자(위 링크에선 S, 1987_1에선 mask) 와 &, |, ^ 등의 연산을 하는 것이 곧 집합에 추가/삭제 etc 를 하는 작업과 동일하다. 

mask & loc(ny, nx): 같은 알파벳인지 검사!

아래 2개는 도대체 왜 하는지 전혀 이해 안됨 아직도.

mask | loc(ny, nx): | board[y][x]에 board[ny][nx] 를 추가해준다...? 블로그에서 에스는 집합이니까 그렇다 치는데 얘는...?

visited[ny][nx] ^ (mask|(loc(ny, nx)) 이 연산을 대체 왜 하는거야 이걸 하는게 무슨 의미가 있어...?

아 이제 이해해서 풀이에 주석으로 다 써놨음.

 

 

- 카카오 2023 이모티콘 할인행사: https://school.programmers.co.kr/learn/courses/30/lessons/150368?language=python3 

모든 경우의 수는 4의 7승 즉 2의 14승, 연산 횟수까지 합하면 여기에 *100이기에 그냥 완탐 하는 건 아닐 거라고 생각했음.

'최적해를 구한다'는 건 알았으나, 디피는 아니니까 수학 아이디어로 푸는 줄 알았음. 근데 완탐 맞고, 단지 dbfs로 풀 뿐인 거다. dbfs 를 쓰면 완탐을 하면서도, "초반에 계산한 걸 또 계산해야 하는 계산 중복을 줄일 수 있기에". 따라서 이 문제는 그동안 완탐 유형일 때 순열조합 말고 dbfs 기법을 굳이 쓰는 이유를 깨닫지 못했던 내가 이걸 씀으로써 얻는 효용이 뭔지 깨달은 계기임.... 이 아닌데? 전체 경우의 수 구해도 되는데...? 내가 신기한 건 이렇게 큰 사이즈의 경우의 수를 얘는 어떻게 버티는 거임? 이코테의 기준과 플머스의 기준은 암만 생각해도 좀 다른 듯... 사실상 이 기준을 몰라서 완탐으로 못푼거랑 마찬가지잖아.

동기부여 겸 옛날 감 찾으려 푼 문제였는데, 이 영상이 람다, yield 까지 쓰면서 풀어서 배우는 것도 있고 좋았음. 빅테크 여성 개발자임. 근데 시간 복잡도 해석은 안한 것 같기도..?: https://www.youtube.com/watch?v=o-gCVXs3vIw 

지금 yield 안쓰고 나머지는 람다 등만 적용해서 풀었다가 틀렸음.. 헷갈려 죽것다. 다음에 다시 풀어보자.

 

- 1991: https://www.acmicpc.net/problem/1991

트리 순회는 너무 기본이라 외웠다. 따라서 복습을 요함

 

- 1167: https://www.acmicpc.net/problem/1167

구조만 트리지, 실제론 그래프 알고리즘(프림, 크루스칼, 플로이드워셜 등등)류라고 예상했는데, 플로이드 워셜 쓸 수 있지만 노드 개수 10만 정도면 시간 초과가 난다고 한다. 검사 경우의 수를 어떻게 줄이나 했더니, 우선 정답에 해당하는 최대거리 중 한 끝은 반드시 루트를 포함할 것이라고 함. 루트를 포함하지 않는 경우는 (이하 1167 참고). 또, 검사중인 노드에서 다음 노드 중 가장 거리가 먼 곳에서 dbfs를 반복하면 된다고 한다 가장 깊이 갈 때까지 말이다. 모든 노드 2개 조합에 대해 검사하지 않아도 되는 이유는? 이게 그래프가 아닌 트리란 점에서 기인한다. 글고 1167_1 즉 백준 2등 풀이는 그래프 초기화 상태에서 나처럼 새로 배열 객체 갈아 치우지 않고 있던 객체에 append 하는 식으로 초기화 했는데, 난 어느게 더 시간 적게 나올까 궁금했는데 append가 훨씬 적게 나오네. 역시 객체 갈아끼우기가 아무리 그래도 어펜드보다 시간 많이 걸리는구나. 복습을 요하는 문제.

 

 

 

- 21772: https://www.acmicpc.net/problem/21772

가희님 코테 문제 드디어 풀어봤다! 시작은 코테 대비용으로 복습하려는 의도 - https://codingdog.tistory.com/entry/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9%EA%B3%BC-%EA%B0%80%EC%A7%80%EC%B9%98%EA%B8%B0%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%98%88%EC%A0%9C-%EB%AC%B8%EC%A0%9C%EB%A5%BC-%ED%86%B5%ED%95%B4-%EC%95%8C%EC%95%84%EB%B4%85%EC%8B%9C%EB%8B%A4

요 글로. 학습하기 좋으니까. 근데 시간이 급해서 적당히 풀어보다가 풀이 봤따.