파이썬 백준 1946번 실버1 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 보기 분류: 그리디 알고리즘, 정렬 문제 풀기 순위를 2차원 리스트로 입력받아 오름차순 정렬을 하고 순차적인 서류 등수 순번대로 면접 등수를 비교하여 우위에 있는 지원자를 찾는다. 조건을 만족할때 hired 를 하나씩 늘려 선발되는 지원자의 수를 출력한다. 코드 보기 import sys inputdata = sys.stdin.readline..

파이썬 백준 13023번 골드5 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 보기 분류: 그래프 탐색, 깊이 우선 탐색 문제 풀기 사람 다섯명이 연속적으로 주루룩 4번 이상의 연결이 형성되면 문제에서 제시한 관계가 만족한다. 맞으면 1, 아니면 0. 주어진 입력을 graph (relationships) 로 저장하여 모든 사람에 대해 연속 4번의 관계가 만족하는지 모두 탐색해 본다. 이때, DFS 가 재귀함수로 4번이 실행되면 fnDFS 를 result == True 로 나와 관계를 만족하여 1 을 출력하고, 그렇지 않고 4번의 재귀가 일어나..

파이썬 백준 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차원 리스트에 저장한다. 이때 문제에..