✔ BOJ
알고리즘 스터디 2주치 쌓여서 머리가 정리가 안되길래 일단 2주치 문제 정리해본다. 스터디 가야되니께,,
7562 나이트의 이동
bfs 이용해서 모든 나이트의 이동을 다 해보고, 도착점에 도달하면 가능함으로 판단.
모든 이동을 했는데도 도달을 못하면 불가능으로 판단했다.
시간초과가 나서 해맸는데, visited 연산을 큐에 넣기 전에 하면 중복이 미리 걸러져 더 빠르게 해결할 수 있었다.
11279 최대 힙
최대값이 앞에 저장되는 우선순위 힙 문제였다.
python의 heapq 라이브러리를 이용해서 우선순위에 -value를 넣어주는 방식으로 구현했다.
근데 ❗직접 힙큐를 구현❗해보고 싶었는데 생각처럼 잘 안돼서, 스터디 때 물어보고 다들 못하면 구글링 해보고 해볼 것!!!
11722 가장 긴 감소하는 부분 수열
전에 풀었던 가장 긴 증가하는 부분 수열과 같은 형식이라 호다닥 함. dp 문제
1780 종이의 개수
분할 정복과 재귀 문제..! 저번에 분할정복 풀 때, 인덱스 나눠주는거 헷갈려 했는데 이번에는 잘 정리해서 적절한 범위로 함수 호출 했다.
list.count() 함수를 쓰면 시간 초과 돼서 set에 넣고 원소 갯수로 더 잘라야할지 끝내도 될지 판단했다.
2644 촌수계산
진!!!!짜 많이 해맨 문제. 부모-자식, 자식-부모 모두 각각 딕셔너리를 만들었다.
일단 A의 자식 중에 B가 있는지 dfs를 했다.
다음으론 B의 자식에 A 가 있는지 dfs를 하고, 없을 경우 B의 부모 C를 찾아, B의 subtree가 아닌 C의 subtree만 탐색했다(visited 만들어서)
경우의 수가 사실 그렇게 많진 않은데 귀찮아서 일단 짜야지 하다보니 오히려 더 해맸다. 좀 더 세심하게 테스트케이스를 고민해보고 코딩해야지
10819 차이를 최대로
배열을 만들어
를 최대로 하는 배열을 출력하는건데,, 그게 백트래킹으로 일단 안돼서 itertools.permutations를 써서 했다. n이 얼마 되지 않아 시간 초과는 안됐다.
백트래킹으로 하면 테케는 넘어가는데 6%에서 자꾸 틀린다..
스터디 이후에 ❗백트래킹❗ 해보기
11725 트리의 부모 찾기
dfs를 이용한 백트래킹으로 기본적인 트리 순회 문제라 생각하고 푼듯. 이제 기억도 잘 안나네...
1890 점프
처음엔 dfs bfs문제인줄 알았는데 dp였다.
단순히 우측과 아래로만 이동할 수 있기 때문에 dp로 가능한듯...?
차례로 탐색하면서 이동이 가능한 점에 +1을 해주었고, 마지막 칸이 최종 정답이였다.
10971 외판원 순회2
TSP 라고 Traveling Salesman Problem의 대표적인 알고리즘 이라고 한다.
비용을 계산하는 문제였는데,, ❗백트래킹❗으로 풀고 싶었는데 시간초과가 떠서 permutations로 풀었다. 스터디 가서 물어보기
10451 순열 사이클
딕셔너리를 만들고, 사이클에 포함되는 경우 value를 0으로 바꿔줬다.
dfs처럼 계속해서 key를 value로 바꾸며 검색하다가 value가 0 인 경우 (사이클을 돌아 제자리로 온 경우) 그 사이클을 끝내 줬다.
2504 괄호의 값
괄호고 그냥 스택인데 오지게 안풀림❗❗❗
2004 조합 0 개수
조합의 0의 갯수를 세는건데, 팩토리얼에서 0이 늘어나려면 10이 곱해져야 한다. 팩토리얼 과정에서 2는 충분히 여유롭기 때문에 5의 갯수만 헤아리면 된다고 생각했다.
그래서 n 을 보고 미리 5의 갯수를 계산하는 리스트를 두려고 했는데, 메모리 초과가 됐당 ㅎㅎ.... ❗❗❗❗❗❗
1965 상자넣기
증가하는 최장 수열과 같은 류의 dp 문제
2529 부등호
백트래킹으로는 풀리는데, 0으로 시작하는 경우 어째야할지 모르겠다. 그리고 어차피 제일 큰 값과 제일 작은 값만 알면되서 더 효율적으로 가능할 것 같다. 마지막에 min max연산 하는 거 말고.
그냥 규칙을 찾아서 될 것 같았는데, 규칙으론 왜 안풀리는지 모르겠다 ❗❗❗
15663 N과 M(9)
아직 남았냐?
2407 조합
math.factorial 써서 두둥탁
여기서부터는 골드5
14503 로봇 청소기
이거 그냥 구현 문젠데 왜 못 했지? 저녁 먹고 다시 해봐야지 ❗❗❗❗
14500 테트로미노
테트로미노 만들어둔거 ㅈㅎ오빠랑 똑같은데 시간초과 떠서 화남 ❗❗❗❗❗
10026 적록색약
str.replace 이용해서 bfs
12865 평범한 배낭
저번주 내 담당 골드5 문제.
일반적인 knapsack알고리즘 이였다.
dp의 일종인데 특별한 점이라면, value와 weight를 모두 고려해야 된다는 것
스터디 가기전에 한번 쓱 보고 설명 준비해서 갈 것 💻💻
14891 톱니바퀴
골드5라고 보기엔 무색한 (아니 내가 발전한건가?) 문제
구현 문제였다 애초에. collections.deque 이용해서 rotate했다.
회전 방향을 알아보기 위해 기준을 중심으로 좌, 우로 퍼지며 검사를 하는게 포인트.
근데 어차피 톱니가 4개 뿐이라 하드코딩도 쌉가능 했을듯
꼼지락🐥
'블랙 위도우'를 보고 왔다. 마블 영화 영화관에서 본거 첨인가...? 맨날 티비에서 해주는거 잠깐 본 기억 밖에 없다. 아 그렇진 않구나. 나름 앤트맨이랑 스파이더맨 봤으니까..! ㅋㅋㅋㅋㅋ 블랙 위도우는 외전같은 느낌이 강해서, 스토리의 결말이 속 시원하진 않았다. 평소 워낙 잘 놀라는 편이라 액션영화를 잘 안보는데, 긴장하고 영화를 보다 보니 너무 피곤하다. 저번 주에 본 '크루엘라'가 너무너무 재밌어서 사실 중간에 지루했다ㅎㅎ 나는 디즈니의 영웅들이 더 좋은 너낌,,,, 크루엘라가 영상미랑 노래랑 진짜 다 너무 좋았어서 자꾸 비교된다. 솔직히 크루엘라는 코로나 아니였음 2회차도 쌉가능인딩.. 학원 학생이 블랙 위도우 너무너무 재밌다고 난리여서 기대했는데 아쉽다.
내가 미국에 있을 땐, 할로윈에 여자애들이 다 디즈니 공주님 코스튬을 입었었는데, 요즘에는 저런 여자 히어로도 많이 우상 삼겠다 싶다. 멋지긴 해
그럼 오늘 중국어 공부는 또 미룬 관계로 내일 죽여주겠어 중국어. 하아... 월요일부터는 열심히 살아야지! ㅋㅋㅋㅋ
