Algorithms 💻/BAEKJOON

[백준] 치킨배달(Python) - 구현 & 백트래킹

# 문제 문제가 언뜻 보면 복잡해보이지만, 사실 M개의 치킨집을 선택하는 최적의 입지를 구하는 문제다. 여기서 최적의 입지의 기준이란 각 집으로부터 "치킨거리"의 합이 가장 작아지는 M개의 치킨집을 고르는 경우를 구하는 것 ! "치킨거리"를 구하는 공식 또한 인덱스를 기준으로 하기에 그렇게 어렵지 않다. # 입출력 # Idea # Code 우선 이 문제는 구현과 백트래킹으로 풀 수 있으므로, 구현으로 푸는 방법을 먼저 소개하겠다. itertools의 combination 함수를 이용하면 쉽게 구현 가능하다. """ 치킨 배달 - Combination으로 먼저 풀기 """ from itertools import combinations # 해당 치킨집 조합과 1들의 거리를 리턴하는 함수 def distanc..

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

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

[백준] N-Queens 문제(Python) - 백트래킹

# 문제 즉, 상하좌우 대각선으로 이동하는 N개의 퀸을 서로 부딪히지 않도록 배열하는 방법 수를 리턴하는 문제이다. 백트래킹의 전형적인 문제 유형이라고 한다. 아래의 예시처럼 말을 놓는 경우의 수는 하나의 경우의 수가 될 것이다. # 입출력 # Idea 우선 해당 문제는 백트래킹 문제로, DFS 방법으로 문제를 푸는 방법을 고안할 수 있다. (백트래킹에 대해 궁금하신 분들은 여기를 참고!) 특히 이 문제를 처음 봤을 때, 나는 다음과 같이 DFS노드를 뻗으면 어떨지 생각을 했다. 각 raw별 좌표를 노드로 놓고, Depth는 raw 단위가 되도록 노드를 뻗는 것이다. 특히 백트래킹은 유망한 노드(정답이 될 가능성이 있는 노드)이면 계속 DFS 탐색을 하고, 그렇지 않으면 탐색을 멈추고 위 depth의 노..

[백준] 1,2,3 더하기(Python) - 백트래킹 & 1차원 dfs 탐색

# 문제 # 입출력 # Idea 이전 문제처럼 1차원 dfs를 이용하는 문제라고 생각했다. 그 이유는 오직 1, 2, 3으로 이루어진 노드의 그래프를 n depth만큼 뻗으면 되는 1차원 dfs로 접근했기 때문이다. 특히, 오직 매번 depth의 노드가 1,2,3으로 이루어지기 때문에 이전 문제와 달리 visited 체크를 하지 않아도 된다고 생각했다. 이러한 아이디어를 그림으로 구체화하면 다음과 같다. 따라서 만약 위 빨간색 경로의 dfs를 탐색한다면, depth가 깊어질수록 나오는 노드를 점차 cur_sum이라는 변수에 더해서, 만약 cur_sum이 n과 같다면 최종 count를 저장하는 변수에 1을 더하고 재귀함수를 탈출하도록 하면 된다. 그리고 만약 count에 1을 더하고 탈출했다면, 이전 de..

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

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

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

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

[백준] 캥거루 세마리2 (Python) - Greedy

# 문제 캥거루 세 마리가 사막에서 놀고 있다. 사막에는 수직선이 하나 있고, 캥거루는 서로 다른 한 좌표 위에 있다. 한 번 움직일 때, 바깥쪽의 두 캥거루 중 한 마리가 다른 두 캥거루 사이의 정수 좌표로 점프한다. 한 좌표 위에 있는 캥거루가 두 마리 이상일 수는 없다. 캥거루는 최대 몇 번 움직일 수 있을까? # 입출력 # Idea 이 문제의 가장 중요한 부분은 "최대 몇 번 움직일 수 있는지" 출력해야한다는 것! 이러한 조건 때문에 아래와 같은 만족해야할 두가지 필요충분조건이 생긴다. 1. 초기 위치 A, B, C 중에서 바깥 A, C 중 이동해야할 element를 정할 때는 A&B와 B&C 사이의 거리의 대소를 정해야한다. 2. 만약 A가 이동하기로 했다면, B와 C의 사이 중 B나 C의 바로..

[백준] 우유축제 (Python) - Greedy

# 문제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후에는 초코우유를 한 팩 마신다. 초코우유를 한 팩 마신 후에는 바나나우유를 한 팩 마신다. 바나나우유를 한 팩 마신 후에는 딸기우유를 한 팩 마신다. 영학이는 우유 축제가 열리고 있는 우유거리에 왔다. 우유 거리에는 우유 가게들이 일렬로 늘어서 있다. 영학이는 우유 거리의 시작부터 끝까지 걸으면서 우유를 사먹고자 한다. 각각의 우유 가게는 딸기, 초코, 바나나 중 한 종류의 우유만을 취급한다. 각각의 우유 가게 앞에서, 영학이는 우유를 사마시거나, 사마시지 않는다. 우유거리에는 사람이 많기 때문에 한 번 지나친 ..