본문 바로가기

알고리즘/백준

 (64)
[BOJ] [Python] 1316 : 그룹 단어 체커 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만 1을 출력하면 된다. # ord('a') == 97 num = int(input()) result = 0 for _ in range(num): string = input() dp = [0] * 26 tmp = string[0] for s in string: if dp[ord(s) - 97] == 0: dp[ord(s) - 97] = 1 else: if tmp != s: result -= 1 break tmp = s result += 1 print(result) 아스키코드를 활용했다. 주의할 점은 2번 이상 나온 문자에 대한 처리이다. 예를 들어보자. 예) abcc 마지막에 있는 c는 연속해서 나온 문자이기 때문에 통과이다. 예) a..
[BOJ] [Python] 1764 : 듣보잡 듣도 보도 못한 사람의 명단을 구하는 문제이다. 무식하게 문제를 풀면 시간 복잡도가 O(N x M)이 된다. 그리고 500,000 x 500,000 = 250,000,000,000으로 시간초과가 난다. 듣도 못한 사람의 명단을 A, 보도 못한 사람의 명단을 B 라고 했을 때 하나만 정렬된 명단이라면, 이진탐색이 가능해진다. n, m = map(int, input().split()) li_n = [] li_m = [] for _ in range(n): li_n.append(input()) for _ in range(m): li_m.append(input()) li_m.sort() def BSearch(target): low = 0 high = len(li_m) - 1 while low
[BOJ] [Python] 20438 : 출석체크 문제를 정리해보자. 3번부터 (N + 2)번까지 있다. 지환이가 무작위로 선정한 학생을 i라고 하자. i번은 i번의 배수인 학생들에게 출석 코드를 보낸다. (i는 Q번 바뀐다.) 현재 K명은 졸고 있다. 졸고 있는 학생은 출석도 안 하고, 출석 코드를 보내지도 않는다. 최종적으로 출석이 되지 않은 학생들의 수를 구하면 된다. # N : 학생 수 # K : 졸고 있는 학생 수 # Q : 지환이가 출석 코드를 보낼 학생 수 # M : 주어질 구간의 수 import sys input = sys.stdin.readline n, k, q, m = map(int, input().split()) k_li = list(map(int, input().split())) q_li = list(map(int, input()...
[BOJ] [Python] 18222 : 투에-모스 문자열 X는 0을 시작으로 X += X'을 반복한다. 시간초과 때문에, 점화식을 찾아서 풀어야 하는 문제이다. 헤매다가 결국 위키백과를 참고해서 풀었다. 점회식은 아래와 같다. T(0) = 0 T(2n) = T(n) T(2n + 1) = 1 - T(n) n을 0부터 시작하는 것으로 봤기 때문에, k -= 1 해서 생각한다. 예를 들어보자, K = 6 n = 5 -> n = 2 -> n = 1 return 1 -> return 1 -> return ( 1 - 1 ) K = 5 n = 4 -> n = 2 -> n = 1 return 1 -> reutrn 1 -> return 1 # t(0) = 0 # t(2n) = t(n) # t(2n + 1) = 1 - t(n) k = int(input()) def find(x)..
[BOJ] [Python] 2630 : 색종이 만들기 분할정복 알고리즘을 이용했다. 분할정복 알고리즘의 로직은 다음과 같다. 1. 문제가 분할이 가능하면, 2개 이상으로 나눈다. 2. 나누어진 문제가 여전히 분할 가능하면 1번을 다시 수행하고, 가능하지 않다면 문제를 푼다. 3. 나누어진 각각을 모두 합병한다. 이 문제는 해결이 가능할 때까지 반복해서 4등분으로 나눈다. 즉, 계속 쿼드 트리를 만드는 것이다. (쿼드 트리는 트리의 자식 노드가 4개인 트리를 뜻한다.) 어떻게 4등분을 할지 생각해보자. 색종이는 항상 정사각형이기 때문에, 4등분을 하고 각 왼쪽 위을 기준으로 재귀함수를 돌리는 것을 반복한다. num = int(input()) graph = [list(map(int, input().split())) for _ in range(num)] w = ..
[BOJ] [Python] 5212 : 지구온난화 현재 지도를 기준으로, 섬이 삼면 이상의 바다로 둘러싸여 있다면 50년 후 그 섬은 잠긴다. 지도상에서 섬이 바다로 바뀌는 데는 굳이 BFS를 사용할 필요가 없다고 생각했다. 바이러스처럼 퍼져나가는 상황이 아니기 때문이다. 이중 반복문을 통해서 해결해보자. 현재 지도인, graph 리스트와 같은 지도를 하나 더 만든다. 이것은 copy 리스트인데, 이중 반복문을 돌며 50년 후 상황을 기록한다. 바다는 . 뿐만 아니라 r과 c의 범위를 나간 곳도 포함이다. 섬을 기준으로 상하좌우를 확인하면서 삼면 이상 바다라면, 섬의 위칫값을 0으로 변경한다. r, c = map(int, input().split()) graph = [[0] * c for _ in range(r)] copy = [[0] * c for _..
[BOJ] [Python] 10971 : 외판원 순회 2 문제의 예제 입력을 표로 작성해보았다. 주의할 점 1. 모든 도시를 경유한다. 2. [i][j]가 0일 경우 갈 수 없는 길이다. 3. 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 고민했던 점 1. 어디서 출발해야 할까? 2. 어떻게 최단 거리로 모두 경유할까? 모든 도시를 경유해야 하는 문제 때문에, 다익스트라 알고리즘을 사용하지 않았다. 백트래킹으로 해결해 보자. n = int(input()) li = [] li_idx = [] dp = [0] * n result = 1e9 for _ in range(n): li.append(list(map(int, input().split()))) def back(cnt): global result if cnt..
[BOJ] [Python] 15649 : N과 M (1) 1부터 N까지 자연수 중에서 중복 없이 M개를 골라 수열을 만들면 된다. 핵심은 '중복 없이'이다. n, m = map(int, input().split()) li = [] dp = [0] * (n + 1) def back(cnt): if cnt == m: print(*li) return for i in range(1, n + 1): if dp[i] == 1: continue li.append(i) dp[i] = 1 back(cnt + 1) dp[li[-1]] = 0 li.pop() back(0) 백트래킹, 처음에는 어렵게 느껴졌는데 지금은 감을 좀 잡은 것 같다.
[BOJ] [Python] 11663번 : 선분 위의 점 예를 들어보자. (아래는 백준 예제 입력 1의 일부이다.) 5 1 1 3 10 20 30 1 9 현재 점의 위치는 1, 3, 10, 20, 30이다. 선분의 시작점은 1, 끝점은 9이다. 점의 위치 상에서 선분의 위치를 찾아줘야 한다. 점의 위치 상에서, 선분의 시작점은 선분의 시작점보다 크거나 같은 최솟값, 선분의 끝점은 선분의 끝점보다 작거나 같은 최댓값을 찾아주면 된다. 따라서 각각 1과 3이다. (전자는 tmp_s, 후자는 tmp_e) 여기서 주의할 점은 범위이다. 첫 번째 선분의 시작점이 점의 가장 앞의 위치보다 왼쪽에 있을 때. => tmp_s를 점의 가장 앞의 위치로 생각해주면 된다. 선분이 포함하는 최솟값이 가장 앞의 위치이기 때문이다. 두 번째 선분의 끝점이 점의 가장 끝 위치보다 오른쪽..
[BOJ] [Python] 10815번 : 숫자 카드 M개의 수에 대해서, 상근이가 가진 숫자 카드와 비교하는 문제이다. 중복되는 수가 있다면 1, 없다면 0이다. 순차 탐색으로 풀었다. n = int(input()) A = list(map(int, input().split())) A.sort() m = int(input()) tmp = list(map(int, input().split())) B = sorted(set(tmp)) idx = 0 result = {} for num in B: while True: if idx == n: result[num] = 0 break if num == A[idx]: result[num] = 1 break elif num < A[idx]: result[num] = 0 break else: idx += 1 for n in..

티스토리툴바