본문 바로가기

백준

 (47)
[백준]_1764번 : 듣보잡(파이썬 and C언어) 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 특히 C언어로 짰을 때 얻을게 많았던 문제였다. 왜냐하면 파이썬에서는 정렬, 동일한 요소 인식 sort와 intersection으로 쉽게 얻을 수 있지만 C는 그런 기능을 스스로 만들어줘야 하기 때문에.. 따라서 다시 한번 파이썬에 감사하는 시간을 갖자. 이번 문제에서는 파이썬보다 C를 더 비중 있게 다루도록 하겠다. 시도 1(Python) import sys input = sys.stdin.readline nls = set() mls = set() N, M ..
[백준]_1461번 : 도서관(파이썬 and C언어) 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 그리디 알고리즘을 사용하는 문제. 그리디 알고리즘을 사용하기 위해서는 ( 최적의 해 ) == ( 순간 최적의 해 )을 만족해야 한다. 대표적인 예시로는 충분한 수량의 500원, 100원, 50원, 10원, 1원이 있을 때 N원을 만들기 위해 조합할 수 있는 최소의 동전 수를 구하는 문제가 있다. 전략은 결국 500원이 가장 큰 비중을 차지하니까 500원으로 N원을 채우다가 500원으로 더 이상 채울 수 없으면 100원으로 옮겨가는 방법이다. 이제 이 문제가 왜 그리디..
[백준]_4108번 : 지뢰 찾기(파이썬 and C언어) 4108번: 지뢰찾기 C개의 문자들이 포함된 R개의 줄을 출력한다. 단, 모든 '.' 대신 인접한 칸에 위치한 지뢰의 수로 변경해 출력한다. '*' 칸은 그대로 출력한다. 문자 사이에 공백이나 줄 사이에 공백 줄이 있어선 www.acmicpc.net 구현이어서 그런가 해야 될 것이 좀 많은 귀찮은 문제들 중 하나이다. 또한 여태까지 푼 문제들 중에서 문제 접근 방법이 파이썬과 C언어가 많이 차이 났던 문제인 것 같다. 먼저 파이썬식으로 전략을 세워보고 C를 위한 디테일은 그 이후에 생각해 보자. 전략 파이썬은 어차피 동적 배열이기 때문에 배열의 크기에 대한 걱정은 덜고 시작하는 것이다. 이 문제에서 가장 걸리는 것은 *을 어떻게 처리해야 그 주변 값들이 하나씩 증가할 것이냐 이다. 그래서 일단 다음과 같..
[백준]_1019번 : 책 페이지(파이썬 and C언어) 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 골드 1치고 문제가 매우 단순해서 바로 덤벼들었던 문제이다. 하지만 나는 함정에 걸려든 것이었다.. 문제를 naive 하게 페이지 숫자를 문자열로 쪼개고(203 -> 2, 0, 3) 각 쪼개진 원소들의 개수만큼 정답 배열 안에 대입하면 되겠다는 접근을 한 것이다. 하지만 이런 브루트 포스식 접근 방법은 페이지 수가 10억까지 주어지는 문제에서는 시간 초과가 나오기 일쑤다. 그래도 일단 브루트 포스식으로 접근한 코드를 소개하겠다. 통과하지도 못한 코드를 왜 소개하냐고? 왜냐하면 나중에 개수를 직접 셀 때 내가 제대로 셌는지 알아보..
[백준]_11726번 : 2xn 타일링(파이썬 and C언어) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 이 문제가 어렵게 느껴진 이유는 우리가 타일을 쌓는 접근 방식을 절대로 컴퓨터한테 옮길 수 없기 때문이다. 우리는 타일을 하나하나 배열해서 모든 경우의 수를 찾지만 컴퓨터는 고작 타일 하나도 쌓지 못하는 상황이다. 따라서 타일 배열이 가능한 경우의 수를 나열해 봐서 어떤 규칙이라도 있는지 찾아보자 n에 따라 가능한 배열의 경우의 수를 T(n)이라고 정의하자. 따라서 n을 4까지 조사하면 아래와 같은 결과를 얻을 수 있다. n T(n) 1 1 2 2 3 3 4 5 피보나치 냄새가 나긴 ..
[백준]_4948번 : 베르트랑 공준(파이썬 and C언어) 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 에라토스테네스의 체를 이용해서 시간 초과를 내지 않고 풀 수 있냐 없냐를 판정하는 문제이다. 사실상 전략이랄 것도 없어서 바로 코드로 들어가겠다. 시도 1(Python) import sys input = sys.stdin.readline def eratosthenes(limit): primes = [] is_prime = [1] * (limit + 1) is_prime[0] = is_prime[1] = 0 for number in range(2, int(..
[백준]_1543번 : 문서 검색(파이썬 and C언어) 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 문서에서 주어진 단어가 몇 번이나 포함되어 있는지 중복을 제외하고 세야 하는 문제이다. 예를 들어 ababababa의 문서가 주어지고 검색 단어가 aba라면 ababababa → ababababa 이므로 답은 2이다. 전략 따라서 이 문제를 풀기 위해서는 입력받은 문자열을 하나씩 쪼개어 배열에 저장한 뒤 검색 단어의 존재 여부에 따라 검사의 위치를 이동시켜 주는 방법을 선택해야 한다. 이해를 돕기 위해 위의 예시를 다시 사용하겠다. 0 인덱스부터 시작해서 찾고자 하는..
[백준]_1929번 : 소수 구하기(파이썬 and C언어) 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 전략 여느 때와 다름없이 검사할 범위가 큰 소수 문제는 에라토스테네스의 체를 사용하는 문제이다. 시간 초과가 안 나오게 조심해야 하는 문제들 중 하나이기 때문에 시간복잡도를 최소화시키면서 코딩을 해야 한다. 시도 1(Python) m,n=map(int,input().split()) for i in range(m,n+1): if i==1: continue for j in range(2,int(i**0.5)+1): if i%j==0: break else: print(i) 왠지 모르게 느리다(522..

티스토리툴바