본문 바로가기
728x90

백준

 (129)
[백준] 14729번 칠무해 [Python] - 정렬 소수점 셋째짜리까지 표시된 점수들 중 낮은 점수 7개 오름차순으로 출력 더보기 문제 조$($Joe$)$는 중앙대학교 교수이고, 논리회로 설계 과목을 담당하고 있다. 그는 수업을 하면서 7명의 학생을 제외한 나머지 학생들에게 좋은 학점을 주겠다고 약속을 하였다. Joe 교수님을 돕기 위해서 학생들의 최종 성적이 주어질 때, 그의 연구실인 You See Lab으로 데려갈 성적이 좋지 못한 7명의 학생, 칠무해의 성적을 뽑아보자. 입력 첫째 줄에 학생의 수 N$(8 ≤ N ≤ 10,000,000)$이 주어진다. 둘째 줄부터 N개의 줄에는 학생들의 성적이 무작위로 주어진다. 성적은 최소 0점부터 최대 100점까지 0.001 점 단위로 부여된다. 출력 하위 7명의 성적을 점수가 낮은 순으로 각 줄마다 출력한다. ..
[백준] 19637번 IF문 좀 대신 써줘 [Python] - 이진 탐색 주어진 전투력 기준마다 정해진 칭호가 있다. 전투력에 따라 칭호를 출력하는 문제 이진 탐색은 그리드 탐색$($처음부터 끝까지 모든 경우를 탐색$)$에 비해 빠르다. 우선 정렬된 경우에 유용하기 때문에, 정렬 되지 않은 자료에 대해서는 정렬이 필요하다. 이번 문제는 비내림차순으로 정렬되어 있는 자료가 주어지기 때문에 딱히 정렬할 필요는 없다. 모든 경우의 수가 $N$가지일 때, 이진 탐색은 대략 $log_{2}{N}$가지이다. 가장 많은 탐색을 해야하는 경우 100번의 탐색을 7번의 탐색으로 1000번의 탐색을 10번의 탐색으로 마칠 수 있다. 더보기 문제 게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다. 예를 들어, 전투력 10,000 이하의 캐릭터는..
[백준] 13413번 오셀로 재배치 [Python] 오셀로 말$($2개$)$의 위치를 바꾸거나, 말 1개를 뒤집기 위 두 가지 작업만으로 초기 상태 -> 목표 상태 까지의 최소 작업 횟수 구하는 문제 각 상태는 W와 B가 이어진 문자열 형태로 주어짐 더보기 문제 로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검정, 뒷면이 흰색으로 된 말이다. 세희의 목표는 로봇을 이용하여 처음 배치된 오셀로 말을 주어진 형태로 바꾸는 일을 하는 것이다. 아래의 예시를 참고하자. 초기 상태 목표 상태 ○●●○○ ○●○●○ 세희는 로봇을 이용해 2가지 작업 중 하나를 골라 진행할 수 있다. 배치된 말 중 임의의 2개의 말을 골라 서로의 위치..
[백준] 26005번 나뭇잎 학회 [Python] NxN개의 스위치 중에서 단 하나만 있는 정상 스위치는 상하좌우 중 하나의 스위치와 같이 한 번 누르면 작동한다. 어떠한 경우에도 정상 스위치를 구할 수 있는 최소한으로 누러야 하는 횟수를 구하는 문제 더보기 문제 기선이는 퀴즈를 좋아해서 알고리즘 학회에 들어가고자 하이아크에 방문하였다. 하지만 학회 문 앞에는 단 한 개의 전구, 여러 개의 스위치와 함께 다음과 같은 쪽지가 붙어있었다. 보이는 것과 같이 하나의 전구와 $N \times N$ 개의 스위치가 $N \times N$ 배열로 있습니다. 이 스위치 중 단 하나만 전구와 연결되어 있으며, 연결된 스위치를 누르면 전구가 깜빡입니다. 스위치에는 특수 장치가 적용되어 있어서 상하좌우로 인접한 두 개의 스위치를 동시에 눌러야만 합니다. 예를 들어 $N=3..
[백준] 28466번 볼링공 찾아주기 [Python] 볼링공의 무게와 보관할 사물함 번호가 입력 받아 저장하고, 볼링공의 무게가 주어지면 그 볼링공을 보관 중인 사물함 번호 출력하기 더보기 문제 동현이는 볼링을 사랑하는 훌륭한 프로그래머다. 오늘도 볼링을 치고 싶은 동현이는 자신의 볼링공 컬렉션을 보면서 어떤 볼링공을 가져갈지 고민에 빠졌다. 동현이는 매일의 컨디션에 따라 아주 미세한 무게까지 컨트롤하고 싶기 때문에 다양한 무게의 볼링공이 매우 많다. 볼링공을 관리하는 사물함에는 사물함 안에 들어 있는 볼링공들의 무게가 적혀 있고, 하나의 사물함에 여러 개의 볼링공이 들어갈 수 있다. 동현이는 오로지 볼링에만 집중하고 싶기 때문에 볼링공 관리는 여러분에게 맡기기로 했다. 동현이의 요청에 따라 볼링공을 관리해 보자! 요청은 다음과 같다. 1 x w: x번 사..
[백준] 3060번 욕심쟁이 돼지 [Python] - 등비수열 매일 N만큼의 사료로 돼지를 먹일 수 있다. N과 첫 날 돼지들이 먹은 양이 주어진다. 돼지들은 매일 전날 자신이 먹었던 양에 양 옆 돼지들과 맞은 편의 돼지가 먹었던 양까지 더해서 먹고 싶어한다. 돼지들의 요구를 들어줄 수 없게 되는 날을 구하는 문제 더보기 문제 유명한 농부 박현수는 돼지 6마리를 키우고 있다. 그는 하루에 한 번씩 돼지에게 맛있는 밥을 준다. 돼지는 원형 식탁에 앉아서 식사를 한다. 현수의 돼지들은 기억력이 뛰어나기 때문에 전 날 자신의 양쪽과 맞은편에 앉았던 돼지가 먹었던 양을 기억하고 있다. 또, 욕심도 많기 때문에, 그 만큼의 양을 추가하여 식사를 하기를 원한다. 예를 들어, 현수가 1번부터 6번까지 돼지에게 각각 3, 2, 7, 1, 5, 4만큼 밥을 주었다면, 2번 돼지는 ..
[백준] 14494번 다이나믹이 뭐예요? [Python] - 다이나믹 (1,1)에서 (n,m)까지 →, ↓, ↘의 세 방향만 사용해서 한 번에 한 칸씩 이동할 떄, 경우의 수 더보기 문제 안녕하세요~ 저는 오늘 다이나믹 프로그래밍$($동적 계획법$)$을 설명하기 위해 등장한 욱제예요! 다이나믹은 이름이 엄청 거창하지만 사실 이름에 비해 개념은 간단하답니다. 다이나믹의 기본 아이디어는 바로 이전에 계산한 값을 사용해서 $($= 이미 계산된 값을 사용해서, 어려운 말로 메모이제이션 한다고 해요$)$ 반복되는 똑같은 연산 횟수를 줄이는 거예요. 예를 들어서, 5번째 피보나치 수열을 구하는 F$($5$)$의 동작 과정을 살펴볼게요. 같은 함수가 불필요하게 많이 호출되는 것을 볼 수 있죠? F$($2$)$와 F$($3$)$을 미리 구해놓고 F$($4$)$를 구할 땐 미리 구해둔 F..
[백준] 3613번 Java vs C++ [Python] Java의 카멜 표기법과 C++의 스네이크 표기법 서로 바꿔서 출력하기 더보기 문제 Java 예찬론자 김동규와 C++ 옹호가 김동혁은 서로 어떤 프로그래밍 언어가 최고인지 몇 시간동안 토론을 하곤 했다. 동규는 Java가 명확하고 에러가 적은 프로그램을 만든다고 주장했고, 동혁이는 Java는 프로그램이 느리고, 긴 소스 코드를 갖는 점과 제네릭 배열의 인스턴스화의 무능력을 비웃었다. 또, 김동규와 김동혁은 변수 이름을 짓는 방식도 서로 달랐다. Java에서는 변수의 이름이 여러 단어로 이루어져있을 때, 다음과 같은 방법으로 변수명을 짓는다. 첫 단어는 소문자로 쓰고, 다음 단어부터는 첫 문자만 대문자로 쓴다. 또, 모든 단어는 붙여쓴다. 따라서 Java의 변수명은 javaIdentifier, longAn..
[백준] 1235번 학생 번호 [Python] 주어진 학생들을 구분할 수 있을 만큼 학번을 앞에서부터 삭제했을 때, 가장 짧은 길이의 학번 만들기 더보기 문제 이번에는 학생들을 더욱 효율적으로 관리하기 위해 학생마다 고유한 학생 번호를 부여하기로 하였다. 학생 번호는 0부터 9 사이의 숫자로 이루어진 문자열로, 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같다. 학생들의 번호를 부여해 놓고 보니, 김진영 조교는 어쩌면 번호가 지나치게 긴 것은 아닌가 싶은 생각이 들었다. 예를 들어 아래와 같은 7자리의 학생 번호를 보자. 이름번호 오민식 1212345 김형택 1212356 이동호 0033445 이처럼 학생 번호를 굳이 7자리로 하지 않고, 뒤에서 세 자리만을 추려서 남겨 놓아도 모든 학생들의 학생 번호를 서로 다르게 만들 수 있다. 이름..
[백준] 1213번 팰린드롬 만들기 [Python] 팰린드롬$($palindrome$)$: 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등 주어진 문자열로 팰린드롬 만들기 더보기 문제 임한수와 임문빈은 서로 사랑하는 사이이다. 임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다. 임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다. 임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오. 입력 첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다. 출력 첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hanso..
[백준] 14916번 거스름돈 [Python] 2원과 5원짜리로만 거스름돈 n원을 거슬러 주는데, 필요한 최소 동전의 개수 구하는 문제 더보기 문제 춘향이는 편의점 카운터에서 일한다. 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오. 예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다. 입력 첫째 줄에 거스름돈 액수 n$($1 ≤ n ≤ 100,000$)$이 주어진다. 출력 거스름돈 동전의 ..
[백준] 11656번 접미사 배열 [Python] 주어진 단어의 접미사를 사전순으로 한 줄에 하나씩 출력하는 문제 더보기 문제 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다. baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다. 문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. 출력 첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다. 단어를 앞..

티스토리툴바