kkh1902's Algorithm Study

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 과정 전형적인 DFS, BFS 문제로 두 가지 방법 모두 풀 수 있는 문제입니다. 풀이 ① BFS 그래프의 탐색 시작점을 모르기 때문에 전체를 돌면서 1인 지점에서 탐색을 시작합니다. 탐색 중 1인 부분은 0으로 바꿔 다시 방문하지 않도록 하고 한 번의 BFS가 끝나게 되면 더 이상 확장이 불가능 하므로 마을 하나가 탄생합니다. 이 마을안의 1의 개수들을 출력하면 되므로 다음 코드와 같이 count를 반환하면 됩니다. from collections impor..

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제풀이 경우 4가지에 따라서 insert를 해준다고 생각을 하였다. 그러나 시간 복잡도가 너무 나왔다. 경우에 따라 스택으로 (자료구조)로 계산하니 통과하였다. 디테일 : 입력을 받을때 여러줄로 받을 필요 없이 range에서도 받을 수 있다. 코드 내풀이 import sys word = sys.stdin.readline().strip() word = list(word) n = int(sys.std..

https://www.acmicpc.net/problem/9093 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net 문제 접근 핵심은 문자열을 거꾸로 정렬하는 것이다. 방법1 . 슬라이싱 사용 방법2. join(reversed(string))사용 방법3. Stack 사용 방법4 for loop 사용 ( revstr = i + revstr) 문제 풀이 슬라이싱 사용 입력을 받자마자 거꾸로 정렬해서 출력 end= ' ' 붙여서 엔터 방지 시킨다. import sys n = int(sys.stdin.readl..

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 풀이 최빈 값을 구하는 게 핵심이다. Counter 라이브러리를 사용해서 횟수에 따라서 딕셔너리를 만들어주면 라이브러리내 most_common() 함수를 사용해 두번째 인자를 가져온다. 코드 내풀이 n = int(input()) nums = [] for _ in range(n) : nums.append(int(input())) # 산술평균 print(round(sum(nums)/n)) # 중앙값 nums.sor..

13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제풀이 n = int(input()) // 4 a = list(map(int, input().split())) // 2 3 1 b = list(map(int, input().split())) // 5 2 4 1 res = 0 m = b[0] for i in range(n-1): if b[i]

1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제풀이 a = input().split('-') num= [] for i in a : partsum = 0 s = i.split('+') for j in s: partsum += int(j) num.append(partsum) n = num[0] for i in range(1, len(num)): n -= num[i] print(n) 문제해석 그리디 - 단위로 정보를 받아 들인다. + 단위로 정보를 받아들여서 더한다. 총 나눈다. 총정리 정보를 나누어서 ..

11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 n = int(input()) time = list(map(int, input().split())) time.sort() answer = 0 for x in range(1, n+1): answer += sum(time[0:x]) print(answer) 문제해석 그리디 문제 리스트를 받아서 정렬을 해준다 ( 최소 값을 구하기 위해서는 정렬을 해주어서 앞에 있는 사람은 시간이 적은 걸린 사람이 해야한다 왜냐하면 누적이기 때문에 앞에가 크면 계속 그 값이 반복 되기 때문이다) 누적 합을..

1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제풀이 n = int(input()) s = [] op = [] # 답 count = 1 temp = True for i in range(n): num = int(input()) while count

1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제풀이 n = int(input()) s = [] for i in range(n): first, second = map(int, input().split()) s.append([first, second]) s = sorted(s, key=lambda a: a[0]) s = sorted(s, key=lambda a: a[1]) last = 0 cnt = 0 for i, j in s: if i >= last: cnt += 1 last = j print(cnt) 문제해석 핵심 : 그리디 알고리즘 우선 for 반복문을 통해 2차원 리스트를 구성한다. (입력값을 다 받는다) 정렬후 비..

11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 n, k = map(int, input().split()) m = [] num = 0 for i in range(n): m.append(int(input())) for i in range(n - 1, -1, -1): if k == 0: break if m[i] > k: continue num += k // m[i] k %= m[i] print(num) 문제 해석 그리디 알고리즘 돈은 리스트..