알고리즘
-
[백준] 1342 행운의 문자열 with PythonPS 2022. 3. 1. 03:58
📌 BOJ 1342 행운의 문자열 💡 조건 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다. S의 길이는 최대 10이고, 알파벳 소문자로만 이루어져 있다. 첫째 줄에 위치를 재배치해서 얻은 서로 다른 행운의 문자열의 개수를 출력한다. 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin arr = stdin.readline().rstrip() cnt = 0 point = [0 for _ in range(26)] for i in arr: point[ord(i) - 97] += 1..
-
[백준] 18243 Small World Network with PythonPS 2022. 3. 1. 02:19
📌 BOJ 18243 Small World Network 💡 조건 첫 번째 줄에 지구에 있는 사람의 수 N과 친구 관계의 개수 K. (1 ≤ N ≤ 100, 0 ≤ K ≤ N×(N-1)/2) 모든 사람은 1부터 N까지 번호가 매겨져 있다. 두 번째 줄부터 K+1번째 줄까지 친구 관계를 나타내는 A B가 한 줄에 하나씩 주어진다. (1 ≤ A, B ≤ N) A와 B가 친구면 B와 A도 친구다. 자기 자신과 친구인 경우는 없다. A와 B의 친구 관계는 중복되어 입력되지 않는다. 해당 네트워크가 작은 세상 네트워크를 만족하면 "Small World!"를, 만족하지 않는다면 "Big World!"를 출력 BFS, 그래프 이론 유형의 문제 🖥 소스 코드 from sys import stdin from collec..
-
[백준] 15722 빙글빙글 스네일 with PythonPS 2022. 2. 27. 22:03
📌 BOJ 15722 빙글빙글 스네일 💡 조건 달팽이는 원점에서 시작하여 1초에 한 칸 씩, 시계방향으로 아래 그림과 같이 움직인다. 1초일 때 달팽이의 위치는 (0, 1)이다. 몇 초가 지났는지가 입력으로 주어질 때, 현재 달팽이의 위치를 좌표로 출력하는 문제 달팽이가 움직인 시간이 n초로 주어진다. (0 ≤ n ≤ 1000, n은 0이상의 정수) 구현, 시뮬레이션 유형의 문제 🖥 소스 코드 from sys import stdin def solve(): n = int(stdin.readline()) pos = [0, 0] mode, length = 0, 1 cnt = 0 while 1: for i in range(2): for _ in range(2): # Add if i == 0: if mode ==..
-
[백준] 14425 문자열 집합 with PythonPS 2022. 2. 27. 21:25
📌 BOJ 14425 문자열 집합 💡 조건 N개의 문자열로 이루어진 집합 S 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 문제 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000) 어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. 문자열, 자료구조 유형의 문제 🖥 소스 코드 from sys import stdin n, m = map(int, stdin.readline().split()) strings = {} for _ in range(n): strings[stdin.readline().rstrip()] = 0 for i in range(m): s = st..
-
[백준] 14916 거스름돈 with PythonPS 2022. 1. 26. 22:44
📌 BOJ 14916 거스름돈 💡 조건 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈 액수 n(1 ≤ n ≤ 100,000) DP, 수학 유형의 문제 🖥 소스 코드 from sys import stdin n = int(stdin.readline()) res = int(1e9) for i in range(n // 5, -1, -1): money = n - i * 5 cnt = i if money % 2 != 0: continue else: cnt += money // 2 res = min(cnt, res) print(res) if res != int(1e9) else print(-1)🔖 예제 및 실행결과 예제 13실행결과 5⌨️ 문제 풀이 5원 동전이 몇 개 일때 최소인지 구하면 된다. int..
-
[백준] 14888 연산자 끼워넣기 with PythonPS 2022. 1. 24. 20:44
📌 BOJ 14888 연산자 끼워넣기 💡 조건 N개의 수로 이루어진 수열 A1, A2, ..., AN 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 수의 개수 N(2 ≤ N ≤ 11) A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력 순열, 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin from itertools import permutations n = int(stdin.readline().rstrip()) num = list(map(int, stdin.readline().split())..
-
[백준] 14502 연구소 with PythonPS 2022. 1. 24. 20:28
📌 BOJ 14502 연구소 💡 조건 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8) 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다. DFS + BFS, 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin from collections import deque n, m = map(int, stdin.readline()...
-
[백준] 11504 돌려 돌려 돌림판! with PythonPS 2022. 1. 11. 18:06
📌 BOJ 11504 돌려 돌려 돌림판! 💡 조건 첫 번째 줄에 테스트케이스의 개수 T 테스트케이스의 첫 줄에는 돌림판을 N등분할 정수 N (1 ≤ N ≤ 100) X, Y의 길이 M (1 ≤ M ≤ 9, M ≤ N) 다음 3개의 줄에 X의 각 자리수, Y의 각 자리수, 돌림판의 상태 돌림판에서 X ≤ Z ≤ Y를 만족하는 M자리의 수 Z가 몇 개가 있는 지를 출력 X와 Y사이에 있는 수가 123 밖에 없는 데 돌림판에서 2번 나온다면, 1이 아닌 2를 출력 구현, 시뮬레이션 유형의 문제 🖥 소스 코드 from sys import stdin for _ in range(int(stdin.readline())): n, m = map(int, stdin.readline().split()) x = int(..
-
[백준] 10819 차이를 최대로 with PythonPS 2022. 1. 11. 17:53
📌 BOJ 10819 차이를 최대로 💡 조건 N개의 정수로 이루어진 배열 A N (3 ≤ N ≤ 8) 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. 다음 식의 최댓값을 구하는 프로그램을 작성. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 5. **브루트포스 알고리즘 유형**의 문제 ## 🖥 소스 코드 from sys import stdin from itertools import permutations n = int(stdin.readline()) arr = list(map(int, stdin.readline().split())) res = -int(1e9) for arr2 in permutations(arr, n): v ..
-
[백준] 9461 파도반 수열 with PythonPS 2022. 1. 10. 18:54
📌 BOJ 9461 파도반 수열 💡 조건 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100) 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 각 테스트 케이스마다 정수 N을 입력받아 P(N)을 출력. Dynamic Programming 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin dp = [0 for _ in range(101)] dp[0], dp[1], dp[2] = 1, 1, 1 for i in range(3, 101): dp[i] = dp[i - 3] + dp[i - 2] for _..