본문 바로가기

알고리즘

[python] algospot SNAIL 문제 깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다. 앞으로 m 일간 각 날짜에 비가 올 확률이 정확히 75%일 전망입니다. m 일 안에 달팽이가 우물 끝까지 올라갈 확률을 계산하는 프로그램을 작성하세요. -> 문제 링크 : https://algospot.com/judge/problem/read/SNAIL algospot.com :: SNAIL 달팽이 문제 정보 문제 깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 � algos.. 더보기
[python] algospot Wildcard 문제풀이 문제 와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다. 예를 들어 와일드 카드 he?p 는 파일명 help 에도, heap 에도 매치되지만, helpp 에는 매치되지 않는다. 와일드 카드 *p* 는 파일명 help 에도, papa 에도 매치되지만, hello 에는 매치되지 않는다. 와일드카드 문자열과 함께 파일명의 집합이 주어질 때, 그 중 매치되는 파일명들을 찾아내는 프로그램을 작성하시오. 문제풀이 이 문제에서 핵심은 *이다. 와일드카드 *가 나왔을 때 이 문자가 파일 이름에서 몇개.. 더보기
[python] algospot PI 문제풀이 문제 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다. 이 때, 각 조각들의 난이도는 다음과 같이 정해집니다. 모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1 숫자가 1씩 단조 증가하거나 단조 감소할 때 (예: 23456, 3210) 난이도: 2 두 개의 숫자가 번갈아 가며 출현할 때 (예: 323, 54545) 난이도: 4 숫자가 등차 수열을 이룰 때 (예: 147, 8642) 난이도: 5 그 외의 경.. 더보기
[python] algospot JLIS 문제 두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부르기로 합시다. 이 중 가장 긴 수열을 합친 LIS(JLIS, Joined Longest Increasing Subsequence)이라고 부릅시다. 예를 들어 '1 3 4 7 9' 은 '1 9 4' 와 '3 4 7' 의 JLIS입니다. '1 9' 와 '3 4 7' 을 합쳐 '1 3 4 7 9'를 얻을 수 있기 때문이지요. A 와 B 가 주어질 때, JLIS의 길이를 계산하는 프로그램을 작성하세요. -> 문제 링크 : https://algospot.com/judge/problem/read/JLIS algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열에.. 더보기
[python] baekjoon 가장 큰 증가 부분 수열 문제 풀이 문제 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다. 수열 A가 주어졌을 때, 합이 가장 큰 증가 부분 수열의 합을 출력하시오. 문제풀이 수열의 크기는 최대 1000으로 주어진다. 가장 단순한 방법으로는 만들 수 있는 모든 수열을 만들어보고 증가 부분 수열 중 최댓값을 찾는 것이다. 하지만 이 방법은 O(2^1000)이라는 엄청난 시간이 걸린다. 이 문제는 부분문제로 쪼갠 뒤 해결할 수 있다. 현재 문제가 인덱스 i부터 시.. 더보기
[python] algospot FENCE 문제풀이 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/FENCE algospot.com :: FENCE 울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체 algospot.com 문제풀이 판자의 수가 최대 20000이기에 모든 위치를 탐색하며 그 위치에 해당하는 최대 넓이를 구하려고 한다면 O(N^2)이 나와 시간 초과가 된다. 그렇기에 N인 모든 위치를 탐색하지 않는 방법이 필요하다. 분할 정복 방법을 이용해서 N인 탐색범위를 줄여보자. 전체 막대 수에서 반을 갈라보자. 그렇다면 최대 크기의 직사각형이 만들어지는 위치는 3개 .. 더보기
[python] algospot QuadTree 문제풀이 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 쿼드 트리로 압축된 흑백 그림이 주어졌을 때, 이 그림을 상하로 뒤집은 그림 을 쿼드 트리 압축해서 출력하는 프로그램을 작성하세요. -> 문제 링크 : https://algospot.com/judge/problem/read/QUADTREE algospot.com :: QUADTREE 쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적 algospot.com 문제풀이 문제의 조건을 보면 원본 그림의 크기가 2^20 x 2^20이.. 더보기
[python] algospot STRJOIN 문제풀이 문제 void strcat(char* dest, const char* src) { // dest 의 마지막 위치를 찾는다 while(*dest) ++dest; // src 를 한 글자씩 dest 에 옮겨 붙인다 while(*src) *(dest++) = *(src++); // 문자열의 끝을 알리는 \0 을 추가한다 *dest = 0; } 위의 strcat 함수를 이용해 n 개의 문자열을 순서와 상관없이 합쳐서 한 개의 문자열로 만들고 싶습니다. 순서가 상관 없다는 말은 {al,go,spot} 을 spotalgo 로 합치든 alspotgo 로 합치든 상관 없다는 의미입니다. 그러나 문자열을 합치는 순서에 따라 전체 비용이 달라질 수 있습니다. 예를 들어 먼저 al 과 go 를 합치고 (2+2=4), 이것을.. 더보기

티스토리툴바