룰루랄라 알고리즘

DFS를 활용한 백트래킹으로 문제를 풀었다. 사실 DFS를 안쓰고 백트래킹 하는 법을 잘 모르겠다. 아무튼 코드가 복잡하다 다른 분이 푼 코드에 비해 현저히 길다. 내가 푼 방식으로 봤을 때 키포인트는 1. 33,34줄에서 방문처리와 pop() DFS를 활용한 백트래킹에서 가장 중요한 부분인것 같다. 2. 56줄 부터 나오는 join int형은 길이를 셀 수 없기때문에 str형태로 바꿔서 max_num의 길이를 측정하고, 리스트에 str로 append해서 str(0) 과 join했다. join은 str형태 밖에 쓸 수 없다. 아래는 다른 사람이 푼 코드를 보고 따라한 방식이다. max_num, min_num을 처음부터 str형태로 저장했다. 위 풀이는 아무리봐도 이해가 안된다. 절대 내가 생각해 낼 수 ..

N개의 정점을 2개의 집합으로 나눌 수 있는 모든 경우의 수에서 연결 요소가 2개인 그래프 찾기 삼성 sw기출문제 왤케 어렵냐 제한 시간이 매우 짧아서 시간초과를 걱정했는데 다행이 빠르게 되네 이게 왜 시간이 빠르지 아마도 값이 작아서 일 듯하다 코드가 내 기준으로 되게 더럽다. 좀 더 간결하고 예쁘게 줄이고 싶은데 푼 걸로 만족하자 bfs를 두번 돌리는게 매우 마음에 들지않는다. 최근 들어 조합, 순열 문제가 꽤 많은 듯 아직 bfs의 개념이 완벽하진 않은것 같다. 문제풀이는 너무 복잡해서 주석으로 대체 했다.

함수로 리스트를 슬라이싱해서 넘기는 발상을 못 해서 삽질한 문제;; 그리고 마지막 출력에서도 삽질 했었는데, 내가 전에 작성한 코드로는 tree가 [ 3, [6, 2], [1, 4, 5, 7] ] 이런 식으로 나와서 26,27 번째 코드가 에러가 났었다. 리스트가 [ [3], [6, 2], [1, 4, 5, 7] ] 이런식으로 모두 2차원이여야 에러가 발생하지 않는듯함 리스트를 슬라이싱하고, 깊이를 재귀함수로 넘겨서 트리의 중위순회를 역순으로 구현한 문제

d[N][K]는 N번째 물건 까지 살펴보았을 때, 무게가 K인 배낭의 최대 가치 이다. 물건을 배낭에 담을 때, 1. 현재 배낭의 허용 무게보다 넣을 물건의 무게가 더 크다면 넣지 않는다. 2. 그렇지 않다면, 다음 중 더 나은 가치를 선택하여 넣는다 2-1) 현재 넣을 물건의 무게만큼 배낭에서 뺀다. 그리고 현재 물건을 넣는다. 2-2) 현재 물건을 넣지않고 이전 배낭 그대로 가지고 간다. 위 과정을 식으로 나타내면 다음과 같다. 현재 담을 물건의 인덱스를 i, 현재 가방 허용 용량이 j, 현재 담을 물건의 무게를 weight, 가치 value라고 할 때, ① j < weight : d[i][j] = d[i-1][j] ② d[i][j] = max( dp[i-1][j], d[i-1][ j-weight[i..

combinations를 이용해 N번 까지의 숫자를 조합 만약 N이 4일 때 case = [ [0,1],[0,2],[0,3],[1,2],[1,3],[2,3] ] case_B = [x for x in range(N) if x not in case_A] 리스트 컴프리헨션을 이용해 case 원소 중에서 case_A 원소를 제외한 리스트

a에서 b로 가는 경로 또는 a가 k를 거쳐 b로 가는 경로가 있다면 graph[a][b] = 1

백준 14888번 내 기준 dfs를 활용한 백트래킹 정석 문제 1. modify 리스트에 연산자의 개수를 저장 2. dfs 함수로 깊이 depth, 총 점수 total, 연산자의 개수를 변수로 넘김 3. 깊이가 N이 될 때 마다 total의 최댓값, 최솟값을 저장하고 함수를 빠져나오면 깊이가 N-1인 다른 dfs 함수가 실행되어 또 다시 total의 최대,최소 판별 4. 이렇게 모든 경우의 수를 백트래킹으로 판별가능

백준 3190번 queue를 이용해 이동방향을 저장하여 꼬리좌표가 이동할 때 마다 popleft 하여 해결