본문 바로가기

전체 글

 (94)
[백준]_2606번 : 바이러스(파이썬 and C언어) 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 파이썬(dfs) 파이썬(bfs) C언어(dfs) bfs와 dfs 두 개의 방법으로 해결할 수 있는 문제이다. 파이썬(dfs) 문제 풀이의 기반이 되는 그래프를 먼저 그려야 한다. 여기서 말하는 그래프란 2차원 배열에 특정노드마다 어떤 노드들과 인접해 있는지 저장해 주는 그래프이다. 예를 들어 문제에서 예제로 제시된 을 보면 1 노드는 2 노드와 5 노드와 연결되어 있기 때문에 그래프에는 [ [ ], [ 2, 5 ] ...]와 같이 저장될 것이다. 저장하는 방법은 아래..
[백준]_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을 곱해준 상태로 집어넣는다...
[백준]_27964 : 콰트로치즈피자(파이썬 and C언어) 27964번: 콰트로치즈피자 치즈와 피자에 환장하는 비행씨는 매일같이 치즈피자를 사 먹다가 지갑이 거덜 나고 말았다. 만들어 먹는 것이 사 먹는 것보다 싸다는 것을 안 비행씨는 여러 가지 토핑을 가져와서 직접 피자를 www.acmicpc.net 전략(Python) 문자열을 잘 이용할 줄 알아야 하는 문제이다. 먼저 파이썬식 논리라면 중복된 토핑들을 제거해야 하기 때문에 입력받은 토핑들을 집합으로 나타낸 후 다시 리스트로 바꾸는 작업을 해야 한다. 또한 문자열 뒤에 있는 6개의 글자가 "Cheese"이기만 하면 토핑으로 인정되는 것이다. 이것은 파이썬의 기능인 슬라이싱으로 확인할 수 있다. 시도 1(Python) tr=int(input()) topping=list(set(list(map(str, input..
[백준]_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원으로 옮겨가는 방법이다. 이제 이 문제가 왜 그리디..

티스토리툴바