(python3) 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net 딕셔너리 정렬 문제 조건이 많기 때문에 딕셔너리를 활용해서 구현하면 직관적인 코딩이 가능합니다. 딕셔너리를 완성한 후 점수 기준에 맞춰 sorted 와 key 파라미터를 활용해 커스텀한 정렬을 실행해줍니다. sorted 사용법은 다음 글에 자세히 설명해두었습니다. [sort] 파이썬에서 커스텀한 기준으로 이터러블한 객체 정렬하기 key 파이썬에서 제공하는 sorted 기능은 key 파라미터로 커스텀한 기준을 부여하여 정렬할 수 있습니다. 파이썬 sor..
(python3) 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 투포인터, 이진 탐색 완전 탐색을 진행하면 $O(N^2)$ 으로 시간초과가 발생합니다. 정렬된 상태로 입력이 주어지므로 이진 탐색을 활용하면 O(N*logN) 으로 줄일 수 있습니다. 추가로 섞을 용액 두개 다 양수인 경우 가장 작은 합 조합은 가장 작은 양수 두개가 됩니다. 음수의 경우도 마찬가지 입니다. 가장 큰 음수 두개, 가장 작은 양수 두개 조합을 확인하고 음수+양수 조합을 확인하면 시간을 더 단축시킬 수 있을 것 같습니다. 음수..
(python3) 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 신발끈 공식으로 다각형 면적 구하기 다각형의 점은 순서대로 주어집니다. 랜덤하게 주어지는 경우도 생각해봤는데, 랜덤한 좌표는 다각형이 특정되지 않기 때문에 풀이가 안되더라구요. 순서대로 주어진 좌표를 신발끈 공식에 넣어서 해결할 수 있습니다. 신발끈 공식은 오목, 볼록 다각형 모두에 공통적으로 적용됩니다. 코드 import sys def solution(input) : N = int(input().strip()) P = [] for _ in range(N) : P.app..
(python3) 20529번: 가장 가까운 세 사람의 심리적 거리 각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. www.acmicpc.net 이 문제 재밌네요!! 비둘기집 원리가 매우 간단한 이론이지만 재밌는 상황을 많이 만들어내는 것 같아요. 비둘기집 원리 비둘기집 원리란, "5칸짜리 집에 비둘기 6마리가 살려면 최소 한칸은 2마리 이상 살아야한다." 저는 16개의 mbti 를 2진법처럼 다뤄서 배열의 index 로 만들어서 사용했습니다. 잡다한 작업들이 많습니다. 다른 분의 코드를 보니 훨씬 깔끔한 코딩이 가능하더라구요..!! 일단 제 코드부터 소개하자면 코드 import sys def solution(input) : # 16개의 mbti MBTI = ['ISTJ', 'ISF..
(python3) 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 큐를 활용한 BFS 로 최단거리 구하기 시작점에서부터 다른 점들까지의 최단 거리를 구하는 문제이기 때문에 너비 우선 탐색으로 진행하면 해결할 수 있습니다. BFS 는 큐를 활용해서 구현하는게 가장 대표적입니다. 기본 아이디어는, 탐색을 진행할때마다 새로운 탐색 지점들을 큐에 넣고, 큐에서 지점을 하나씩 빼서 그 지점의 다음 단계 탐색을 진행하는걸 반복하는 겁니다. 그러면 깊이가 깊은 노드들이 큐의 뒷..
(python3) 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net best spot 찾기 우선순위를 가지는 조건이 여러 개라 차근차근 처리해주면 될 것 같습니다. 마지막 조건이 r,c가 작은 순서이므로 조건 우선순위대로 탐색하고, 동점의 경우 먼저 나온 칸을 best 로 유지시켜줬습니다. 이렇게 탐색하면 4점은 나오는 즉시 최종 best 가 됩니다. 만족도 계산하기 매 칸마다 그 학생이 좋아하는 학생 번호를 찾아야하기 때문에, 좋아하는 사람 정보의 경우 학생 번호를 key 로 관리해줄 필요가 있습..
