본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 1924번 2007년 https://www.acmicpc.net/problem/1924 1924번: 2007년 첫째 줄에 빈 칸을 사이에 두고 x(1 ≤ x ≤ 12)와 y(1 ≤ y ≤ 31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. www.acmicpc.net 22/10/08 단순 구현 문제로, 파이썬의 datetime모듈을 사용했다. 문제 접근 방식: 파이썬의 datetime모듈에서 toordinal메서드를 활용하여 구현하였다. 이 메서드는 날짜를 입력받으면 1년 1월 1일로부터 그 날짜가 몇 일 지났는지를 반환하는 함수인데, 2007년 x월 y일이 2007년 1월 1일로부터 몇 일이 지났는가를 toordina..
[Python] 11719번 그대로 출력하기 2 https://www.acmicpc.net/problem/11719 11719번: 그대로 출력하기 2 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄이 주어질 수도 있고, 각 줄의 앞 뒤에 공백이 www.acmicpc.net 22/10/08 의외로 몇 번 틀렸던 문제로, 오답의 원인을 알아내면서 의외의 수확을 거둘 수 있었던 문제였다. 문제 접근 방식: 구현하는 것 자체는 어렵지 않은데, 몇 번 틀렸었다. 그 이유는 input대신에 sys.stdin.readline을 사용했다는 점이다. 나는 이 문제를 try except구문을 사용해서 EOFError가 되면 종료하는 형식으로 했는데, sys.st..
[Python] 2877번 4와 7 https://www.acmicpc.net/problem/2877 2877번: 4와 7 창영이는 4와 7로 이루어진 수를 좋아한다. 창영이가 좋아하는 수 중에 K번째 작은 수를 구해 출력하는 프로그램을 작성하시오. www.acmicpc.net 22/10/07 약간의 아이디어가 있으면 쉽게 풀 수 있는 문제로, 사람에 따라 더 쉽게 느껴질 수도 있는 문제라고 생각한다. 문제 접근 방식: 문제 해결의 가장 큰 핵심은 이진수이다. 이 아이디어는 나열하다 보니 알게 되었다. 4 7 ---- 한 자릿수(2개 있음) 44 47 74 77 ---- 두 자릿수(4개 있음) 444 447 474 477 744 747 774 777 ---- 세 자릿수(8개 있음) 7을 1로, 4를 0으로 간주하면 마치 4와 7이 채워지는..
[Python] 2661번 좋은수열 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 22/10/06 전형적인 백트래킹 문제로, 좋은 수열이 되는 조건을 잘 따라가며 시뮬레이션하면 되는 문제이다. 문제 접근 방식: 문제를 해설하기에 앞서, 먼저 N = 8일 때의 찾는 과정을 도식화한 그림을 보자. 우리는 좋은 수열 중 가장 작은 수열을 찾는 것이 목적이다. 이 그림은 이를 찾기 위해 3가지 조건을 지키면서 탐색을 진행하는 과정을 나타낸 것으로, 3가지 조건은 다음과 같다. 1. 가장 작은 수열..
[Python] 2212번 센서 / 13164번 행복 유치원 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 22/10/06 두 문제는 문제 설명과..
[Python] 2343번 기타 레슨 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 22/10/05 이분 탐색 문제로, 왜 이분 탐색으로 접근할 생각을 했냐고 묻는다면... 강의의 수가 최대 10만개이고, 강의의 길이는 최대 10000분이고, 블루레이 디스크의 최소 개수는 1개이기 때문에 가능한 블루레이의 크기는 최대 10만*10000 = 10억이다. 때문에 1분부터 10억분까지 일일이 선형으로 탐색하려면 시간이 너무 오래 걸릴 것 같아 이분 탐색으로 하기로 했다. 문제 접근 방식: 블..
[Python] 17845번 수강 과목 https://www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net 22/10/04 전형적인 배낭 문제이다. 문제 접근 방식: 이 문제에서는 서윤이가 공부에 투자할 수 있는 시간의 한계가 존재하므로, 서윤이가 쓸 수 있는 총 공부 시간의 한계, 다시 말해 이 문제에서는 N의 값을 배낭의 한계허용치라고 생각할 수 있다. 과목의 중요도의 합이 최대가 되도록 시간을 써야 하므로, 각 과목의 중요도는 배낭에 담는..
[Python] 9084번 동전 / 3067번 Coins https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net 22/10/03 배낭 문제 중 하나인데, 1차원 ..

티스토리툴바