본문 바로가기
728x90

전체 글63

[알고리즘] 크래프톤 정글 3주차 / 알고리즘 中 혼자서 못 푼 문제 정리 8(행렬 곱셈 순서) BOJ 11049 행렬 곱셈 순서 난이도 : (크래프톤 정글 기준) 중, (백준 난이도 기준) 골3 사용 알고리즘 or 자료 구조 : 다이나믹 프로그래밍(DP) 처음 생각한 풀이 드디어 고대하고 걱정했던 다이나믹 프로그래밍을 푸는 주간이 와버렸다... 정글에 들어오기 전부터 알고리즘 공부를 계속 하긴 했지만 아무리 해도 DP는 익숙해지지도 않고 감도 안와서 가장 걱정했었는데 걱정했던 대로 겁나 어렵다... 사실 솔직히 말하면 2시간 동안 온갖 방법을 생각하면서 점화식을 찾으려 노력했지만 예제 문제조차 맞게 나오는 방법을 떠올리지 못했다. 결국 동료의 도움을 받아 CLRS(둔기 알고리즘 책 => 학교 다니면서도 이런 책은 본 적이 없다)에 DP 파트에 이 문제에 관한 부분이 있다는 것을 듣고 읽어보려 했지.. 2024. 4. 5.
[알고리즘] 크래프톤 정글 2주차 / 알고리즘 中 혼자서 못 푼 문제 정리7(임계경로) BOJ 1948 임계경로 난이도 : (크래프톤 정글 기준) 상, (백준 난이도 기준) 플5 사용 알고리즘 or 자료 구조 : 위상정렬, 그래프 이론 처음 생각한 풀이 이전 문제인 그래프 수정을 접근법을 안보고 풀기도 했고, 백준 기준 난이도가 더 어려워서 솔직히 물로 봤다. 그도 그럴게 그래프 수정은 플4고 이거는 플5이기도 하고 문제를 이해하는게 더 쉬웠고 접근 방법도 더 쉬워보였기 때문이다. 하지만 그렇지 않았다. 처음에는 단순히 각 노드 별로 걸린 시간과 경로를 저장해놓는 배열을 선언하여 위상정렬을 하는 과정에서 해당 데이터를 이용하여 다음 노드에 데이터를 저장하는 식으로 풀었다. 하지만 지금 생각해보면 도시의 개수는 최대 10,000개, 도로의 개수는 최대 100,000개 였기 때문에 메모리가 터.. 2024. 4. 3.
[TIL] 크래프톤 정글 2주차 - 자료구조(B-Tree) 알고리즘 주간에는 그래도 전공자고 밖에서도 알고리즘 공부를 꾸준히 해왔기 때문에 따로 공부를 할 필요가 없다고 생각했는데 갑자기 공부 키워드로 밖에서 쓴 적이 없어 기억에서 사라진 B-Tree가 있었다.. 그래서 B-Tree를 아주 자세히까지는 아니어도 어떤 자료 구조이고 어떤 곳에서 쓰이고 왜 쓰는지, 어떤 방식으로 쓰이는 지 등을 간략하게 공부하고 정리했다. B-tree의 구성 요소 1. entry entry는 일반 트리에서의 노드와 같다. entry는 data와 rightptr(오른쪽 자식을 향하는 포인터)를 가지고 있다. 2. node node는 일반 트리와 다르다. node는 firstptr(왼쪽 자식을 향하는 포인터), numEntries(노드에 속하는 entry의 개수), entry(arra.. 2024. 4. 1.
[알고리즘] 크래프톤 정글 2주차 / 알고리즘 中 혼자서 못 푼 문제 정리6(장난감 조립) BOJ 2637 장난감 조립 난이도 : (크래프톤 정글 기준) 중, (백준 난이도 기준) 골2 사용 알고리즘 or 자료 구조 : 위상정렬 / DP 처음 생각한 풀이 탑다운 방식으로 최종 제품을 1개 만드는 데 필요한 중간 부품 및 기본 부품들의 개수를 미리 선언해둔 리스트에 더해가며 최종적으로 완성된 리스트에서 indegree가 0인 것들만 출력하는 방식으로 푸는 것이라고 생각했다. 그런데 왜인지는 모르겠지만 계속해서 메모리 초과가 떴고, 도대체 왜 그런거지 하고 접근법을 찾아봤다. 사실 접근법을 찾아보니 접근법의 방식들이 메모리 초과가 안 날 만하다고 생각은 들지만, 여전히 원래 방식이 왜 메모리 초과가 나는 지는 이해가 가지 않는다. 구글링 이후 풀이 일단 DP를 사용하는 방법이다. 탑다운, 바텀업 .. 2024. 4. 1.
[알고리즘] 크래프톤 정글 2주차 / 알고리즘 中 혼자서 못 푼 문제 정리5(미로만들기) BOJ 2665 미로 만들기 난이도 : (크래프톤 정글 기준) 중, (백준 난이도 기준) 골4 사용 알고리즘 or 자료 구조 : DFS / BFS 처음 생각한 풀이 처음 생각한 방법은 단순 BFS를 돌려서 최단 경로에서 뚫는 벽의 수가 답일 것이다! 라고 생각하여 구현했었지만, 다 하고 생각해보니 최단 경로는 벽의 수랑 관계 없다는 것을 깨닫고 코드를 갈아엎었다. 두번째 생각한 방법은 도착점까지 모든 경로에서 뚫는 벽의 수를 비교해서 최솟값을 구하는 방식이었는데 당연하게도 모든 경로의 수를 세면 경우의 수가 기하급수적으로 많아져 deque를 써도 메모리가 터질 정도로 데이터가 저장되어 데이터 초과가 떠서 오답 처리가 되었다. 사실 지금 생각해보면 조금만 더 곰곰히 생각해봤다면 충분히 구현 가능할 만한 난.. 2024. 4. 1.
[알고리즘] 크래프톤 정글 2주차 / 알고리즘 中 혼자서 못 푼 문제 정리4(아침 산책) BOJ 21606 아침 산책 난이도 : (크래프톤 정글 기준) 중, (백준 난이도 기준) 골3 사용 알고리즘 or 자료 구조 : DFS / BFS 처음 생각한 풀이 단순히 node와 edge가 tree형태로 주어지니까 당연히 실내 전체 순회를 돌며 실내에서 시작해서 다음 노드가 실외라면 dfs를 한번 더 실행하고 실내라면 dfs를 마치고 답을 +1 시켜주는 것으로 생각하고 풀었더니 서브 태스크의 제한조건을 모두 만족하지 못하고 시간초과가 떠버렸다. 시간 초과가 뜨는게 당연한 게 2번 같은 경우에는 edge가 상당히 많아 dfs를 굉장히 많이 호출하여 시간 초과가 안나도 메모리 초과가 뜰 것인게 당연하고, 5번의 경우에도 마찬가지일 것이다. 그럼 이걸 어떻게 풀어야할까? 생각해봤지만 도무지 떠오를것 같지 .. 2024. 4. 1.
728x90

티스토리툴바