공부하는 블로그 ✍️

📌 11656. 접미사 배열 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다. baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다. 문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오. ✏️ 입력. 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. 📋 출력. 첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다 # 접미사 배열 str = input() arr..

📌 11650. 좌표 정렬하기 2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. ✏️ 입력. 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 📋 출력. 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. n = int(input()) arr = [] for i in range(n): arr.append(list(map(int, input().split()))) arr.sort() for i in rang..

퀵 정렬의 시간 복잡도 - 퀵 정렬의 평균 시간 복잡도는 O(NlogN) 으로 다른 정렬 알고리즘에 비해 매우 빠른 편이다 - 피벗값의 위치가 변경되어 분할이 일어날 때 마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할한다고 가정해보자 - 데이터의 개수를 8개라고 가정하고, 정확히 절반씩 나누어 간다는 가정을 해보자 - 이 때 높이를 확인해보면 데이터의 개수가 N 개일 때 높이는 약 logN 이라고 판단할 수 있다 - 즉, 분할이 이루어지는 횟수가 기하급수적으로 감소한다 - 데이터의 개수가 많아질수록 다른 정렬에 비해 압도적으로 빠르게 동작하게 된다 - 다만, 퀵 정렬의 평균 시간 복잡도는 O(NlogN) 이지만, 최악의 경우의 시간 복잡도는 O(N²) 이다 - 데이터가 무작위로 입력되는 경우 퀵 ..

호어 분할 방식 구현하기 / Python - 퀵 정렬에 대해 알아보고, 첫 번째 데이터를 피벗(Pivot)으로 사용하는 호어 분할 방식의 전체적인 과정은 위와 같다 - 예제로 들었던 배열을 사용해, 퀵 정렬을 파이썬으로 구현해 보도록 하자 arr = [ 5, 7, 9, 0, 3, 1, 6, 2, 4, 8 ] - 예제의 데이터를 배열의 형태로 선언하여 사용한다 def quick_sort(arr, start, end): if start >= end: # 요소가 하나인 경우 종료 return pivot = start # 호어 방식이므로 첫번째 데이터를 pivot으로 사용한다 left = start + 1 # 왼쪽 데이터는 pivot의 바로 오른쪽 데이터를 사용한다 right = end # 오른쪽 데이터로 마지..

퀵 정렬 - 퀵 정렬은 가장 많이 사용되는 알고리즘이다. - 퀵 정렬과 비교할 만큼 빠른 알고리즘에는 병합 정렬 알고리즘이 있다 - 기준을 설정하고, 다음 큰 수와 작은 수를 교환하여 리스트를 반으로 나누는 방식으로 동작한다 피벗 (Pivot) - 피벗(Pivot) : 큰 숫자와 작은 숫자를 교환할 때, 교환의 기준을 말한다 - 퀵 정렬에서는 피벗(Pivot)이 사용된다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야 한다 - 피벗을 설정한 뒤에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다 - 피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵 정렬이 분류된다 호어 분할 방식(Hoare Parition) - 가장 대표적인 분할 방식인 호어 ..

✏️ 서버 사이드(Server-Side)와 클라이언트 사이드(Client-Side) 서버 사이드(Server-Side)란 네트워크의 한 방식인 클라이언트-서버 구조에서 서버에서의 처리를 말한다 웹에서의 서버 사이드를 간단히 말하자면, 웹 서버에서 하는 작업을 의미한다 클라이언트로 요청을 받아 처리하고 처리 결과를 브라우저에 송신, 응답하는 역할을 한다 클라이언트 사이드(Client-Side)란, 네트워크의 한 방식인 클라이언트-서버 구조에서 클라이언트의 처리를 말한다 웹에서의 클라이언트는, 서버와는 상대되는 개념으로 어떤 서비스를 요청하는 역할을 하게 된다 웹 페이지를 요청하는 것은 클라이언트의 역할이라고 말할 수 있다 웹 페이지의 요청은 대부분 웹 브라우저가 하게 된다. 그렇기 때문에 일반적으로 웹에서..

📌 1991. 트리 순회 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, - 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) - 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) - 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) ✏️ 입력. 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노..

📌 10546. 배부른 마라토너 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명만 빼고! 모두가 참가하고 싶어서 안달인데 이런 백준 마라톤 대회에 참가해 놓고 완주하지 못한 배부른 참가자 한 명은 누굴까? ✏️ 입력. 첫째 줄에는 참가자 수 N이 주어진다. (1 ≤ N ≤ 105) N개의 줄에는 참가자의 이름이 주어진다. 추가적으로 주어지는 N-1개의 줄에는 완주한 참가자의 이름이 쓰여져 있다. 참가자들의 이름은 길이가 1보다 크거나 같고, 20보다 작거나 같은 문자열이고, 알파벳 소문자로만 이루어져 있다. 참가자들 중엔 동명이인이 있을 수도 있다. 📋 출력...

📌 12034. 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 문자열 중 적어도 하나의 접두사인 것의 개수를 구하는 프로그램을 작성하시오. ✏️ 입력. 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열이 주어진다..

📌 12034. 김인천씨의 식료품가게(Large) 전설적인 인천 식료품가게의 주인인 김인천 씨는 대대적인 할인행사를 계획하고 있습니다. 계산을 단순하게하기 위해 그는 25% 할인된 가격으로 상점의 모든 품목을 판매하기로 결정했습니다. 즉, 각 품목의 판매 가격은 정상 가격의 정확히 75 %입니다. 우연하게도 인천 식료품가게에서 판매하는 모든 물건의 정상가는 4의 배수인 정수이고, 할인된 가격 역시 편리하게도 모두 정수입니다. 김인천씨는 이 할인행사를 준비하기위해서 먼저 모든 판매물품의 할인된 판매가격을 프린터로 출력을 실행했고, 또한 할인행사 종료후 다시 쓸 모든 품목에 정상가격표 역시 출력을 실행하였습니다. 손님이 찾아와 잠깐 자리를 비웠던 김인천씨가 다시 가격표의 출력을 확인하기 위해서 프린터로 돌아..