[백준] 2075번 N번째 큰 수 파이썬 풀이
https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 1. 접근 방식 한 줄씩 입력 받을 때마다 1번째 ~ N번째 큰 수를 갱신하자 1번부터 N번째 큰 수를 담는 리스트를 사용한다. 위 그림에선 노란 리스트이다. 회색 리스트는 매번 입력 받는 숫자들이다. 노란 리스트는 회색 리스트의 숫자들이 추가될 때마다 갱신된다. 현재 노란색 리스트에 있는 숫자들과 회색 리스트에 있는 숫자들을 내림차순 정렬하고, 인덱스 0에서 (N - 1)까지 잘라서 노란 리스트에 담기..
[프로그래머스] H-index 파이썬 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/42747 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 접근 방식 계수 정렬(Count Sort)를 이용하자 인용 횟수가 동일한 논문이 있을 것이다. 따라서 인용 횟수가 인덱스고, 그 수만큼 인용된 논문의 개수를 값으로 하는 리스트를 활용하도록 하자. 위 리스트를 뒤에서부터 접근함으로써 높은 논문 인용 횟수에서 그 횟수를 하나씩하나씩 줄여나가자. 만약 현재 인용 횟수보다 논문의 개수가 적다면 인용 횟수를 하나 더 줄이고, 논문 개수보다 많거나 같..
[백준] 1931번 회의실 배정 파이썬 풀이
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 1. 접근 방식 회의 시작 시간과 끝나는 시간이라는 2가지 기준으로 오름차순 정렬하자. 앞 타임 회의가 끝나면 이후 타임 회의가 시작될 수 있기 때문에 우선 시간을 기준으로 정렬해준다. 현재 회의 시작 시간이 이전 회의의 끝나는 시간보다 크거나 같을 때, 현재 회의를 시작할 수 있다. 이전 회의가 끝나는 시간이 end이고 현재 회의 시작 시간이 x일 때, 현재 회의 시작 조건을 코드로 나타내면 if x >= end이다. 현재 회의가 새롭게 시작되었으므로, 회의 개수는 + 1된다. 현재 회의가 이전 회의 시간이 끝..
정렬 알고리즘2: 퀵, 병합
참고 「취업을 위한 코딩 테스트이다 with 파이썬」 나동빈 지음 「Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬 편」 시바타 보요 지음 https://yabmoons.tistory.com/250 콘텐츠 개념 파이썬 구현 코드 시간 복잡도 장단점 퀵 정렬과 병합 정렬 선택 기준 대부분의 프로그래밍 언어에서 정렬 라이브러리는 속도가 빠른 퀵이나 병합 정렬을 기반으로 한다. 퀵 정렬 (Quick Sort) 개념 피벗pivot이라는 기준에 의해 리스트 내 큰 숫자와 작은 숫자를 교환한다. 피벗을 설정하는 기준은 다양하지만, 리스트의 첫 번째 원소를 피벗으로 설정하는 "호어 분할 방식"이 가장 대표적이다. 초록색이 피벗이고, 노란색 화살표는 5 다음 숫자에서부터 피벗보다 큰 값을 찾고, 파란색 화살표..
[백준] 18870번 좌표 압축 파이썬 정답 코드
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 1. 접근 방식 중복되는 수가 존재하며, 중복되는 여러 수는 마치 하나만 존재하듯이 카운팅 되므로 집합 개념을 사용하자. 중복 제거된 데이터를 정렬하면, 각 수의 인덱스가 곧 새로운 좌표이다. (파란색 숫자) 각 수의 인덱스를 기억하기 위해 딕셔너리를 사용하자. key는 수이고, value는 인덱스이다. 이후엔 기존 데이터를 순회하면서 해당 수를..
[백준] 1431번 시리얼 번호 파이썬 정답 코드
https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 1. 접근 방식 가장 먼저 입력받은 시리얼 번호에 내장 함수 sort( )를 적용하여 3번째 조건으로 정렬하자. 3번째 조건이긴 하지만, 1, 2번 조건으로 비교할 수 없다면 알파벳 사전 순으로 정렬해야 한다. 문자열을 sort( )하면 ASCII 코드 값을 기준으로 오름차순 정렬된다. 그럼 일단 알파벳 순서대로도 정렬이 되는 것이므로, 먼저 sort( )를 적용한다. sorted( )의 k..
정렬 알고리즘1: 버블, 선택, 삽입
참고 「취업을 위한 코딩 테스트이다 with 파이썬」 나동빈 지음 모두를 위한 컴퓨터 과학 (CS50 2019) https://www.boostcourse.org/cs112/joinLectures/41488?isDesc=false 구성 요소 개념 파이썬 구현 코드 시간 복잡도 장단점 버블 정렬(Bubble Sort) 개념 데이터 내 인접한 두 요소를 비교하여 자리를 교환하거나 그대로 유지하는 정렬 방법이다. 위 그림은 버블의 각 단계를 나타낸 것으로, 파란색이 인접한 두 요소이다. 오름차순 정렬 기준, 왼쪽에 있는 값이 오른쪽에 있는 값보다 크다면 둘이 자리를 바꾼다. 이미 정렬되어 있는 상태(왼쪽 요소 < 오른쪽 요소)라면 그대로 다음 인덱스로 넘어간다. 데이터의 마지막 요소까지 비교가 끝나면, 가장 ..