본문 바로가기

분류 전체보기

 (33)
[백준] 1267번 파이썬 풀이 https://www.acmicpc.net/problem/1267 1267번: 핸드폰 요금 동호가 저번 달에 이용한 통화의 개수 N이 주어진다. N은 20보다 작거나 같은 자연수이다. 둘째 줄에 통화 시간 N개가 주어진다. 통화 시간은 10,000보다 작거나 같은 자연수이다. www.acmicpc.net [문제] 동호는 새악대로 T 통신사의 새 핸드폰 옴머나를 샀다. 새악대로 T 통신사는 동호에게 다음 두 가지 요금제 중 하나를 선택하라고 했다. 1. 영식 요금제 2. 민식 요금제 영식 요금제는 30초마다 10원씩 청구된다. 이 말은 만약 29초 또는 그 보다 적은 시간 통화를 했으면 10원이 청구된다. 만약 30초부터 59초 사이로 통화를 했으면 20원이 청구된다. 민식 요금제는 60초마다 15원씩 청..
3. 이진탐색 알고리즘(binary_search) 이진 탐색(Binary_search) 이진 탐색이란 탐색의 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘이다. 입력 데이터가 많거나 탐색 범위의 크기가 매우 넓을 때 효과적으로 문제를 해결할 수 있다. 단, 오름차순으로 정렬되어 있는 리스트가 있어야 하며, 데이터가 무작위로 정렬되어 있다면 사용할 수 없다. 정렬된 데이터에서만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목푯값을 찾을 확률은 두배가 되므로 속도가 빠르다는 장점이 있다. 이진 탐색의 동작 과정 1. 시작 인덱스와 마지막 인덱스 사이의 중간 값을 중간 인덱스로 정한다. (이 때, 소수점 이하는 무시하고 중간 인덱스를 정한다.) 2. 중간 인덱스에 해당하는 데이터와 현재 찾으려는 데이터(타겟)이 같은지 비교한다. 3. 중간값이 ..
[백준] 10870번 파이썬 풀이 https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net [문제] 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. ( 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 5..
[백준] 1100번 파이썬 풀이 https://www.acmicpc.net/problem/1100 1100번: 하얀 칸 체스판은 8×8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램 www.acmicpc.net [문제] 체스판은 8×8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램을 작성하시오. [입력] 첫째 줄부터 8개의 줄에 체스판의 상태가 주어진다. ‘.’은 빈 칸이고, ‘F’는 위에 말이 있는 칸이다. [출력] 첫째 줄에 문제의 정답을 출력한다. [예제 입력 1..
2. 복잡도(Time complexity) 알고리즘의 실행시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다. 이 속도는 컴퓨터의 처리속도, 사용된 언어 종류, 컴파일러의 속도에 달려있다. 알고리즘의 실행시간은 두 부분으로 나누어 볼 수 있다. ㅇ 입력값의 크기에 따라 알고리즘의 실행시간을 검증할 수 있다. ㅇ 입력값의 크기에 따른 함수의 증가량 - 중요하지 않은 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한 성장률에 집중할 수 있는데 이것을 점금적 표기법(Asymptotic notation)이라고 부른다. - 점근적이라는 의미는 가장 큰 영향을 주는 항만 계산한다는 의미이다. 시간 복잡도 점근적 표기법을 알아보기 전에 시간복잡도라는 것이 무엇인지를 알아보자. 시간 복잡도는 문제를 해결하는 알고리즘의 성능을 표기하는 방법이다. 알고..
[백준] 1009번 파이썬 풀이 https://www.acmicpc.net/problem/1009 1009번: 분산처리 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000) www.acmicpc.net [문제] 재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다. 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... , 10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2..
1. 알고리즘이란? 알고리즘(Algorithm)이란? ㅇ 알고리즘의 의미 - 문제를 해결하기 위한 일련의 순서적인 계산/풀이 절차/방법으로, 컴퓨터 프로그램의 작성 시 기초가 된다. - 또한 요구되는 해로 이끄는 일련의 단계이지만, 이러한 절차/단계들이 보다 수학적으로 엄격하고 간결하게 다루어질 필요가 있다. ㅇ 알고리즘의 목적 - 궁극적으로 문제의 해결을 기계로 실행하기 위한 것 알고리즘의 특징 ㅇ 입력, 출력 - 입력은 없을 수도 있으나, 출력은 반드시 하나 이상 생성되어야 한다. ㅇ 유한성( Finiteness ) - 한정된 수의 작업 후에는, 반드시 유한 시간 내에 종료해야 한다. ㅇ 명확성( Definiteness ) - 각 단계는 단순 명확해야 하며, 모호하지 말아야 한다. ㅇ 유효성( Effectiveness ..
[백준] 1076번 파이썬 풀이 https://www.acmicpc.net/problem/1076 1076번: 저항 첫째 줄에 첫 번째 색, 둘째 줄에 두 번째 색, 셋째 줄에 세 번째 색이 주어진다. 위의 표에 있는 색만 입력으로 주어진다. www.acmicpc.net [문제] 전자 제품에는 저항이 들어간다. 저항은 색 3개를 이용해서 그 저항이 몇 옴인지 나타낸다. 처음 색 2개는 저항의 값이고, 마지막 색은 곱해야 하는 값이다. 저항의 값은 다음 표를 이용해서 구한다. 예를 들어, 저항의 색이 yellow, violet, red였다면 저항의 값은 4,700이 된다. [입력] 첫째 줄에 첫 번째 색, 둘째 줄에 두 번째 색, 셋째 줄에 세 번째 색이 주어진다. 위의 표에 있는 색만 입력으로 주어진다. [출력] 입력으로 주어진 저항의..
[백준] 1546번 파이썬 풀이 https://www.acmicpc.net/problem/1546 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net [문제] 세준이는 기말고사를 망쳤다. 세준이는 점수를 조작해서 집에 가져가기로 했다. 일단 세준이는 자기 점수중에 최댓값을 골랐다. 이 값을 M이라고 한다. 그러고 나서 모든 점수를 점수/M*100으로 고쳤다. 예를 들어, 세준이의 최고점이 70이고, 수학점수가 50이었으면 수학점수는 50/70*100이 되어 71.43점이 된다. 세준이의 성적을 위의 방법대로 새로 계산했을 때, 새로운 평균..
[백준] 1264번 파이썬 풀이 https://www.acmicpc.net/problem/1264 1264번: 모음의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 영어 대소문자, ',', '.', '!', '?', 공백으로 이루어진 문장이 주어진다. 각 줄은 최대 255글자로 이루어져 있다. 입력의 끝에는 한 줄 www.acmicpc.net [문제] 영문 문장을 입력받아 모음의 개수를 세는 프로그램을 작성하시오. 모음은 'a', 'e', 'i', 'o', 'u' 이며, 대문자 또는 소문자이다. [입력] 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 영어 대소문자,',', '.', '!', '?', 공백으로 이루어진 문장이 주어진다. 각 줄은 최대 255글자로 이루어져 있다. 입력의 끝에는 한 줄에..

티스토리툴바