파이썬 백준 2902번 브론즈2 https://www.acmicpc.net/problem/2902 2902번: KMP는 왜 KMP일까? 입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 ('-', 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드 www.acmicpc.net 문제 보기 분류: 구현, 문자열 문제 풀기 이름과 하이픈을 모두 리스트로 나누어 입력받는다. 하이픈 및 소문자는 모두 무시하고 대문자만 출력한다. 입력받은 문자형태의 리스트를 for loop 을 돌리면서 그 단위 문자가 대문자이면 연속하여 프린트한다. 코드 보기 import sys inputdata = sys.stdin.readline de..

파이썬 백준 1181번 실버5 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 보기 분류: 문자열, 행렬 문제 풀기 한 단계 한 단계 set() 과 sort() 함수를 사용하여 풀었다. 주어진 단어들을 리스트에 입력받고 set() 을 사용하여 중복제거 word_ls = list(set(word_ls)) sort() 를 사용하여 알파벳 순으로 정렬 word_ls.sort() sort(key = len) 을 사용하여 문자 길이 순으..

파이썬 백준 10026번 골드5 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 보기 분류: 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 풀기 2667번 단지번호붙이기 문제와 비슷하다. 지난번엔 집이 있는 위치를 표시한 숫자 1에 대해 DFS 를 실행하였다면, 이번 문제 적록색약에서는 방문여부에 대해서 그리고 다른 문자 즉 다른 색이 나오는지 까지 확인하여 DFS 를 돌린다. 색약이 아닌 경우와 색약인 경우를 분리해서 다뤄..

파이썬 백준 11724번 실버2 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 보기 분류: 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 풀기 "연결 요소의 개수" 라 하면 아무리 생각해도 간선의 개수밖에 떠오르지 않는다. 요소라 한다면 그 느낌은 더욱 작아지는 방향으로 나아가는 단위 물체 아닌가.. 문제 이해 부족으로 인해 검색을 해보고 서로 관련 없이 완전 분리된 ..

파이썬 백준 2667번 실버1 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 보기 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 풀기 그래프 탐색을 하는 문제이다. 연습을 위해 DFS 방법으로 접근을 하였다. 주어진 예제 입력에 따라 2차원 리스트로 집의 위치를 모두 town_map_input 에 입력받는다. town_map_input = [list(map(str, inputdata().split())) for..

파이썬 백준 11758번 골드5 https://www.acmicpc.net/problem/11758 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 문제 보기 분류: 기하학 문제 풀기 처음에는 점 p2 를 기준으로 p1 과 p3 에 대한 기울기 관계를 이용해 풀려고 하였다. 이때, 일반적으로 마구잡이 놓여있을 땐 상관이 없었는데 x 의 좌표가 같아지는 상황에서는 분모가 0 이 되어버려 또 다른 if 조건이 만들어져야 했다. if 조건을 줄줄이 ..

파이썬 백준 1018번 실버4 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 보기 분류: 브루트포스 알고리즘 문제 풀기 규칙 모양이 정제되지 않은 2차원 리스트를 저장하고 체스판으로 형성 가능한 8 by 8 에 대해 모든 경우를 따져보고 W 또는 B 으로 변경해야 할 최솟값을 찾는다. 8 x 8 로 자를 수 있는 위치의 기준은 2차원 배열의 왼쪽 위의 index 를 기준으로 하여 그 경우를 area_N 과 area_M 으로 모두 ..

파이썬 백준 1012번 실버2 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 보기 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 풀기 이 문제를 DFS 로 풀기 위해서 sys.setrecursionlimit(10000) 모듈을 추가해야 한다. 파이썬 기본 재귀 한도는 1000 이기에 재귀 깊이가 1000을 넘어가게 되는 경우 런타임 오류가 발생한다. 주어진 배추의 위치를 matrix 2차원 리스트에 저장한다. 이때 문제에..

파이썬 백준 2606번 실버3 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 보기 분류: 그래프 이론, DFS 문제 풀기 작동방식은 이해를 하였으나 아직 코드 형태가 친근하지 않은 DFS 로 접근해보는 문제이다. 컴퓨터의 개수와 연결된 개수를 입력 받고 연결된 두 노드간의 정보를 저장하기 위한 2차원 매트릭스를 작성한다. 그리고 컴퓨터의 개수보다 1개 더 많게 0으로 채워진 visited_dfs 를 만든다. (index 번호와 컴퓨터의 번호를..

파이썬 백준 1002번 실버3 https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 문제 보기 분류: 수학, 기하학 문제 풀기 어떤 두 개의 원이 2차원 평면 위에 존재할 수 있는 방법에 대해 묻는 문제이다. 문제에서 주어진 x1, y1, r1, x2, y2, r2 는 원의 중심 좌표와 반지름으로 생각하면 1. 두 원의 중심과 반지름이 완벽히 같을때 무한의 교점을 갖는다. if x1 == x2 and y1 == y2 and r1 == r2: print(-1) 2. 두 원의 중심 거리의 크기가 두 반지름..