1. 문제 설명 (1) 곱하기 혹은 더하기 각 자리가 숫자(0~9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하여 숫자 사이에 '*' 혹은 '+' 연산자를 넣는다. 결과적으로 만들어 질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정한다. 연산 결과는 항상 20억 이하의 정수가 되도록 입력한다. (2) 입력 조건 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어진다.(1
1. 문제 설명 (1) 모험가 길드 한 마을에 N명의 모험가가 존재한다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정한다. 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하시오. (2) 입력 조건 첫째 줄에 모험가의 수 N이 주어집니다. (1 = i: # 지금까지 모인 멤버의 수가 공포도 보다 크면 그룹 생성 groups += 1 member = 0 5. 해설 공포도가 낮은 모험가부터 오름차순으로 정렬한다. 각 공포도의 단계마다 반복문을 통해 멤버를 추가하는데, 누적된 멤버가 현재 공포도 보다 같거나 높은 경우 그룹을 생성한다. 누적..
문제 출처 : algospot.com :: TSP2 algospot.com :: TSP2 Traveling Salesman Problem 2 문제 정보 문제 NP-Complete 문제의 가장 유명한 예 중 하나인 여행하는 외판원 문제 (Traveling Salesman Problem) 은, 여러 개의 도시와 그 도시 간의 거리가 주어졌을 때, 각 도시를 algospot.com 1. 함수의 정의 바꾸기 6.7 단원(6.7 예제 : 최적화 문제 - 여행하는 외판원 문제(Python) (tistory.com))에서 완전 탐색 알고리즘을 통해 이 문제를 해결한 전력이 있다. 전에는 n개의 도시들에 대해 n!개의 경로를 모두 생성하는 방법을 사용했는데, n이 15만 되더라도 계산이 불가능할 지경이다. 또한, sh..
문제 출처 : algospot.com :: DRAGON algospot.com :: DRAGON 드래곤 커브 문제 정보 문제 드래곤 커브(Dragon curve)는 간단한 수학 규칙으로 그릴 수 있는 그림으로, 위 그림같은 형태를 지닙니다. 드래곤 커브는 선분 하나에서 시작해서 간단한 규칙으로 이 algospot.com 1. p번째 글자를 찾는 함수 작성하기 (1) 함수 설계하기 우선 맨 앞에서 전체 드래곤 커브 문자열을 생성하는 알고리즘을 만들고, 이것을 기반으로 p번째 글자를 찾는 알고리즘을 작성해본다. 드래곤 커브 문자열을 만드는 방법을 재귀적인 구현으로 만든다. 처음 주어진 정보는 0세대 문자열인 FX(=seed)와 세대 수 n(=generations)이다. 이를 전달받는 함수 curve( )를 ..

문제 출처 : algospot.com :: KLIS algospot.com :: KLIS K-th Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있 algospot.com 1. 문제 분석 이전의 예제와 문제(8.4절 참고)들을 통해서 최대 증가 부분 수열 중 가장 긴 것을 찾아낸 경험이 있다. 이를 바탕으로 위 문제를 해결하기 위해서는 다음의 과정을 거쳐야 한다. 1. 바탕이 되는 최적화 문제를 푼다. 2. 최적화 문제의 최적해를 세는 문제를 푼다. 3. 답의 수를 기반으로 답안을 재구성한다...

문제 출처 : algospot.com :: MORSE algospot.com :: MORSE 모스 부호 사전 문제 정보 문제 모스 부호(Morse code)는 전화가 없던 시절 무선 전신에 주로 사용하던 코드로, 짧은 신호(단점, o)와 긴 신호(장점, -)를 섞어 글자를 표현하는 표현방식입니다. 예를 algospot.com 1. 모든 신호 만들기(완전 탐색 알고리즘) (1) 문제 분석 이 문제처럼 문제의 모든 답을 사전순으로 나열했을 때, 이 중 k번째에 오는 답을 구하라는 문제가 종종 있다. 답의 개수가 적은 경우에는 모든 답을 만들어 정렬하고 k번째 답을 반환할 수도 있지만 현실은 그렇지 못 한 경우가 대부분이다. 기존의 동적 계획법 문제를 해결할 때, 완전 탐색으로 시작했던 것 처럼 이런 형태의 ..

문제 출처 : algospot.com :: OCR algospot.com :: OCR 광학 문자 인식 문제 정보 문제 알림: 채점 서버 속도 문제로 시간 제한을 60초로 늘리고, 테스트 케이스 수를 20으로 줄입니다. 광학 문자 인식(Optical Character Recognition)은 사람이 쓰거나 기계로 인 algospot.com 1. 문제 분석 이 문제에서 어려운 부분은 입력에 주어진 요구 조건을 수학적으로 풀어 쓰고 정형화 하는 부분이다. 또한, 원문이 생성되는 과정이 '8.16 문제 : 두니발 박사의 탈옥'에서 소개된 마르코프 연쇄 모델을 따른다. 마르코프 연쇄 유한개의 상태가 존재한다. 매 시간마다 상태가 변경된다. 어떤 상태 a에서 다른 상태 b로 옮겨갈 확률은 현재 상태 a에 의해서만 ..
문제 출처 : algospot.com :: PACKING algospot.com :: PACKING 여행 짐 싸기 문제 정보 문제 여행을 떠나기 전날까지 절대 짐을 싸지 않는 버릇이 있는 재훈이는 오늘도 비행기 타기 전날에야 가방을 싸기 위해 자리에 앉았습니다. 비행기 규정상 재훈이는 algospot.com 1. 문제 분석 (1) 완전 탐색 알고리즘 물건의 모든 조합을 하나하나 검사하고 이들 중 최적의 조합을 찾아내는 완전 탐색 알고리즘부터 시작 각 물건에 대해 가져가거나 말거나 두 가지의 선택이 존재한다. 따라서 전체 n개의 물건에 대해 2^n개의 조합이 있고 이를 통해 다음과 같은 부분 문제를 얻을 수 있다. pack(items) = 지금까지 모든 물건들의 목록이 items에 주어질 때, 남은 용량을..
- Total
- Today
- Yesterday
- 난이도:하
- k번째 답 계산하기
- 카카오
- 비트 마스크
- 동적 계획법
- 프로그래밍 대회에서 배우는 알고리즘 문제해결전략
- 구현
- 난이도:중
- 마르코프 연쇄
- 탐욕법
- python
- 종만북
- 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략
- 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략
- 프로그래머스
- 파이썬
- 그리디
- 난이도:상
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
31 |