알고리즘/BOJ32 [BOJ] 2630. 색종이 만들기 문제https://www.acmicpc.net/problem/2630잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하기 주요 아이디어영역 전체가 같은 색이 아니라면 절반으로 계속 잘라주기 -> 재귀로 구현파란색 / 하얀색 종이 판단해서 cnt 올리기 코드 구현 (Python 3)더보기 import sysfrom collections import Countersys.setrecursionlimit(10**5)result = []# 색종이의 color 판단def check_color(paper): total = sum(sum(paper, [])) if total == len(paper) * len(paper[0]): return 'B' elif total == 0: .. 2024. 6. 25. [BOJ] 15686. 치킨 배달 문제https://www.acmicpc.net/problem/15686 주요 아이디어치킨 거리 = 맨해튼 거리 = L1 norm선택될 수 있는 치킨 집은 최대 13개이므로, 브루트포스 (=완전 탐색) 방식을 통해 치킨 집을 선택하는 모든 경우의 수를 구한 다음 각각의 최소 거리를 구하면 된다 코드 구현 (Python 3)더보기 """크기 N*N브루트포스1. 치킨 거리 구하는 함수2. 치킨 집 위치 좌표 넣기3. 해당 치킨 집 위치를 제외하고 모두 없앤 가상맵 생성 함수3. 가상 하나씩 돌면서 모든 경우의 수에 대해 치킨 거리를 계산"""from itertools import combinationsimport sysdef chicken_dist(r1, c1, r2, c2): return abs(r.. 2024. 6. 25. [BOJ] 15683. 감시 문제https://www.acmicpc.net/problem/15683 주요 아이디어생각보다 구현이 까다로운 문제였다.위 다섯 종류의 90도 회전이 가능한 감시 카메라가 맵에 배치되어 있으며, 맵 전체에서 사각지대 영역의 최소 넓이를 측정하는 문제이다.또한 CCTV는 서로를 통과할 수 없다는 조건이 걸려있다.CCTV는 8개 이하이므로 완전탐색 (=브루트 포스) 으로 문제를 해결한다CCTV의 회전 방향을 따로 rotation 배열에 저장해둔다맵에 있는 모든 CCTV를 회전시켜보고, 그 때마다 면적을 체크해서 최소 면적으로 갱신한다 코드 구현 (Python 3)더보기 """사각지대를 최소화하기브루트포스니까 모든 경우의 수 전부 비교1. 감시 당하는 부분 #으로 표시2. CCTV 좌표 저장해두고, 하나씩 회.. 2024. 5. 21. [BOJ] 13414. 수강신청 문제https://www.acmicpc.net/problem/13414 주요 아이디어대기 목록을 전달받고, 중복이 되어있을 경우 대기목록의 맨 뒤로 가야 한다.입력을 받는 순서대로 dictionary에 추가한다이미 있을 경우 (뒤로 밀려나기 때문에) dict의 value가 갱신된다 코드 구현 (Python 3)더보기 import sysdef solution(k, l): students = [sys.stdin.readline().strip() for i in range(l)] student_dict = {} # dictionary 추가 ('학번' : '순서') for i, student in enumerate(students): student_dict[student] = i.. 2024. 5. 21. [BOJ] 1806. 부분합 문제https://www.acmicpc.net/problem/1806 주요 아이디어처음에는 혹시 될까 해서 그냥 풀어보았다.말 그대로 하나씩 잘라보면서 최소값을 갱신하는 방식... 코드 구현 (Python 3)더보기 # 길이 N, 합 Sn, s = map(int, input().split())# 수열numbers = list(map(int, input().split()))total = 0min_len = 10**8 + 1 # s 최대값# 벌써 O(n^2) 나오죠for i in range(len(numbers)): for j in range(i, len(numbers)): arr = numbers[i:j] if sum(arr) >= s: if min_.. 2024. 5. 21. [BOJ] 9466. 텀 프로젝트 문제https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을www.acmicpc.net 주요 아이디어처음에는 BFS 방식으로 접근하고자 했다.1. BFS를 수행해 그래프가 완성되는지 판단2. 그래프가 완성될 경우 그래프에 속한 노드를 반환 / 아닐 경우 None을 반환3. 시작 노드 순차적으로 순회하며 BFS를 수행하고, 그래프가 만들어진 노드들의 개수를 제하면 그래프가 완성되지 않은 노드들의 개수만 남게 됨 코드 구현 (Python 3)더보기.. 2024. 4. 24. 이전 1 2 3 4 5 6 다음
