본문 바로가기

알고리즘 문제 풀이60

[백준 2910번] 빈도 정렬 - 파이썬 https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 💡문제 분석 요약 입력으로 주어진 수열을 빈도가 많은 순으로 정렬한 다음 출력한다. 💡알고리즘 설계 1. 해시에 해당 숫자가 저장된 빈도를 저장한다. 2. 해시의 값을 기준으로, 빈도가 높은 순으로 정렬한다. 3, for문을 이용해 해시의 값 만큼 해당 숫자를 출력한다. 💡코드 import sys input = sys.stdin.readline N, C=map(int, input().split()) message=list(map(int, .. 2024. 4. 13.
[백준 9017번] 크로스 컨트리 - 파이썬 https://www.acmicpc.net/problem/9017 9017번: 크로스 컨트리 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 케이스로 주어진다. 입력 파일의 첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 T 가 주어진다. 두 번째 줄부터는 두 줄에 하나의 www.acmicpc.net 💡문제 분석 요약 크로스 컨트리 달리기는 주자들이 자연적인 야외의 지형에 만들어진 코스를 달리는 운동 경기이다. 경주 코스는 일반적으로 4에서 12 킬로미터이며, 숲이나 넓은 땅을 통과하는 풀과 흙으로 된 지면과 언덕과 평평한 지형을 포함한다. 이 경기는 주자들의 개인성적을 매기고, 이를 가지고 팀의 점수를 계산한다. 한 팀은 여섯 명의 선수로 구성되며, 팀 점수는 상위 네 명의 주자의 점수를 .. 2024. 4. 13.
[백준 2607번] 비슷한 단어 - 파이썬 https://www.acmicpc.net/problem/2607 2607번: 비슷한 단어첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이www.acmicpc.net💡문제 분석 요약영문 알파벳 대문자로 이루어진 두 단어가 다음의 두 가지 조건을 만족하면 같은 구성을 갖는다고 말한다.두 개의 단어가 같은 종류의 문자로 이루어져 있다.같은 문자는 같은 개수 만큼 있다.예를 들어 "DOG"와 "GOD"은 둘 다 'D', 'G', 'O' 세 종류의 문자로 이루어져 있으며 양쪽 모두 'D', 'G', 'O' 가 하나씩 있으므로 이 둘은 같은 구성을 갖는다. 하지만 "G.. 2024. 4. 7.
[백준 13335번] 트럭 - 파이썬 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 💡문제 분석 요약 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit ti.. 2024. 4. 7.
[백준 18870번] 좌표 압축 - 파이썬 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 💡문제 분석 요약 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 💡알고리즘 설.. 2024. 3. 31.
[백준 19583번] 싸이버개강총회 - 파이썬 https://www.acmicpc.net/problem/19583 19583번: 싸이버개강총회 첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤ 23:59) 각 시간은 HH:MM의 형식으로 주어진다. 두번째 줄부터는 www.acmicpc.net 💡문제 분석 요약 개강총회가 시작하기 전에 채팅 기록이 있고, 개강총회가 끝난 후 채팅 기록이 있는 사람의 수를 출력한다. 💡알고리즘 설계 1. 개강총회의 시작시간, 끝난 시간, 스트리밍 종료 시간을 입력받는다. 2. 시와 분으로 입력된 시간을 분 단위로 변환한다. 3. 채팅 시간과 닉네임을 입력받고, 채팅 시간을 분 단위로 변환한다. 4. 채팅 시간이 시작 .. 2024. 3. 31.
[백준 1966번] 프린터 큐 - 파이썬 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 💡문제 분석 요약 가장 중요한 문서를 먼저 프린터하고, 현재 문서보다 더 중요한 문서가 있을 경우 현재 문서를 맨 뒤 순서로 보낸다. 내가 원하는 문서는 몇번째로 출력되는가? 💡알고리즘 설계 1. 현재 문서 리스트에서 가장 중요도가 높은 문서의 중요도를 구한다. 2. 현재 문서보다 더 중요한 문서가 있을 경우, 현재 문서를 제일 뒷 순서로 보낸다. 3. 현재 문서가 가장 중요한 문서일 경우, 문서를 .. 2024. 3. 23.
[백준 5397번] 키로거 - 파이썬 https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 💡문제 분석 요약 글자를 입력받고, 가 입력될 경우엔 커서를 오른쪽으로 이동하여 글자를 입력한다. -가 입력될 경우 커서 왼쪽의 글자를 삭제한다. 💡알고리즘 설계 스택과 연결리스트로 풀 수 있는 문제이다. 커서를 index로 두고, list.insert(index, c)로 해당 위치에 글자를 삽입하는 방법은 insert()의 시간복잡도가 O(N)이고, 문자열의 최대 길이가 백만이므로 시간초.. 2024. 3. 23.
[백준 2630번] 색종이 만들기 - 파이썬 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.www.acmicpc.net 💡문제 분석 요약아래와 같이 정사각형 모양으로 나누어 진 종이가 있을 때, 파란색 종이의 개수와 흰색 종이의 개수를 구하여라. 💡알고리즘 설계현재 칸의 종이 색과 첫번째 칸의 종이의 색이 다르면 현재 종이를 4등분으로 자르고, 다시 탐색한다.현재 종이에 있는 모든 칸이 색깔이 같다면, 그 색의 count를 하나 더한다.1. 종이의 색 정보를 입력받는다2. cut 함수를 .. 2024. 3. 16.

티스토리툴바