전체 글

(Python) 백준 10814번 - 나이순 정렬

문제 링크 : https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이 sort() 함수에 key로 lambda 함수를 넘겨주게 되면, 이 함수의 반환값을 기준으로 순서대로 정렬하게 된다. 여기서는 x[0], 즉 리스트의 첫번째 요소인 age를 기준으로 정렬하게 되는 것이다. import sys num = int(sys.stdin.readline()) arr = [] for _ in range(num): age, name = map(str, sys.st..

(Python) 백준 7568번 - 덩치

문제 링크 : https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 풀이 브루트포스 문제이다보니 실버 문제치고 풀이가 어렵지 않았다. import sys num = int(sys.stdin.readline()) weight = [] height = [] rank = [0] * num for _ in range(num): w, h = map(int, sys.stdin.readline().split()) weight.append(w) hei..

(Python) 백준 2751번 - 수 정렬하기 2

문제 출처 : https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 풀이 합병 정렬을 사용한 풀이이다. O(NlogN)의 시간복잡도를 가지는 합병 정렬이기에 시간 초과가 발생하지 않을 것으로 기대했으나 시간 초과가 일어나서 상당히 당황했었다. 하지만 sys.stdin.readline()이 아닌 input()을 사용해서 시간초과가 발생한 것이었다. import sys def mergesort(arr): # 분할과 정복을 활용한 합병정렬 if..

(Python) 백준 1978번 - 소수 찾기

문제 링크 : https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 풀이 처음엔 단순하게 에라토스테네스의 체 방식으로 풀어서는 시간 초과가 날 수 있을거 같았으나 문제 분류에 에라토스테네스의 체라고 적혀있어서 시도해보았더니 제한 시간 내에 통과할 수 있었다. n = int(input()) count = 0 # 소수가 아닐 경우를 count arr = list(map(int, input().split())) for num in arr: if num == 1: # 1은 소수가 아님 count += 1 # 소수가 아니면 c..

(Python) 백준 1436번 - 영화감독 숌

문제 링크 : https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 풀이 브루트포스 문제이다보니 실버 문제치고 풀이가 어렵지 않았다. i = int(input()) fin = 0 # 종말의 숫자 flag = 0 # 몇 번째 종말의 숫자인지 while i != flag: # 원하는 순서의 종말의 숫자에 도달할때까지 반복 fin += 1 # 0부터 하나씩 증가 시키기 if "666" in str(fin): # "666"과 비교를 위해 fin을 문자열로..

(Python) 백준 1181번 - 단어 정렬

문제 링크 : https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 arr = [] for _ in range(int(input())): m = input() if m in arr: continue if len(arr) == 0: arr.append(m) for i in range(len(arr)): if len(arr[i]) > len(m): arr.insert(i, m) break elif len(arr[i]) == len(m):..

계수 정렬

계수 정렬이란? 카운팅 정렬 (Counting Sort)이라고 부르기도 하는 계수정렬은 O(n)의 시간복잡도를 가지는 정렬이다. 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다. 계수 정렬의 특징 주어진 데이터의 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘이다. 0과 양수 범위의 데이터들만 정렬할 수 있다. 데이터의 범위가 커지게 되면 소요되는 시간이 커지게 되고, 메모리가 낭비되는 문제가 발생한다. 또한 음수 범위의 데이터들은 정렬할 수 없다는 단점을 가진다. 계수 정렬의 과정 정렬되지 않은 수들을 count 배열에 몇 번씩 등장하는지 적어둔다. count 배열을 앞에서부터 순회하며 등장 횟수를 누적합으로 변경한다. 기존의 배열의 뒤에서부터 누적합 결과를 인덱스로 사..

(Python) input() vs sys.stdin.readline()

백준 문제를 풀 때 Input()을 사용하면 시간 초과가 발생하고, sys.stdin.readline()을 사용하면 시간 안에 채점이 완료되는 경우가 여러 번 있어서 이 둘의 차이를 명확하게 정리하고자 한다. 이 두 함수가 동작하는 모습을 보면 기능은 비슷하다고 생각할 수 있지만, 명확한 차이점이 존재한다. 1. input() 파이썬의 내장함수로써, 인수로 prompt message를 받을 수 있다. 2. sys.stdin.readline() sys 모듈의 메소드로써, 인수로 prompt message를 받지 않는다. 3. 차이점 (1) 위에서 언급했듯이 input()은 인수로 prompt message를 받고, 이를 출력한다. 반면 sys.stdin.readline()은 아무런 인수를 받지 않기 때문에..

(Python) 백준 10989번 - 수 정렬하기 3

문제 링크 : https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 원래 브론즈 문제는 포스팅하지 않으려 했으나 문제와 관련하여 정리할 개념들이 많이 있어서 풀이를 적어보려고 한다. 메모리 제한과 시간 제한이 있어 단순하게 python의 sort함수로는 이 문제를 풀 수 없어서 계수정렬을 이용하여 풀었다. count = [0] * 10001 for _ in range(int(input())): count[int(input())] += 1 for i in range..

[ToDo List using JPA] 2. Todo List 구현

1. 기본 설정 ToDo List 프로젝트의 기본 설정을 위한 작업들이다. // build.gradle dependencies { testImplementation 'org.springframework.boot:spring-boot-starter-test' implementation 'org.springframework.boot:spring-boot-starter-data-jpa' implementation 'org.springframework.boot:spring-boot-starter-web' implementation 'com.h2database:h2' compileOnly 'org.projectlombok:lombok:1.18.24' runtimeOnly 'com.h2database:h2' ann..