백준 1543 : 문제링크

• 문제유형 :

  • 탐색

• 설명

  • 단순히 모든 경우의 수를 계산하여 해결

  • 인덱스를 하나씩 올리면서 단어와 비교

  • 동일하면 결과값을 1 올리고 인덱스 위치를 단어의 길이만큼 늘린다

  • 다르면 인덱스를 1만 올린다

  • 단어의 길이보다 문서의 남은 인덱스의 길이가 짧을 때 종료한다

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  document = input() word = input() index = 0 result = 0 while len(document) - index >= len(word): if document[index:index + len(word)] == word: result += 1 index += len(word) else: index += 1 print(result)

Comment and share

백준 11004 : 문제링크

• 문제유형 : 정렬

• 설명

  1. 데이터의 크기가 5000000이다

  2. 병합정렬, 퀵 정렬, 힙 정렬을 사용해야한다.

  3. python 기본 정렬 라이브러리로도 가능하다.

• 풀이

  • 병합정렬

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

    def merge_sort(array): if len(array) == 1: return array left = array[:mid] right = array[mid:] i, j, k = 0 while i < len(left) and j < len(right): if left[i] < right[j] array[k] = left[i] left += 1 else: array[k] = right[j] right += 1 k += 1 if i == len(left): while j < len(right): array[k] = right[j] j += 1 k += 1 elif j == len(right): while i < len(left): array[k] = left[i] i += 1 k += 1 return array n, k = map(int, input().split(' ')) array = list(map(int, input().split(' '))) array = merge_sort(array) print(array[k-1])

  • 정렬 라이브러리

    1 2 3 4 5 6

    n, k = map(int, input().split(' ')) array = list(map(int, input().split())) array = sorted(array) print(array[k-1])

Comment and share

백준 2751 : 문제링크

• 문제유형 : 정렬

• 설명

  • 데이터의 개수가 1000000개

  • NlogN의 정렬 알고리즘을 이용해야한다. -> 병합, 퀵, 힙 정렬

  • 기본 정렬 알고리즘으로 해결가능

• 풀이

  • 병합 정렬

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

    def merge_sort(array): if len(array) <= 1: return array mid = len(array) // 2 left = merge_sort(array[:mid]) right = merge_sort(array[mid:]) i, j, k = 0, 0, 0 while i < len(left) and j < len(right): if left[i] < left[j]: array[k] = left[i] i + = 1 else: array[k] = right[j] j += 1 k += 1 if i == len(left): while j < len(right): array[k] = right[j] j += 1 k += 1 elif j == len(right): while i < len(left): array[k] = left[i] i += 1 k += 1 return array n = int(input()) array = [] for _ in range(n): array.append(int(input())) array = merge_sort(array) for data in array: print(data)

  • 정렬 라이브러리

    1 2 3 4 5 6 7

    n = int(input()) array = [] for _ in range(n): array.append(int(input())) array = sorted(array)

Comment and share

백준 7490 : 문제링크

• 문제유형 : 재귀

• 설명

  1. 자연수 N의 범위(3 <= N <= 9)가 한정적이므로 완전 탐색으로 문제 해결

  2. 수의 리스트와 연산자의 리스트로 분리하여 모든 경우의 수를 해결

  3. 가능한 모든 경우를 고려하여 연산자 리스트를 만들 때 재귀를 사용

  4. 파이썬 eval() 함수를 이용하여 문자열 형태의 표현식을 계산한다.

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

  import copy def recursion(array, n): if len(array) == n: operators_list.append(copy.deepcopy(array)) return array.append(' ') resursive(array, n) array.pop() array.append('+') recursive(array, n) array.pop() array.append('-') recursive(array, n) array.pop() test_case = int(input()) for _ in range(test_case): operators_list = [] n = int(input()) recursive([], n-1) integers = [i for i in range(1, n+1)] for operators in operators_list: string = "" for i in range(n-1): string += str(integers[i]) + operators[i] string += str(integers[-1]) if eval(string.replace(" ", "")) == 0: print(string) print()

Comment and share

백준 1074 : 문제링크

• 문제유형 : 재귀

• 설명

  1. 2^N의 사각형을 2^(N-1)의 사각형 4개로 나누어 재귀로 해결

  2. N = 2일때 까지 분할

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

  def solve(n, x, y): global result if n == 2: if x == X and y == Y: print(result) return result += 1 if x == X and y + 1 == Y: print(result) return result += 1 if x + 1 == X and y == Y: print(result) return result += 1 if x + 1 == X and y + 1 == Y: print(result) return result += 1 return solve(n / 2, x, y) solve(n / 2, x, y + n / 2) solve(n / 2, x + n / 2, y) solve(n / 2, x + n / 2, y + n / 2) result = 0 N, X, Y = map(int, input().split(' ')) solve(2 ** N, 0, 0)

Comment and share

백준 1074 : 문제링크

• 문제유형 : 재귀

• 설명

  • 2^N의 크기의 사각형을 2^(N-1)의 사각형 4가지 부분으로 나눠서 재귀적으로 해결

• 풀이

  • 실패 코드

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

    def solve(n, x, y): global result if n == 2: if x == X and y == Y: print(result) return result += 1 if x == X and y + 1 == Y: print(result) return result += 1 if x + 1 == X and y == Y: print(result) return result += 1 if x + 1 == X and y == Y: print(result) return result += 1 solve(n / 2, x, y) solve(n / 2, x, y + n/2) solve(n / 2, x + n / 2, y) solve(n / 2, x + n / 2, y + n / 2) result = 0 N, X, Y = map(int, input().split(' ')) solve(2 ** N, 0, 0)

Comment and share

백준 10989 : 문제링크

• 문제유형 : 정렬

• 설명

  • 데이터의 개수가 최대 10000000개

  • 계수 정렬 사용

    • 배열의 인덱스를 특정한 데이의 값으로 여기는 방식

    • 배열의 크기는 데이터의 범위를 포함할 수 있도록 설정

    • 데이터가 등장한 횟수만큼 각 인덱스의 배열 값을 증가시킴

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12 13

  import sys n = int(sys.stdin.readline()) array = [0] * 10001 for i in range(n): data = int(sys.stdin.readline()) array[data] += 1 for i in range(10001): if array[i] != 0: for j in range(array[i]): print(i)

Comment and share

백준 11650 : 문제링크

• 문제유형 : 정렬

• 설명

  1. 튜플로 두 개의 데이터를 묶어서 저장

  2. 파이썬 기본 정렬 알고리즘은 튜플의 인덱스 순서대로 오름차순 정렬한다.

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12

  n = int(input()) array = [] for _ in range(n): x, y = map(int, input().split) arrray.append((x, y)) array = sorted(array) for i in array: print(i[0], i[1])

Comment and share

백준 10814 : 문제링크

• 문제유형 : 정렬

• 설명

  1. 튜플로 두 개의 데이터를 묶어서 저장

  2. sorted 함수로 정렬, lambda로 첫번째 정렬 기준값을 정함

  3. 튜플로 저장하면 첫번째 정렬 기준값이 동일할 때 다음 값으로 자동 정렬

• 풀이

  1 2 3 4 5 6 7 8 9 10 11 12

  n = int(input()) array = [] for _ in range(n): input_data = input().split(' ') array.append((int(input_data[0])), input_data[1]) array = sorted(array, key=lambda x : x[0]) for i in array: print(i[0], i[1])

Comment and share

백준 1427 : 문제링크

• 문제유형 : 정렬

• 설명

  1. 9 에서 0 까지 차례대로 내려가면서 확인

  2. 각 숫자의 개수를 계산해서 출력

• 풀이

  • 선택 정렬

    1 2 3 4 5 6

    array = input() for i in range(9, -1, -1): for j in array: if int(j) == i: print(i, end='')

Comment and share