본문 바로가기

Computer Science

[백준 / Python] 11052 : 카드 구매하기 문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 전설카드 레드카드 오렌지카드 퍼플카드 블루카드 청록카드 그린카드 그레이카드 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다. 민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카.. 더보기
[백준 / Python] 1463 : 1로 만들기 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. My code x = int(input()) dp = [0]*(x+1) for i in range(2, x+1): dp[i] = dp[i-1] + 1 if i % 2 == 0: dp[i] = min(dp[i], dp[i//2] + 1) if i % 3 == 0: dp[i].. 더보기
[백준 / Python] 6588 : 골드바흐의 추측 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다. 이 추측은 아직도 해결되지 않은 문제이다. 백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오. 입력 입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다. 각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n .. 더보기
[백준 / Python] 1676: 팩토리얼 0의 개수 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. My code n = int(input()) cnt = 0 while n > 0: cnt += n//5 n //= 5 print(cnt) TIL 정수론: 특정 숫자가 뒤에서부터 0을 가지는 개수는 5가 곱해진 수만큼이다. e.g: 5! = 5x4x3x2x1 = 120 더보기
[백준 / Python] 251: 수 정렬하기 2 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. My code import sys n = int(input()) num = [] for _ in range(n): num.append(int(sys.stdin.readline())) num.sort() for i in num: print(i) TIL Python 내장함수인 sort()는: Stable Sort이다. 즉, 중복된 값의 경우 입력 순서와 동일하게 정렬한다. O(NlogN)이다. 더보기
[백준 / Python] 1316: 그룹 단어 체커 문제 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. My code n = int(input()) word_list = [input() for i in range(n)] result = 0 # check def check(word): if len(word) == 1: return True else: passed = "" for idx, char in enumerate.. 더보기
17-03 ~ 17-04 Linked List 17-03. Linked List Linked List란? Linked list와 array의 차이를 알아보자. 배열은 메모리를 통짜로 받아들이고, linked list는 데이터 아이템의 메모리를 하나하나 받아온다.(malloc 함수를 이용하여 그떄그때 받아온다.) 단점 다음 데이터가 어디에 있는지 찾기 힘들다. 무조건 순차 접근(sequential access) 배열, 연결 리스트의 장단점 배열에서는 element라는 용어를 사용한 기억이 있을 것이다. 배열의 관점에서 '몇 번째 데이터' 등을 의미할 때는 요소를 이용하여 부르고, 데이터 자체를 의미할 때는 Item이라는 용어를 많이 사용한다. linked list를 통해 영화와 평점을 노드 요소로 가지는 자료구조를 완성해보자. #defi.. 더보기
17-01 ~ 17-02 영화 평점관리 연습문제 17-01. 영화 평점관리 연습문제 이번 부록에서는 data structure에 대해서 주로 다룰 것이다. 이 강의 뒷부분을 이해하기 위해서, 해당 문제를 스스로 풀어보기를 강력히 권장한다. 17장은 예제가 길어지므로, (코드를 따라서 치는 것보다) 이번 예제를 직접 작성해보고, 이후 이어지는 내용을 배우고 추후 작성했던 프로그램을 업그레이드 하는 방식으로 구현하면 재밌게 공부할 수 있을 것이다. #include // #include #include #include #include //// 01 #define TSIZE 45 #define LMAX 10 struct movie { /* data */ char title[TSIZE]; float rating; }; void read_file(struct m.. 더보기

티스토리툴바