본문 바로가기

백준

 (47)
[백준]_11758번 : CCW(파이썬 and C언어) 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다. www.acmicpc.net 제목 그대로 ccw알고리즘 저격 문제이다. 심지어 ccw알고리즘을 구현하기만 하면 해결되는 문제이기 때문에 ccw가 무엇인지만 알고 있으면 그렇게 어려운 문제는 아니다. 질문 게시판에서 보이는 ccw를 사용하지 않은 풀이를 보니 왜 알고리즘을 공부해야 하는지 깨닫게 되었다. 전략 ccw는 Counter Clock Wise알고리즘을 뜻한다. ccw알고리즘은 복잡한 코드 대신 외적을 사용하여 세 점의..
[백준]_1931번 : 회의실 배정(파이썬 and C언어) 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 가장 많은 회의 수를 배정하게끔 코드를 짜야한다. 그렇다면 어떤 접근을 해야 할까? 먼저 문제를 푸는 데에 있어서 중요한 값들은 무엇이 있을까. 일단 회의실 배정을 많이 해야 되기 때문에 회의의 시작 시간과 마침 시간이 최대한 적어야 한다. 또한 직전에 끝난 회의 시간과 그다음에 시작할 회의의 시간 차이가 적어야 한다. 하지만 어느 것이 가장 중요하다고 할 수 있는가? 그렇지 않다. 바로 동시에 동등히 중요하다는 것이다. 예제와 같은 답이((1,4), (5,7), (8,11), (12,14)) 어떻게 나오게 되었는지 생각해보자. (1,4)는 존재하는 모든 타임테이블 중에서 가장..
[백준]_7576번 : 토마토(파이썬) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 다행히도 이 문제를 풀기 하루 전에 'Z', '유기농 배추', '쉬운 최단거리'와 같은 그래프 탐색 문제를 많이 풀어 단련이 되어 있는 상태로 푼 문제라 그런가 첫 번째 시도만에 초록색 "맞았습니다!!"를 띄워서 너무 기뻤다. 이번 해설에서는 기쁜 마음과 더불어 문제를 자세히 해설해 보겠다. 필자 또한 그래프 탐색 문제의 열쇠를 알기 전에 어떤 부분들이 이해가 안 되었는지를 중심으로 서술하고자 한다. 물론 이 분야를 다 깨우쳤다는 뜻은 절대 아니..
[백준]_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을 곱해준 상태로 집어넣는다...

티스토리툴바