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

수 정렬하기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

나이순 정렬

in Algorithm, Sorting

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

소트인사이드

in Algorithm, Sorting

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

수 정렬하기

in Algorithm, Sorting

백준 2750 : 문제링크

  • 문제유형 : 정렬

  • 설명

    • 선택 정렬로 풀이

    • sort함수로도 해결 가능

  • 풀이

    • 선택 정렬

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      n = int(input())
      array = list()

      for _ in range(n):
          array.append(int(input()))

      for i in range(n):
          min_index = i
          for j in range(i+1, n):
              if array[min_index] > array[j]:
                  min_index = j
          array[i], array[min_index] = array[min_index], array[i]

      for i in array:
          print(i)

    • 기본 라이브러리

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      n = int(input())
      array = list()

      for _ in range(n):
          array.append(int(input()))

      array.sort()

      for i in array:
          print(i)

Comment and share

  • page 1 of 1

Yechan Kim

author.bio


author.job