백준/Silver(1~5) (33) 썸네일형 리스트형 [백준]_20920번 : 영단어 암기는 괴로워(파이썬) 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 짜증 나는 조건들이 심지어 우선순위를 이루고 있는 문제이다. 가장 먼저 떠올랐던 아이디어는 단어 길이가 M 이상인 단어들만 뽑아서 우선순위대로 [-(나온 횟수), -(길이), '단어']으로 구성된 리스트를 새로운 리스트([[...], [...], ...])에 전부 때려 박고 sort 해주면 간단히 해결될 문제라고 생각했다. 나온 횟수와 길이를 음수로 저장하는 이유는 sort를 하게 되면 맨 앞의 .. [백준]_1697번 : 숨바꼭질(파이썬) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 리스트 2개를 동시에 나눠서 관찰해야 되는 문제였다. 한 개는 이동 횟수를 추적하는 리스트이고 다른 하나는 너비 우선 탐색에 이용될 deque 배열이다. 전략 먼저 n, k를 입력 받을 것이다. import sys from collections import deque input = sys.stdin.readline n, k = map(int, input().split()) 이제부터 설명의 편의를 위해 n대신 백준에 예시로 나온 대로 5.. [백준]_18870번 : 좌표 압축(파이썬 and C언어) 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 단순해 보이는 문제이지만 자칫하면 시간 초과나 메모리 초과로 이어질 수 있는 문제이다. 일단 파이썬으로는 어떤 방식으로 접근해야 하는지 생각해 보자. 전략(Python) 예시 입력들을 보아하니 원소 a보다 작은 숫자의 종류가 몇개인지 구하는 것임을 알 수 있다. 즉 중복을 제외하고 세어야 하는 것이다. 하지만 동시에 출력을 위해서는 중복을 제거하지 않은 리스트를 통해서 해야 한다. 그래서 다음과 같은 생각을 할 .. [백준]_11279번 : 최대 힙(파이썬 and C언어) 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 전략 파이썬에서는 그냥 리스트로 입력받고 최댓값을 max를 통해 도출하면 시간이 너무 많이 걸릴 것이기 때문에 파이썬에서 제공해주고 있는 heapq를 사용하자. heapq는 특정 리스트와 값을 주면 자동으로 정렬 기능을 수행해 준다. 그리고 heappop은 특정 리스트의 첫 번째 요소를 꺼내줌과 동시에 리스트에서 제거해 준다. 하지만 우리는 최댓값을 제거해야 하지 않는가? 따라서 값을 리스트에 집어넣을 때는 -1을 곱해준 상태로 집어넣는다... [백준]_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 .. [백준]_4108번 : 지뢰 찾기(파이썬 and C언어) 4108번: 지뢰찾기 C개의 문자들이 포함된 R개의 줄을 출력한다. 단, 모든 '.' 대신 인접한 칸에 위치한 지뢰의 수로 변경해 출력한다. '*' 칸은 그대로 출력한다. 문자 사이에 공백이나 줄 사이에 공백 줄이 있어선 www.acmicpc.net 구현이어서 그런가 해야 될 것이 좀 많은 귀찮은 문제들 중 하나이다. 또한 여태까지 푼 문제들 중에서 문제 접근 방법이 파이썬과 C언어가 많이 차이 났던 문제인 것 같다. 먼저 파이썬식으로 전략을 세워보고 C를 위한 디테일은 그 이후에 생각해 보자. 전략 파이썬은 어차피 동적 배열이기 때문에 배열의 크기에 대한 걱정은 덜고 시작하는 것이다. 이 문제에서 가장 걸리는 것은 *을 어떻게 처리해야 그 주변 값들이 하나씩 증가할 것이냐 이다. 그래서 일단 다음과 같.. [백준]_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(.. 이전 1 2 3 4 5 다음
