https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 합계, 중앙값, 최빈값, 범위 위 4가지만 구하면 되는 문제이다. 심지어 N도 홀수로 주어져서 중앙값 구하기가 더 수월하다 그럼에도 불구하고, 이렇게 글을 작성하는 이유는 바로 'Counter' 때문이다. Counter를 사용하게 되면 리스트에 해당 값이 몇번 등장했는지 알아서 count 해준다!! most_common이라는 함수를 호출하게 되면 (키 : 값) 쌍으로 이루어진 튜플들이 모인 객체를 반환하는데, ..
https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net replace함수를 이용해 치환해주는 문제이다. 변수.replace (old, new, count) 형식인데, 변수에 있는 old 문자를 new 문자로 바꾸는 함수이다. count는 몇번 바꿀지 지정해주는 것이다. 만약 s= 'oxox' 라는 문자열이 있을 때 s.replace('ox', '*', 1) 이라고 하면 '*ox' 라는 결과가 되고, count를 2..
https://www.acmicpc.net/problem/11758 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 문제 제목 그대로 CCW 알고리즘을 이용하여 푸는 문제이다. CCW 알고리즘은 벡터의 외적을 활용해 푸는 알고리즘으로, 학창시절에 배웠던 신발끈 공식을 적용하면 된다. 선분 AB를 u라 하고, AC를 v라 할 때, 위와 같은 외적 공식을 적용할 수 있다. θ 가 180 < θ < 360 이면 시계방향이고, sin θ 값이 음수이다..
https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 다른 사람들의 풀이보다 시간복잡도가 뒤쳐지지만, TLE도 아니고 스스로 풀었으니까 만족한다 ㅋㅎ 우선 입력범위에 해당 하는 소수들은 모조리 골라준다. 그리고 bfs를 시작하여, 현재 기준이 되는 소수와 단 한자리만 다르면서 아직 방문하지 않은 '소수'를 큐에 넣고 탐색을 이어간다. 한마디로 소수 판정 + bfs 이다. import sys from collections import deque #sys.set..
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 트리 재귀 순회 문제이다. 이런 문제를 몇번 풀어보긴 했지만, 익숙하지 않아서 꽤 애를 먹었다. 알고리즘은 뭔가 답답할 땐 항상 그림을 그리며 직접 손으로 따라가보자! --설명-- 1. (0,8)을 넘겨준다 2. mid는 end+1로 설정하고, ( 아래 for문에서 mid값이 갱신되지 않는다면, end를 그대로 넘겨야 하는데 넘길 때 -1을 해주므로 ) 3. start를 pivot 삼..
https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 가장 기본적인 최장 거리 거리 수열 문제이다. O(n^2)의 시간복잡도를 가지기 때문! 해당 알고리즘은 백준에 '가장 긴 증가하는 부분 수열' 시리즈를 풀어보면 좋다 현재 위치 기준으로 이전 위치들을 탐색하며 본인보다 작은게 있다면 dp 값을 최대로 업데이트 해주는 방식이다. import sys #from collections import deque #import heapq #sys.setrecursion..
