코딩테스트

[백준] 스타트와 링크(Python) - 백트래킹

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

[알고리즘] 수학 관련 알고리즘 Code - 에라토스테네스의 체, 유클리드 호제법

기초적인 수학적 알고리즘의 코드를 모아놓은 간단한 포스팅이다! 소수를 구하는 알고리즘과 최대공약수를 구하는 알고리즘! 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. 유클리드 호제법 최대공약수, 최소공배수 구하기 유클리드 호제법은 최대공약수를 구하는 알..

[백준] 로또(Python) - 백트래킹 & 1차원 dfs 탐색

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

[알고리즘] 특정 기준으로 리스트 정렬하기 (python) - key=lambda

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

[백준] 에디터(Python) - Stack

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

[알고리즘] 큐를 이용해 BFS 구현하기 (python)

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