베스트셀러

in Algorithm, Search

백준 1302 : 문제링크

  • 문제유형 :

    • 탐색

  • 설명

    • 파이썬 dictionary 자료형 사용(HashMap)

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    n = int(input())

    books = {}

    for _ in range(n):
        book = input()
        if book not in books:
            books[book] = 1
        else:
            books[book] += 1

    target = max(books.values())
    array = []

    for book, number in books.items():
        if number == target:
            array.append(book)

    print(sorted(array)[0])

Comment and share

새

in Algorithm, Search

백준 1543 : 문제링크

  • 문제유형 :

    • 탐색

  • 설명

    • N이 최대 1000000000 이다

    • K가 반복적으로 증가하므로, 새의 마리 수는 빠르게 증가한다

    • 요구하는 대로 단순 구현하면 된다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    n = int(input())
    result = 0
    k = 1

    while n != 0:
        if k > n:
            k = 1
        n -= k
        k += 1
        result += 1
        
    print(result)

Comment and share

문서 검색

in Algorithm, Search

백준 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

K번째 수

in Algorithm, Sorting

백준 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

수 정렬하기2

in Algorithm, Sorting

백준 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

0 만들기

in Algorithm, Sorting

백준 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

Z

백준 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

피보나치 수

in Algorithm, Recursive

백준 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

수 정렬하기3

in Algorithm, Sorting

백준 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

좌표 정렬하기

in Algorithm, Sorting

백준 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

Yechan Kim

author.bio


author.job