분류 전체보기
-
[백준] 10419 지각 with PythonPS 2023. 4. 3. 16:14
📌 BOJ 10419 지각 💡 조건 교수님의 지각시간 0이상의 정수 t와 수업을 일찍 마쳐주는 시간 s 사이에는 s = t**2 의 관계가 있다. 창영이가 궁금한 경우의 수 T(1 ≤ T ≤ 100)가 첫 번째 줄에 주어지고, 이어서 T 개의 줄에 수업시간 d(1 ≤ d ≤ 10,000, d는 정수)가 차례대로 주어진다. 수업시간에 따른 교수님이 지각할 수 있는 최대 시간 t를 정수로 구해서 출력한다. 지각할 수 있는 최대의 시간을 알아보는 문제 브루트포스 유형의 문제 🔖 예제 및 실행결과 예제 1 5 1 2 5 6 7 실행결과 1 0 1 1 2 2 ⌨️ 문제 풀이 지각할 수 있는 최대시간을 구하려면, 수업시간 d의 최대값이 얼마인지 확인해봐야한다. 지각할 수 있는 최대시간은 100부터 -1씩 줄여나가 ..
-
[백준] 5692 팩토리얼 진법 with PythonPS 2023. 4. 3. 16:04
📌 BOJ 5692 팩토리얼 진법 💡 조건 팩토리얼 진법에서는 i번 자리의 값을 ai×i!로 계산한다. 즉, 팩토리얼 진법에서 719는 10진법에서 53과 같다. 그 이유는 7×3! + 1×2! + 9×1! = 53이기 때문이다. 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 최대 5자리인 팩토리얼 진법 숫자가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. 각 테스트 케이스에 대해서, 입력으로 주어진 팩토리얼 진법 숫자를 10진법으로 읽은 값을 출력한다. 수학 유형의 문제 🔖 예제 및 실행결과 예제 1 719 1 15 110 102 0 실행결과 1 53 1 7 8 8 ⌨️ 문제 풀이 입력 받은 숫자를 문자열로 변경한 뒤, 길이(l)를 구한다...
-
[백준] 1676 팩토리얼 0의 개수 with PythonPS 2023. 4. 1. 22:49
📌 BOJ 1676 팩토리얼 0의 개수 💡 조건 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하는 문제. 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 수학 유형의 문제 🔖 예제 및 실행결과 예제 1 10 실행결과 1 2 예제 2 3 실행결과 2 0 ⌨️ 문제 풀이 리스트에 팩토리얼 계산 값을 미리 넣어놓으면 쉽게 해결할 수 있다. N에 해당하는 값을 꺼내 맨 우측부터 좌측 방향으로 이동하며 0이 아닌 수가 나올 때까지 0의 개수가 몇 개인지 세면 된다. 🖥 소스 코드 from sys import stdin arr = [1, 2, 6, 24, 120] n = int(stdin.readline()) if n < 5: print(0) else: for i i..
-
[백준] 14469 소가 길을 건너간 이유 3 with PythonPS 2023. 4. 1. 22:41
📌 BOJ 14469 소가 길을 건너간 이유 3 💡 조건 N마리의 소가 이 농장에 방문하러 왔다. 소가 도착한 시간과 검문받는 데 걸리는 시간은 소마다 다르다. (물론 같을 수도 있다.) 두 소가 동시에 검문을 받을 수는 없다. 예를 들어, 한 소가 5초에 도착했고 7초 동안 검문을 받으면, 8초에 도착한 그 다음 소는 12초까지 줄을 서야 검문을 받을 수 있다. 모든 소가 농장에 입장하려면 얼마나 걸리는지 구하는 문제. 첫 줄에 100 이하의 양의 정수 N이 주어진다. 다음 N줄에는 한 줄에 하나씩 소의 도착 시각과 검문 시간이 주어진다. 각각 1,000,000 이하의 양의 정수이다. 정렬, 그리디 유형의 문제 🔖 예제 및 실행결과 예제 1 3 2 1 8 3 5 7 실행결과 1 15 ⌨️ 문제 풀이 기..
-
[백준] 1992 쿼드트리 with PythonPS 2023. 3. 31. 17:57
📌 BOJ 1992 쿼드트리 💡 조건 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못한다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 된다. 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하는 문제. 분할정복, 재귀 유형의 문제. 🔖 예제 및 실행결과 예제 1 8 11110000 11110000 00011100 00011100 11110000 111..
-
최소 비용 신장트리자료구조 2022. 8. 9. 18:41
📌최소 비용 신장트리 💡최소 비용 신장트리 정의 가중치가 부여된 무방향 그래프에서 신장 트리의 비용 가중치 : 두 vertex 사이의 거리 혹은 연결하는 비용 = 신장트리를 구성하는 에지들의 비용의 합 최소 비용 신장트리 : 가장 비용이 적은 신장 트리 응용 분야 도로 건설 : 도시를 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제 ex) 통신, 배관 최소 비용 신장트리 알고리즘 최소 비용 신장트리 알고리즘 1) 그래프 내에 존재하는 Edge들만 사용한다. 2) 정점의 개수가 n일 때, n - 1개의 Edge들만 사용한다. 3) 사이클을 형성하는 edge는 사용불가하다. 최소 비용 신장트리를 구하기 위한 알고리즘들 1) 크루스칼 2) 프림 3) 솔린 💡크루스칼 알고리즘(Kruskal Algorit..
-
기초적인 그래프 연산들자료구조 2022. 8. 9. 18:18
📌 기초적인 그래프 연산들 💡깊이 우선 탐색(Depth First Search) DFS 알고리즘 출발 정점, v의 인접리스트부터 방문한다. v에 인접하면서 아직 방문하지 않은 정점 w를 선택한다. w를 시작점으로 하여 다시 DFS를 시작한다. 순환 알고리즘을 이용하여 구현한다.(재귀) 💡너비 우선 탐색(Breath First Search) BFS 알고리즘 출발 정점, v의 인접 리스트부터 방문한다. v에 인접한 모든 vertex부터 방문한다. 그 다음, v에 인접한 첫번째 vertex에 인접한 vertex 중에서 아직 방문하지 않은 vertex 들을 차례대로 다시 방문한다. -> Queue 자료구조를 사용하여 구현 💡연결요소(Connected Component) 무방향성 그래프가 연결되어 있는지 검사한다..
-
[백준] 1890 점프 with PythonPS 2022. 8. 9. 17:33
📌 BOJ 1890 점프 💡 조건 N×N 게임판에 수가 적혀져 있다. N (4 ≤ N ≤ 100) 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 오른쪽 아래 칸에는 항상 0이 주어진다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로..
-
[백준] 1722 순열의 순서 with PythonPS 2022. 8. 9. 17:18
📌 BOJ 1722 순열의 순서 💡 조건 1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다. 임의의 순열은 정렬을 할 수 있다. 예를 들어 N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 문제 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나..