(프로그래머스, 파이썬) 힙 - [더 맵게, 디스크 컨트롤러, 이중우선순위큐]
2022. 10. 26. 17:05
PS/프로그래머스
예전에 힙 관련해서 풀고 나서 다시 보니까 느낌이 새로웠다. 역시 공부는 지속적으로 해야하는 것.. 문제 링크 문제의 조건은 다음과 같다. 모든 scoville의 값들이 K를 넘을 때 까지 '가장 작은 값, 두 번째로 작은 값'을 각각 빼서(pop) 곱해서 더하고 넣어라(push) 단, 모든 스코빌 값들이 K 이상의 값을 가질 수 없다면 -1을 리턴해야 한다. import heapq as h def solution(scoville, K): h.heapify(scoville) #힙으로 만들어준다. count_mix = 0 while scoville[0] < K: #오름차순 정렬이므로 첫 원소가 K보다 크거나 같을 때까지 반복한다. if len(scoville) == 1: #한 개 남은 원소가 K보다 작다면..
(프로그래머스, 파이썬) 해시 - 베스트 앨범
2022. 10. 26. 15:43
PS/프로그래머스
1. 해시(Hash)는 뭘까? 해시를 이해하기 위해서는 우선 해시 함수를 먼저 알아야 한다. 해시함수의 의미는 다음 정도로 생각할 수 있다. "임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수" (출처 : 위키) "데이터를 저장하고 찾는데 사용되는 자료 구조의 한 종류. 찾고자 하는 문자열을 함수로 처리해 얻은 값으로 데이터의 위치를 찾는 방법을 말한다" (출처 : 블로그) 함수를 통해 기존의 데이터를 처리한 그 값이 해시가 되는 것이고, 그 값을 이용해서 고유한 인덱스를 갖게끔 해서 이용하는 것이다. 일종의 암호화를 통해서 그 값을 특정하고, 분류할 수 있게끔 만드는 것이라고 생각이 든다. 2. 해시는 왜 쓰는 것일까? 공통된 것과 그렇지 않은 것 여러 정보를 가진 입력들이 각자 가지는 고유..
(백준, 파이썬) 방 번호
2022. 8. 3. 19:18
PS/BOJ
C 만지다가 막상 파이썬 하려니까 뭔가 예전보다 더듬거리는 느낌이다.. 1475 - 방 번호 문제 다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다. 다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.) 입력 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 필요한 세트의 개수를 출력한다. - 틀린 코드 - for문에 조건을 인풋으로 거는 걸 C언어에서 봐서 한번 따라해봤다. 0..
(백준, C) 핸드폰 요금
2022. 7. 18. 23:05
PS/BOJ
C 강의를 듣고 있는데, 최고의 실력향상은 뭐다? '적용하기' 바로 들어가보자. 1267 - 핸드폰 요금 문제 동호는 새악대로 T 통신사의 새 핸드폰 옴머나를 샀다. 새악대로 T 통신사는 동호에게 다음 두 가지 요금제 중 하나를 선택하라고 했다. 영식 요금제 민식 요금제 영식 요금제는 30초마다 10원씩 청구된다. 이 말은 만약 29초 또는 그 보다 적은 시간 통화를 했으면 10원이 청구된다. 만약 30초부터 59초 사이로 통화를 했으면 20원이 청구된다. 민식 요금제는 60초마다 15원씩 청구된다. 이 말은 만약 59초 또는 그 보다 적은 시간 통화를 했으면 15원이 청구된다. 만약 60초부터 119초 사이로 통화를 했으면 30원이 청구된다. 동호가 저번 달에 새악대로 T 통신사를 이용할 때 통화 시간..
(백준, 파이썬) 균형잡힌 세상 + 일기
2022. 7. 15. 21:48
PS/BOJ
요새 나라가 뒤숭숭하다. 안 좋은 일도 좀 있고.. 사실 평화로운 날이야 많겠지만. 4949 - 균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가..
(백준, 파이썬) 힙
2022. 7. 4. 19:13
PS/BOJ
스택, 큐를 배웠었고 이제 힙을 배울 차례다. 힙은 완전 이진 트리(한개의 노드에 두개의 자식노드)로 이뤄지고, 트리에서 특정 값을 찾는 방식으로 구현된다. 파이썬에는 heapq라는 모듈이 있으므로 편리하게 문제를 풀 수 있었다. 기본적으로 heapq의 heappop() 메소드는 최소값을 기준으로 하고, 최대값으로 하려면 음(-)의 부호를 붙여주면 된다. 나동빈님의 강의를 참고했다. 1927 - 최소 힙 문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ..
(백준, 파이썬)캠핑가서 ATM기에 사과 담기 게임
2022. 7. 1. 17:00
PS/BOJ
4796 - 캠핑 문제 등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만, 캠핑장에는 다음과 같은 경고문이 쓰여 있었다. 캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다. 강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가 기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까? 강산이는 조금 더 일반화해서 문제를 풀려고 한다. 캠핑장을 연속하는 P일 중, L일동안만 사용할 수 있다. 강산이는 이제 막 V일짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠동안 사용할 수 있을까? (1 < L < P < V) 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막..
(백준, 파이썬) 덩치감독 숌
2022. 6. 29. 22:49
PS/BOJ
7568 - 덩치 문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로..
(백준, 파이썬)블랙잭블랙블랙잭잭블랙 (06-28 해결)
2022. 6. 28. 16:48
PS/BOJ
(2022-06-14) 최근 CS50을 수강하면서, 시간복잡도와 의사코드에 대해 알게 되었다. 시간복잡도는 아직 익숙하지 않고, 더 배워야할 것 같지만, 의사코드는 이전에 내가 문제를 풀면서 주석을 달듯이 먼저 설계해보는 그런 과정인 것 같다. 이 스타일이 맘에 들어서 앞으로 문제를 풀 때는 의사코드를 작성해보고 구현하는 연습을 해보려고 한다. + 시간복잡도도 구해보고! --- 2주가 지난 지금 드디어 풀었다. -오늘 풀 문제- 브루트포스 알고리즘(Brute Force) : '야만적으로', '꼼꼼히', '모든 경우'를 찾는다. 2798 - 블랙잭 (https://www.acmicpc.net/problem/2798) 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘..
(백준, 파이썬) 분해합
2022. 6. 28. 11:47
PS/BOJ
2231 - 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. -맞힌 코드- 1 2 3 4 5 6 7 8 9 10 11 12 13 14..