[이코테] 문제3 - 두 배열의 원소 교체(182p) (한줄평) 정렬만 할 줄 안다면 쉽게 해결할 수 있는 문제 풀이 시간: 10분 이내 1) 문제 해결 아이디어 배열의 크기: n, swap 가능 횟수: k 라고 주어졌을 떄 A, B 2가지 배열의 원소를 각각 하나씩 swap하여 만들 수 있는 A의 원소 합의 최댓값을 구하는 문제다. A, B의 원소를 서로 바꿔 A의 원소 합이 최댓값이 되게 하려면 단순하게 A의 작은 수와 B의 큰수를 바꾸는 것을 최대 K번 반복하면 된다. 그러므로 A는 오름차순 정렬, B는 내림차순 정렬하여 0번부터 (k - 1)번 까지 값을 swap하면 된다. 여기서 중요 포인트는 A, B를 각각 정렬 해야함을 떠올리는 것이다. 단, A의 원소가 B의 원소보다 크거나 같으면 굳이 바..
[이코테] 예제3 - 퀵정렬(Quick Sort)(168p) (한줄평) 예제 문제지만 quick sort가 익숙치 않아 복습이 꼭 필요!!! 풀이2는 파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드다. 전통 퀵 정렬의 분할 방식과는 조금 다른데, pivot과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간면에서는 조금 비효율적이다. 하지만 더 직관적이고 기억하기 쉽다는 장점이 있다. (풀이1) 일반적인 코드 풀이 시간: 30분 이내 1) 문제 해결 아이디어 Pivot(기준)을 설정하여 정렬을 수행한 후 Pivot을 기준으로 왼쪽 리스트, 오른쪽 리스트에서 각각 정렬을 수행(왼쪽: pivot보다 작은 수들, 오른쪽: pivot보다 큰 수들) 1. 리스트의 원소가 1개인 경우 종료 2. Pivot(기..
[이코테] 예제2 - 삽입 정렬(Insertion Sort)(164p) 풀이 시간: 1) 문제 해결 아이디어 정렬된 데이터 리스트에서 적절한 위치를 찾은 뒤에 그 위치에 삽입 (첫번째 데이터는 정렬되어있다고 가정, 2번째 데이터부터 정렬 시작) 평균 시간 복잡도: O(n**2) 공간 복잡도: O(n) 2) 소스코드 # 선택 정렬(Insertion Sort) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] # 오름차순 정렬 # 1번 인덱스부터 시작 for i in range(1, len(array)): # 0 ~ i 인덱스 정렬 for j in range(i, 0, -1): # 현재값이 왼쪽값보다 크면 탈출 if array[j] > array[j - 1]: break # 현재값이 왼쪽..
[백준] 12100번 - 2048 (Easy) 풀이 시간: 6시간 이내 (한줄평) 내 설계대로 구현이 잘 되지 않아 다른 사람의 풀이를 참고했음에도 어려웠던 문제 상하좌우 이동 부분이 구현을 하기가 굉장히 까다로워 변수/조건이 조금만 달라져도 오류를 고치다 늪에 빠져버린... 추후 처음부터 끝까지 전체 코드를 직접 짜봐야할 문제!! 1) 문제 해결 아이디어 이 문제는 이동을 통해 변경된 정보를 담아둘 2차원 리스트(temp)를 깊은 복사를 통해 생성하는 것이 중요하다. 3번에서 1) move 함수로 2차원 리스트(temp)를 변경하고 2) dfs를 호출하고 3) 2차원 리스트(temp)를 원상복귀해준다 는 흐름이 중요하다!! 잊지말자 절대~~~ 1. 깊이(depth)가 5이면 5번 이동했다는 것이므로 2..
[백준] 10971번 - 외판원 순회 2 (한줄평) 설계자체는 단 시간에 했지만 시간초과를 해결하는데 시간이 오래걸렸던 문제로 꼭 복습 필요한 문제!! 이 문제는 외판원 순회 문제(TSP)로 N과 비용행렬이 주어졌을 때 외판원 순회에 필요하 최소 비용을 구하는 것이다. 1 ~ N 번호가 매겨진 도시들을 모두 거쳐 원래의 도시로 돌아오는 순회 여행을 말한다. 완전탐색(백트래킹)문제로 DFS를 이용하여 풀 수 있다. 풀이 시간: 90분 이내 1) 문제 해결 아이디어 1. 비용(graph) 입력 및 이동 경로(temp), 방문 여부(visited)를 저장할 리스트 생성 2. dfs(0, 0) 호출 -> 깊이= 0, 비용= 0으로 시작 3. n개 도시를 다 선택했고 마지막 도시→처음 도시로 가는 비용이 0이 아..
[백준] 14889번 - 스타트와 링크 (한줄평) 아이디어를 떠올리고 구현하는 것은 어렵지 않았으나 시간단축을 위한 방법을 고민해봐야했던 문제! 1 ~ N 번호를 가진 사람들이 있을 때 두 팀으로 나누었을 때 각 팀의 능력치(팀에 속한 모든 쌍의 능력치의 합)의 차이의 최솟값을 구하는 문제였다. 두 팀으로 나눌 수 있는 모든 경우의 수를 따져봐야하는 완전 탐색(백트래킹)문제로 DFS를 이용하여 풀 수 있다. 물론 조합을 구할 때 combinations 라이브러리를 사용할 수도 있다. 여기서 풀이 1, 2 둘다 DFS를 이용하여 구현했고 설계방식에 조금 차이가 있는데 풀이2가 메모리, 시간 측면에서 더 효율적이므로 풀이2를 추천한다. (풀이1) 내 풀이 풀이 시간: 30분 이내 1) 문제 해결 아이디어 이..
[백준] 2580번 - 스도쿠 풀이 시간: 70분 이내 (한줄평) 어렵진 않았으나 오류를 고치는데 시간이 걸린 문제. 한번쯤 복습 필요!! 스도쿠는 어렸을 때부터 많이 해봤기 때문에 딱히 아이디어를 떠올릴 필요가 없이 쉽게 구현할 수 있었다. 다만 나의 고정관념으로 인해 생긴 문제들때문에 오류를 고치느라 시간이 좀 걸렸다. (풀이1) DFS를 이용한 시간초과, 틀렸습니다 실패 코드 1) 문제 해결 아이디어 첫번째 오류. 시간 초과 1. Python3으로 제출하였더니 5%까지 되다가 시간초과가 떴다. 2. PyPy3로 제출했더니 11%까지 되다가 시간초과가 떴다. 3. target을 리스트 대신 집합으로 선언하고 discard()를 썼지만 여전히 11%까지 되다가 시간초과가 떴다. 4. graph를 tem..
