# 문제 문제가 복잡해 보일 수 있지만, 사실 아래와 같은 diagonal 하게 대칭인 능력치 행렬이 주어지면, 두 팀의 능력치 차이가 최소가 되도록 팀을 나누고, 그 최소값을 반환하는 문제이다. # 입출력 # Idea 이 문제는 생각보다 이해하기도, 아이디어를 생각하기도 어려웠던 문제다. 그럼에도 불구하고 내가 문제를 풀 때부터 계속 들었던 생각은 능력치 행렬은 대각선 대칭 행렬이라는 것! 이 점을 잘 이용하고 싶었는데, 풀이과정이 잘 생각나지는 않았다. 따라서 이 문제는 아래와 같은 아이디어로 접근하면 된다. 우선 내 가장 큰 고민은 DFS의 노드로 어떤 것을 넣을까였는데, 1부터 N까지 담긴 노드를 그냥 생성하고 이들로 visited 여부를 체크해 팀을 나눈다고 생각하면 편하다. 위 그림에서 노란색..

기초적인 수학적 알고리즘의 코드를 모아놓은 간단한 포스팅이다! 소수를 구하는 알고리즘과 최대공약수를 구하는 알고리즘! 1. 에라토스테네스의 체 소수를 구하는 알고리즘 특정 배수를 지워가는 식으로 전개된다. def era(n): """ Input : 몇까지 탐색할지 Output : n까지 숫자 중 소수를 포함한 리스트 """ a = [False, False] + [True] * (n-1) primes = [] for i in range(2, n+1): if a[i]: primes.append(i) for j in range(2*i, n+1, i): a[j] = False # 배수를 지운다! return primes 2. 유클리드 호제법 최대공약수, 최소공배수 구하기 유클리드 호제법은 최대공약수를 구하는 알..

# 문제 단순히 combination을 구하는 것 같은 아주 간단한 문제이지만, 사실 dfs로 풀어야 진가를 볼 수 있는 문제이기도 했다! # 입출력 K가 집합 S에 포함되는 수의 개수인데 생각보다 6에서 13 사이이면 작은 범위라고 생각했다. 그래서 처음으로 itertools 모듈을 고려하게 된 것 같다. # Idea 처음에는 앞서 언급한대로 from itertools import combinations 을 사용했다. 범위가 작게 주어졌다고 생각했기 때문이다. 이런 방식으로 구한 답도 맞았지만, 이 문제는 백트래킹 단원의 문제인 만큼 dfs로 접근하는 것이 중요한 문제였던 것 같다. 사실 이제 dfs는 좀 익숙한 상태였는데, 모두 2차원 그래프를 대상으로 한 dfs 문제를 풀이했었다. 그래서 이 문제는..

요즘 정렬 문제를 많이 풀다보면, 리스트를 특정 기준으로 정렬해야할 때가 많다. 단순히 .sort(), sorted()로의 오름차순 내림차순으로는 풀 수 없는 문제도 많이 만났고, 이럴때는 key=lambda 함수를 사용하면 된다! 오늘은 이러한 용법에 대해 포스팅 해보도록 하겠다. :) 이 게시글은 여기를 참고하였다. # key=lambda 용법 우선 key=lambda 용법은 sorted 함수의 인자로 쓰인다. 그리고 다음과 같이 사용한다. # key가 하나일 때 모든 정렬의 기반은 오름차순 정렬이다. ex 1) 리스트의 각 원소를 기준으로 정렬하기 (일반 오름차순) 참고로 문자열을 다음과 같이 정렬하면 사전순으로 정렬이 된다. arr = ['abc', 'bac', 'bca'] sorted(arr, ..

# 문제 # 입출력 # Idea 스택을 이용한 문제다. 이 문제의 특징은 주어진 시간제한이 매우 짧기 때문에, insert와 pop(i) 등을 사용해서는 시간복잡도가 커지기 때문에 사용할 수 없다. (시간초과가 뜬다) 그래서 pop()와 append()만을 이용해 스택으로 구현해야한다. 그렇다면 이 문제를 어떻게 스택으로 구현하느냐? 필자는 처음에 각각의 L, D, B, P 경우를 하나하나 스택으로 구현할 수 있도록 경우를 생각했는데, 이럴 경우에 예외처리가 너무 복잡하고 까다로워져서 난항을 겪었다. 따라서 이 문제의 핵심 아이디어는 커서의 위치를 기준으로 데이터를 두개의 스택으로 나누는 것이다! 처음에는 하나의 스택에 데이터를 모두 몰아넣는다. 그리고 앞서 언급한 pop과 append의 스택 연산을 이..

오늘은 BFS 구현에서 주로 사용하는 큐에 대해 포스팅하고, 관련 적용 사례를 복습해보려고 한다. 사실 BFS/DFS 문제를 풀다보면 나는 DFS에 훨씬 더 익숙해서, DFS로 주로 풀이를 한다. 그 이유가 BFS 구현에서 큐에서 막히기 때문이라고 생각했고, 관련 포스팅을 하게된 것이다! # 큐(Queue) 우선 큐는 쉽게 말해서 다음과 같은 선입선출 구조이다. 먼저 들어온 요소가 먼저 나가는, 그런 것이다. BFS(너비우선탐색) 구현에는 큐를 이용하는 것이 정석인데, 그 이유는 BFS는 인접한 노드부터 차례로 넓게 탐색하는 알고리즘이기 때문이다. (BFS에 대해서는 따로 설명하지 않겠다) Python에는 친절하게도 deque 라이브러리가 존재해서, 큐 자료구조를 이용하고 싶을 때는 관련 라이브러리를 다..