[백준] 11650 좌표 정렬하기 - 파이썬
2022. 4. 7. 23:57
알고리즘
11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net import sys n = int(input()) lst = [] for _ in range(n): lst.append(list(map(int, sys.stdin.readline().split()))) lst.sort() for a, b in lst: print(a, b) 첫 번째 값이 같으면 두 번째 값을 보고 정렬을 하는 문제인데 어떻게 정렬을 할까 하다가 일단 sort() 함수를 돌려보고 결과를 볼까? 해..
[백준] 2018 통계학 - 파이썬
2022. 4. 6. 13:38
알고리즘
2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net import statistics, sys n = int(input()) lst = [int(sys.stdin.readline()) for _ in range(n)] print(round(statistics.mean(lst))) print(statistics.median(lst)) mode = statistics.multimode(lst) if len(mode) > 1: mode.sort() print(mode[1]) else: print(mode[0]) print(max(ls..
[백준] 10989 수 정렬하기 3 - 파이썬 (카운팅 정렬)
2022. 4. 5. 17:21
알고리즘
10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 카운팅 정렬에 대해서는 다음 블로그 참고 https://elrion018.tistory.com/37 카운팅 정렬은 non-comparison sort 기법으로 두 수를 반복적으로 비교하는 정렬 기법이 아니다. counting sort 1. input 배열 요소들의 빈도 값을 세어서 counting array에 저장 counting array의 각 요소 값은 인덱스에 해당하는 요소가 input 배열에 얼마나 존재하는지를 의미한다. 2. counting array의 각 요소에 직전 요소..
[백준] 2751 수 정렬하기 2 - 파이썬 / 퀵 정렬
2022. 4. 5. 15:09
알고리즘
2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net import sys n = int(input()) lst = [int(sys.stdin.readline()) for _ in range(n)] lst.sort() for n in lst: print(n) 사실 파이썬 내장 함수 sort 쓰면 통과되는 문제, 설명에서도 내장 함수 쓰라고 하고.. (단, input 사용하면 시간 초과) 파이썬의 sort는 병합정렬과 삽입정렬을 적절히 섞은 알고리즘이라고 하고 시간복잡도는 O(NlogN)이라고 한다. (근데..
[백준] 1436 영화감독 숌 - 파이썬
2022. 4. 4. 19:38
알고리즘
1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net def nth_number(n): order = 0 for i in range(666, 2147483647): cnt = 0 for c in list(str(i)): cnt = cnt + 1 if c == '6' else 0 if cnt == 3: order += 1 break if order == n: return i n = int(input()) print(nth_number(n)) 그냥 무식하게 666부터 시작해서 종말 숫자들을 계속 하나씩 세는 함수다...
[백준] 1018 체스판 다시 칠하기 - 파이썬
2022. 4. 4. 17:23
알고리즘
1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 초기코드 import sys def count(board, x, y, color): count = 0 for i in range(x, x + 8): for j in range(y, y + 8): if board[i][j] != color: count += 1 if j != y + 7: color = 'B' if color == 'W' else 'W' return count n, m = map(int, input().split()) board = [0] *..
[백준] 7568 덩치 - 파이썬
2022. 4. 2. 10:56
알고리즘
7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net import sys n = int(input()) w, h = [0] * n, [0] * n for i in range(n): w[i], h[i] = map(int, sys.stdin.readline().split()) for i in range(n): count = 1 for j in range(n): if w[i] < w[j] and h[i] < h[j]: count += 1 print(count, end=" ") 처음에는 몸무게와 키를 각각 리..
[Spring] Spring DI
2022. 4. 1. 17:31
프로그래밍/Spring
Spring DI DI는 'Dependency Injection'의 약자로 '의존 주입'을 의미한다. 여기서 말하는 '의존'은 객체 간의 의존을 말한다. import java.time.LocalDateTime; public class MemberRegisterService { private MemberDao memberDao = new MemberDAO(); public void regist(RegisterRequest req) { Member member = memberDao.selectByEmail(req.getEmail()); if (member != null) { throw new DuplicateMemberException("dup email " + req.getEmail()); } Member..
[백준] 2231 분해합 - 파이썬
2022. 4. 1. 14:46
알고리즘
2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net def digit_sum(n): sum = n while n > 0: sum += n % 10 n //= 10 return sum n = int(input()) digit = len(str(n)) front = n // 10 ** (digit - 2) - 1 if digit > 2 else n // 10 - 1 while digit_sum(front * 10 + 9) > n: front -= 1 start = front * 10 + ..
[백준] 2798 블랙잭 - 파이썬
2022. 4. 1. 00:02
알고리즘
2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net n, m = map(int, input().split()) lst = list(map(int, input().split())) dif = 300000 for i in range(n - 2): for j in range(i + 1, n - 1): for k in range(j + 1, n): sum = lst[i] + lst[j] + lst[k] if m - sum < dif and sum