룰루랄라 알고리즘

삼성 sw 역량테스트 기출문제 문제를 이해 하는게 푸는 것 보다 더 어려웠다 하라는 대로만 충실히 하면 풀리는 문제인듯. 43~48줄인 후진하는 코드에서 시간이 좀 걸렸는데 다른 분의 풀이를 보니까 그냥 nx = x - dx[d] ny = y - dy[d] 이런 식으로 했는데 내가 봤을 때 직관적이지도 않고 이해가 되지않아서 좀 지저분하지만 내 방식대로 풀었다. dx,dy 리스트의 방향 순서를 문제에서 준 대로 바꿔야 하는게 핵심인 듯 하다. 리스트의 인덱스를 +1 했을 때 보고 있던 방향의 왼쪽을 향하게 하는 순서대로 짜야지 문제를 풀 수 있다.

리스트를 잘라서 수열이 일치하는지 여부를 확인하는게 주요했던 문제 처음에는 아래 코드 처럼 백트래킹을 사용하지 않고 while문을 통해 나름대로 규칙을 세워서 시도 했었는데 백트래킹을 쓰지 않고는 풀 수 없는 문제인걸 깨닫고 다시 백트래킹 코드로 고쳤다.

처음에 이진 탐색으로 stack에 있는 값을 찾지 않고 아래와 같이 in을 써서 탐색 했다가 시간초과에 걸렸다. N,M이 각각 500,000 이하의 큰 수 임을 생각하지 못했다. 값이 큰 리스트를 탐색 할 때는 이진 탐색을 생각해보자

여태까지 중에 백준에서 가장많이 틀리고 다시 시도한 문제 내가 생각한 방식에 대한 믿음을 가지고 풀어야 풀리는 듯. 증명하라고 하면 절대 못할 것 같다. 풀이방식 1. 처음에 플러그가 다 채워질 때까지 장비를 꽂는다. 2. 이미 꽂혀있는 장비라면 건너뛴다. 3. 플러그가 다 꽂혀있고 이미 꽂혀있지 않은 장비라면 3-1. 후에 다시 쓰지 않는 장비를 빼고 그 자리에 꽂는다. 3-2. 다시 쓰지 않는 장비가 없다면 가장 나중에 쓰는 장비부터 빼고 그 자리에 꽂는다. 처음에는 나중에 쓰는 장비의 빈도수를 계산해서 가장 적게 쓰는 장비부터 빼면 된다고 생각했는데 이건 틀렸다. 그 이후에도 자잘하게 놓치는 부분이랑 인덱스 계산 오류 등등 실수가 많았다. 매우 까다로운 문제.

무작위 좌표 3개를 어떻게 구성할지 고민하다가 중복순열 prodct 라이브러리를 활용해 풀었다. 조건 중에 꽃이 벽을 넘어서면 안된다고 제시 했기 때문에 좌표를 1~N-1로 제한 했다. for문과 함수호출을 많이 하는 코드라서 시간 초과가 나오지 않을까 걱정했는데 느리긴 하지만 시간내에 통과했다. 21~28줄의 예외처리 코드를 작성하지 않고 제출해 틀렸다가 수정했다. 비용이 모두 0이면 0을 출력해야 하는데 result에 초기 설정된 최댓값이 출력되어 수정했다.

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 원소를 제외한 리스트