문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/131127 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 풀이 from collections import Counterdef solution(want, number, discount): answer = 0 dict = {} for i in range(len(want)): dict[want[i]] = number[i] for i in range(len(discount) - 9): cnt = C..
코딩테스트
문제 링크 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 문제 풀이 root에 따라 서브쿼리 노드의 개수가 달라지기 때문에 루트노드부터 순차적으로 서브쿼리를 구해나가야 합니다. 특정 노드가 루트가 될 때 그 하위에 포함된 노드들에 대한 서브 쿼리를 구해나가야 하는데 재귀를 통해 각 노드들이 루트 노드가 될 때 하위 노드의 개수를 가장 말단 노드까지 구해줍니다. 예를 들어 위 상황..
문제 링크 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 문제 풀이 트리는 사이클이 없는 연결 요소입니다. 결국 반대로 사이클을 판별하여 트리가 아닌 것들을 찾아내면 문제를 해결할 수 있습니다. 한 노드씩 순차적으로 확인하되 이전에 방문하지 않은 노드들을 확인합니다. find_cycle(start) 함수는 사이클이 존재할 경우 flag에 True를 담아 반환하고 해당 사이클에 존재하는 모든 노드의 방문 처리 배열 값을 1로 ..
문제 링크 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 풀이 간단한 이분탐색 문제 같지만 생각할 예외가 있는 문제였습니다. 처음에는 단순히 배열을 정렬한 후 초기 start를 0, end를 현재 확인하고 있는 인덱스의 앞까지로 해서 이분탐색을 진행하면 되지 않을까 했습니다. 하지만 이렇게 할 경우 아래 테케와 같이 동일한 숫자가 여러 개일 경우 문제가 발생합니다. 4 0 0 0 0 1번 0은 뒤에 있는 0들을 더해서 만들 수 있는 숫자임에도 인덱스 범위로 인해 만..
문제 링크 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 풀이 LIS 알고리즘은 보통 dp를 사용해서 수열의 길이를 갱신하는 방식으로 구현하며, 시간복잡도는 O(n^2)가 됩니다. 이 문제에서는 수열의 길이가 100만까지로 크기 때문에 기존 방식을 활용하면 시간 초과가 나게 됩니다. 시간을 단축하기 위해 이분 탐색을 활용하여 알고리즘을 구현할 수 있습니다. 이 경우에는 O(nlogn)의 시간복잡도를 띄게 됩니다. 알고리즘 방식은 다음과 ..
문제 링크 https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 문제 풀이 처음에는 유효하지 않은 경우를 가지치기 하는 방식으로 풀이하려 했지만, 생각보다 예외 케이스가 많았습니다. 이에 따라 유효한 케이스를 먼저 가지치기하는 방식으로 풀이했습니다. 게임판의 상태가 최종 상태일 경우 유효하다고 반환해야 합니다. 최종 상태로 가능한 경우는 이긴 플레이어를 기준으로 총 3가지로 세웠습니다. 1) X가 이긴 경우 : X의 개수가 O의 개수보다 1 많아야..
문제 링크 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 풀이 import heapq def dijkstra(i, j): global result q = [] heapq.heappush(q, (0, i, j)) visited[i][j] = 1 distance[i][j] = 0 while q: cnt, x, y = heapq.heappop(q) if x == n - 1 and y == m - 1: result = mi..
문제 링크 https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 문제 풀이 문제를 따라가며 조건에 맞게 구현해나가면 어렵지 않게 풀 수 있습니다. 다소 비효율적으로 푼 것 같기도 하지만 주어진 숫자 범위가 매우 작아 시간적인 문제는 없었습니다. 저는 세 개의 함수로 나누어 풀이했습니다. 1) 모눈종이를 붙일 수 있는지 여부를 확인하는 함수 def check(r, c, sticker, start_x, start_y): for x in range(r): ..
