[백준] 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) 개념 데이터 내 인접한 두 요소를 비교하여 자리를 교환하거나 그대로 유지하는 정렬 방법이다. 위 그림은 버블의 각 단계를 나타낸 것으로, 파란색이 인접한 두 요소이다. 오름차순 정렬 기준, 왼쪽에 있는 값이 오른쪽에 있는 값보다 크다면 둘이 자리를 바꾼다. 이미 정렬되어 있는 상태(왼쪽 요소 < 오른쪽 요소)라면 그대로 다음 인덱스로 넘어간다. 데이터의 마지막 요소까지 비교가 끝나면, 가장 ..