본문 바로가기

알고리즘['파이썬','JavaScript']26

구름톤 챌린지 4주 day16 학습 일기 [문제 상황] 탐색할 때 if child in graph[parent]: 이 부분이 시간을 가장 많이 소비했고, 일부 케이스는 시간초과가 발생했다. 되짚어 봤을 때 graph를 2차원 배열로 선언했을 때가 문제의 원인일거라 생각했고 graph = [ [] for _ in range(N+1) ] graph의 내부를 배열 대신, set으로 바꿨다. 예시에서 최악의 경우를 가정했을 때, in 구문에서 시간복잡도가 대폭 증가할 것 같았다. 두가지 정도 간단하게 떠올려 봤을 때 1. graph = [ [] for _ in range(N+1) ] 로 하되, heap 또는 deque를 사용할지 2. set을 사용해서 탐색하는데 시간을 줄이기 였는데, heap을 사용하더라도 pop을 할 때 작은 순으로 정렬되어 있더라.. 2023. 9. 4.
LCS (DP) 유튜브의 Chan-Su Shin 교수님 강의중 알고리즘 - 동적계획법 - LCS 문제 영상을 보고 정리한 내용입니다. 이해가 어려웠던 분들은 꼭 참고해보세요 LCS 백준 문제의 풀이를 봤을 때 이해하기 어려웠던 부분 (1) 2차원 테이블 정의도 이해하기 어려웠고 (2) [i-1][j-1] 부분도 이해하기가 어려웠다. 2차원 배열 LCS 데이터를 표현할 수 있는 방법이 2차원 배열이었다. 0 B D C A B A 0 A B C B D A B 위 표는 문자열 2가지를 나타내는 2차원 배열이다. 여기서 반드시 짚고 넘어가야 할 부분! 1. 위의 표에서 각 문자 1개는 가장 마지막 문자를 나타낸다. 2. 그리고 채워야 하는 빈 칸은, 해당 문자까지의 문자열 LCS를 의미한다. 예를 들어, ABCBDA와 BDCA.. 2023. 9. 2.
구름톤 챌린지 3주 day15 학습 일기 남은 금액 안에서, 과일 당 조각을 몇 개 구매할 수 있는지를 파악하는 문제 정렬된 배열을 순회할 것이기에, heapq로 최대힙을 활용했다. [1개당 포만감, 가격(=해당 과일의 최대 조각 수)] 으로 heap에 삽입 (1) 첫번째 요소가 개당 포만감인 이유 1개당 가격이 1원으로 동일하다. 따라서 1원(1개)당 포만감이 큰 과일을 먼저 구매하기 위해서였다. (2) 두번째 요소가 가격인 이유 실제로 입력으로 들어온 P값을 넣어주었고, 가격이라고 표현했다. 하지만 한 조각의 가격이 1원이기 때문에, 과일 하나는 P개 만큼의 조각을 갖고있다. 따라서 과일의 최대 조각 개수를 의미한다. 남은 돈 내에서 구매 가능한 최대 조각 수를 구하기 위해 두번째 요소로 사용 (3) 첫번째에 포만감을 넣고 두번째에 가격을 .. 2023. 9. 1.
구름톤 챌린지 3주 day14 학습 일기 방문할 수 있으면서, 번호가 가장 작은 노드를 방문하는 부분에서 두가지 방법으로 풀이를 해보았다. 1. child 노드를 배열로 다 받은 뒤, parent 노드를 순회하면서 child 노드 배열을 sort() 2. child노드 배열을 heapq(최소힙)으로 구성 실행 시간에 미세한 차이가 있기는 했다. 그리고 최소힙에서 pop을 할 때, indent를 너무 들여쓰지 않기 위해 (어제 배운) 코드를 작성했는데 하지만 추가된 코드로 인해 코드가 길어진 측면이 있다. 힙을 사용하지 않고 sort() 후에, 반복문으로 조건에 맞는지 확인하는 방법이 코드를 작성하거나 읽는데는 좋은것 같긴 한데 만약 정렬에 소요되는 시간도 줄여야 한다면 힙을 사용 할 수도 있을 것 같다. 다만 파이썬 heapq를 사용하며 주의해.. 2023. 8. 31.
구름톤 챌린지 3주 day13 학습 일기 발전기 문제에서 발전된 문제 이제는 (1) 건물 유형에 따라 (2) K개 이상의 동일 건물 유형이 있는, 연결된 건물들을 '단지'라고 정한다. M(r,c)데이터를 저장하기 위해 M = [ 0 for _ in range(31) ] 로 지정해서, 1부터 30까지에 해당하는 건물 유형인 M(r,c)를 인덱스로, 단지 수를 배열의 요소로 저장했다. 배열로 만든 이유는, M 배열에서 가장 큰 요소를 찾아야 하는데 요소간 중복이 가능하다 그런데 출력 조건이 같은 값이면 건물 유형인 M(r,c)의 크기가 큰 것을 출력해야 한다. 따라서, 인덱스 역방향으로 탐색을 하는게 편할 것 같았다. => max() 내장함수로 값을 찾은 뒤, 값과 똑같은 요소를 가진 인덱스를 출력 [배운점] 마무리 후에 Q&A 게시판을 봤는데, .. 2023. 8. 30.
구름톤 챌린지 3주 day12 학습 일기 ..답이.. 왜 2지? 처음 문제를 읽었을 때, 풀이 과정에서 발전기 위치를 지정해줘야 하는 것으로 생각해서 2개를 열심히 배치해보았지만 최소 3개가 필요한데.. 왜 2일까.. 하는 의문과, 이걸 찾을수가 있는건가? 이진탐색으로 최소 개수를 접근해도.. 배치하는 위치를 전부 고려하는게, 1,000,000,000 안에서 가능한걸까? 너무.. 어렵지 않나..? 하는 생각을 하면서 무언가 잘못 이해했다는 것을 알았다. [제대로 이해한 내용] 해당 지점에 집이 있지만 발전기가 없어도, 그 집의 상하좌우 집 중 하나에 '전력을 공급받고 있다면' 해당 지점도 전력이 공급된다. 결국 발전기가 있는 집과 딱 붙어있지 않아도 된다는 의미. bfs 문제풀이 이렇게 집들이 이어져있기만 한다면, 이어진 집들 중 한 집만 발전.. 2023. 8. 29.
구름톤 챌린지 3주 day11 학습 일기 다이나믹 프로그래밍, Bottom-up 풀이 [미숙했던 점] dp 초기화 dp = [ 0 for _ in range(N+1)] 배열을 이렇게 초기화 했는데, 아이템의 통증 감소 범위와 통증의 수치 관계를 점검하지 못했다. A 2023. 8. 28.
구름톤 챌린지 2주 day10 학습 일기 앗 처음으로 실패가 뜬 문제..! 실패의 원인 1. 목적지를 방문했는지 여부를 체크하는 것이 아니라, 목적지까지 이동하다가(+1, +1, +1 ... ) 그 과정에서 방문한 곳이 있다면 중단하는 것. => 지문이 수정되기 전에 풀긴 했지만, 지문이 수정되고 나서는 지시하는 바가 명확해졌다. 2. N의 크기가 10 이상인 경우를 고려하지 못함. count, commnad를 분리해야 했는데, 분리하는 기준을 잘못 세워서 RuntimeError 발생. 언제나 일반화 가능한 코드를 설계하자 잘 수행하지 못한 부분은 오답노트에 정리하기 오늘의 학습일기 끝 2023. 8. 25.
구름톤 챌린지 2주 day9 학습 일기 2023. 8. 24.

티스토리툴바