문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 입력 첫 줄에 n (1 ≤ n ≤ 100,000)이 주..
문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보..
문제 화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다. 자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자. 입력 첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다...
팩토리얼은 간단하게 n!로 나타내며, 1부터 n까지의 모든 자연수를 1씩 더해가며 곱하는 연산을 가리킨다. 개념을 더 정확하게 파악하려면 1부터 n까지의 자연수가 아닌 n부터 1까지의 자연수를 곱하는 게 맞지만, 지금은 그게 중요한게 아니니까. 파이썬으로는 크게 세 가지 방법으로 팩토리얼을 구현할 수 있다. 물론 바텀업 방식의 동적계획법 등은 여기에선 빠져있다. 가장 먼저, 파이썬의 math 라이브러리에서 제공하는 기본 함수를 사용하자. 그냥 가져다 쓰면 된다. import sys import math n = int(sys.stdin.readline().rstrip()) print(math.factorial(n)) sys 라이브러리를 사용하지 않으면 세 줄로 팩토리얼 계산이 끝나버린다. 다음 방법은 재귀..
문제 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다. 짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다. 입력 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2
문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17, 19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다. 입력의 마지막에는 0이 주어진다. 출력 각 테스트 케이스에 대해서, n보다 크..
Config 일반적으로 맥북은 기본적으로 파이썬이 설치되어서 나온다. 내가 사용하는 m1 맥북 에어는 그중에서도 아예 파이썬 3가 달려서 나오는데, 이걸 업데이트 해서 사용하려고 하니 말리는 글들이 종종 있었다. 기본 설치된 파이썬은 그냥 두는 게 좋다고. 그럼 어떻게 하란 말이냐 봤더니, Homebrew를 통해 파이썬을 설치하고 업데이트 해서 개발 환경에선 해당 파이썬을 불러서 사용하는 걸 추천한다. 한 번에 정리된 글이 잘 보이지 않아서 그냥 내가 쓰기로. 일단 brew를 이용한 파이썬 설치. brew update brew를 먼저 최신버전으로 업데이트하고, brew install python 파이썬을 최신버전으로 설치한다. python --version pip --version 설치가 끝나면 각각 버..
문제 정수 n(0 ≤ n ≤ 4*10^9)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. 출력 각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다. 풀이 Trial Division 방법은 정확하게는 소인수분해를 할 때 사용되는 방법이다. 증명이라기보다는 간단하게, 주어진 수 n을 x * y로 분해했을 때 둘 중 하나는 반드시 n의 제곱근보다 작거나 같다는 성질을 이용한 판별법이다. 에라토스테네스의 체(O(N log log N))에 비하면 속도가 느리지만(O(sqrt(n))), 적당히 작은 수에선 괜..
알고리즘을 풀다가 최대공약수를 구해야 하는 문제가 나와, 별생각 없이 순진하게 아래와 같이 풀었다. import sys a, b = map(int, sys.stdin.readline().split()) x = max(a, b) y = min(a, b) while x % y != 0: z = x % y x = y y = z print(a * b // y) 유클리드 호제법을 사용해서 간단하게 풀었다고 생각하고 넘어갔는데.. 혹시나 해서 검색해보니 역시나 파이썬 math 라이브러리에는 최대공약수와 최소공배수를 구해주는 함수가 있었다! 그것도 유클리드 호제법을 이용해 최적화가 되어 있는! 적잖이 김이 빠지지만, 사용 방법은 아래와 같다. import math # 최대공약수 print(math.gcd(35, 65..
방금 알고리즘 문제를 풀다가 파이썬엔 무려 대칭차집합을 한 번에 찾아주는 연산이 있다는 사실에 충격을 받았다. 아무 생각도 없이 자바에서 푸는 것처럼 풀었다가 이게 웬걸.. 해서 문제를 하나하나 정리하기보단 집합과 관련된 연산을 정리하고 넘어가는 게 좋을 것 같아 여기에 글을 팠다. 설명할 내용은 이게 끝이고, 코드도 매우 짧지만, 강력하다. a = {2, 3, 5, 7, 9, 11} b = {1, 3, 5, 7, 9} a.add(13) a.update({17, 19}) a.remove(19) # 합집합 print(a | b) print(a.union(b)) # 교집합 print(a & b) print(a.intersection(b)) # 차집합 print(a - b) print(a.difference(..
- Total
- Today
- Yesterday
- 백준
- 야경
- 여행
- a6000
- Python
- 기술면접
- 세계일주
- java
- 칼이사
- 스트림
- RX100M5
- 스프링
- 세모
- Backjoon
- 지지
- 남미
- 동적계획법
- 알고리즘
- BOJ
- 중남미
- 맛집
- spring
- 면접 준비
- 리스트
- 세계여행
- Algorithm
- 유럽여행
- 유럽
- 파이썬
- 자바
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |