알고리즘
-
[백준] 12100 2048(easy) with PythonPS 2021. 10. 25. 23:34
📌 BOJ 12100 2048(easy) 💡 조건 보드의 크기는 N * N (1 ≤ N ≤ 20) 0 은 빈칸, 이외의 값은 블록의 값들을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. 최대 다섯번 이동 시켜서 얻을 수 있는 가장 큰 블록의 값을 출력. 백트래킹 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin, setrecursionlimit from collections import deque setrecursionlimit(int(1e9)) n = ..
-
[백준] 1043 거짓말 with PythonPS 2021. 10. 20. 22:33
📌 BOJ 1043 거짓말 💡 조건 N, M은 50 이하의 자연수 각각 사람의 수, 파티의 수 진실을 아는 사람의 수는 0 이상 50 이하의 정수 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수 지민이는 모든 파티에 참가해야한다. 지민이는 이야기를 과장되게 한다. 또한 지민이는 거짓말쟁이가 되기 싫다. 이야기의 진실을 아는 사람이 파티에 있으면 과장해서 말할 수 없다. 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 문제. 자료구조의 활용을 요구하는 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin.readline().split()) trues = set(list(map(int, stdin.readline().split()))[1:..
-
[백준] 3184 양 with PythonPS 2021. 10. 19. 22:21
📌 BOJ 3184 양 💡 조건 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다. 한 칸에서 수평, 수직만으로 이동할수 있다. 영역 안의 양의 수가 늑대의 수보다 많다면 이기고, 늑대가 많으면 양은 사라진다. 넓이 우선 탐색(BFS) 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin from collections import deque n, m = map(int, stdin.re..
-
[백준] 2343 기타 레슨 with PythonPS 2021. 10. 19. 21:52
📌 BOJ 2343 기타 레슨 💡 조건 강의의 수 N (1 ≤ N ≤ 100,000) 블루레이의 수 M (1 ≤ M ≤ N) 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 각 강의의 길이가 분 단위(자연수)로 주어진다. 가능한 블루레이의 크기 중 최소를 구하는 문제. 이분탐색 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin.readline().split()) arr = list(map(int, stdin.readline().split())) def get_cnt(): count = 0 temp = 0 for i in range(n): if temp + arr[i] > mid: count += 1 temp = 0 temp += ar..
-
[백준] 1743 음식물 피하기 with PythonPS 2021. 10. 18. 20:41
📌 BOJ 1743 음식물 피하기 💡 조건 통로의 세로 길이 N(1 ≤ N ≤ 100) 통로의 가로 길이 M(1 ≤ M ≤ 100) 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M) K개의 줄에 음식물이 떨어진 좌표 (r, c) DFS 유형의 문제(깊이우선탐색) 🖥 소스 코드 from sys import stdin, setrecursionlimit setrecursionlimit(10 ** 9) n, m, k = map(int, stdin.readline().split()) arr = [[0] * (m + 1) for _ in range(n + 1)] food_t = [] for _ in range(k): x, y = map(int, stdin.readline().split()) arr[x][y] = 1 ..
-
[백준] 1713 후보 추천하기 with PythonPS 2021. 10. 18. 20:30
📌 BOJ 1713 후보 추천하기 💡 조건 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 총 추천 횟수는 1,000번 이하이며 학생을 나타내는 번호는 1부터 100까지의 자연수 사진틀의 개수와 전체 학생의 추천 결과가 추천받은 순서대로 주어졌을 때, 최종 후보가 누구인지 결정 구현 & 시뮬레이션 유형의 문제 🖥 소스 코드 from sys import stdin import heapq def solution(n): student = {} data = list(map(int, stdin.readline().split())) for s in data: if s not in student: if len(student) >= n: # dict를 heapq 모듈을 사용해 최솟값을 뽑아냄 a = heapq.n..
-
[백준] 1244 스위치 켜고 끄기 with PythonPS 2021. 10. 17. 21:38
📌 BOJ 1244 스위치 켜고 끄기 💡 조건 및 풀이 첫째 줄은 스위치 개수. 스위치 개수는 100 이하인 양의 정수. 둘째 줄은 각 스위치의 상태. 켜져 있으면 1, 꺼져있으면 0이라고 표시 셋째 줄에는 학생 수. 학생수는 100 이하인 양의 정수 넷째 줄부터 마지막 줄까지 한 줄에 한 학생의 성별, 학생이 받은 수. 남학생은 스위치 번호가 자기가 받은 수의 배수이면, 그 스위치의 상태를 바꾼다. 즉, 스위치가 켜져 있으면 끄고, 꺼져 있으면 켠다. 여학생은 자기가 받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서, 그 구간에 속한 스위치의 상태를 모두 바꾼다. 이때 구간에 속한 스위치 개수는 항상 홀수가 된다. 구현 & 시뮬레이션 유형의 문제..
-
[Programmers] 표 편집 with PythonPS 2021. 10. 17. 21:12
📌 Programmers - [표 편집] 💡 조건 및 풀이 표의 원본 행의 개수를 나타내는 변수 n 5 ≤ n ≤ 1,000,000 처음에 선택되어 있는 행의 위치 k 0 ≤ k < n 수행한 명령어들이 담긴 문자열 배열 cmd 1 ≤ cmd의 원소 개수 ≤ 200,000 cmd의 각 원소는 "U X", "D X", "C", "Z" 중 하나 Linked List 자료구조 문제 표의 모든 행을 제거하여, 행이 하나도 남지 않는 경우는 입력으로 주어지지 않는다. 원래대로 복구할 행이 없을 때(즉, 삭제된 행이 없을 때) "Z"가 명령어로 주어지는 경우는 없다. 정답은 표의 0행부터 n - 1행까지에 해당되는 O, X를 순서대로 이어붙인 문자열 형태로 return 🖥 소스 코드 class Node: def _..
-
[Programmers] 광고 삽입 with PythonPS 2021. 10. 17. 17:10
📌 Programmers - [광고 삽입] 💡 조건 및 풀이 동영상에 광고를 넣어야한다. 시청자가 가장 많은 구간에 광고를 넣어야한다. = 시청자 수 구간합이 가장 큰 곳에 광고를 넣어야한다. 동영상 재생시간 길이 play_time, 공익광고의 재생시간 길이 adv_time, 시청자들이 해당 동영상을 재생했던 구간 정보 logs 구간합을 구해 답을 이끌어내는 유형의 문제 play_time, adv_time은 길이 8로 고정된 문자열 play_time, adv_time은 HH:MM:SS 형식이며, 00:00:01
-
[Programmers] 순위 검색 with PythonPS 2021. 10. 14. 23:30
📌 Programmers - [순위 검색] 💡 조건 및 풀이 조건을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가? 를 구하는 문제 '-' 표시는 해당 조건을 고려하지 않겠다는 의미. "cpp and - and senior and pizza 500" 은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?" 를 의미한다. 브루트포스 알고리즘 유형의 문제에 해당한다. 🖥 소스 코드 from itertools import combinations from bisect import bisect_left def solution(info, query): answer..