Algorithm/백준
-
[Python] 11053 가장 긴 증가하는 부분 수열Algorithm/백준 2023. 1. 20. 17:20
1. 문제 📚 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 2. 입출력 예 📋 3. 알고리즘 ✅ N이 1000이기 때문에 완탐으로 하면 시간초과가 날 것이다 앞부분 수열에 따라 뒷부분 수열까지 영향을 주기 때문에 DP로 풀어야 한다! dp 를 1로 초기화해준 다음, 현재 index로 이전의 숫자와 차근차근 비교해서 증가하는 수라면 그 이전에 저장된 dp 값 + 1..
-
[Python] 15657 N과 M (8)Algorithm/백준 2023. 1. 20. 16:21
1. 문제 📚 https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 2. 입출력 예 📋 3. 알고리즘 ✅ 문제 조건 중 비내림차순이 있었기때문에 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 1. 정렬을 해주었고 2. dfs 파라미터로 그 이전 값을 받아, 그 이전 값보다 큰 값들만 append 시켜주었다 4. 소스코드 💻 import sys in..
-
[Python] 1987 알파벳(dfs)Algorithm/백준 2023. 1. 19. 21:00
1. 문제 📚 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 2. 입출력 예 📋 3. 알고리즘 ✅ 그래프 문제 + 백트래킹 문제이다 조건이 이미 한번 지나온 알파벳은 방문할 수 없음이므로 앞으로 나아갈 곳이 이미 지나온 알파벳이라면 뒤로 가서 다시 탐색을 해주어여한다 bfs로 count를 세어준다음, 가장 최대값을 리턴해주었다! 여기서 포인트는 재귀호출이 끝나면 다시 False로 바꿔주어 탐색을 해주어야한다 4. 소스코드 💻 impor..
-
[Python] 1759 암호 만들기Algorithm/백준 2023. 1. 18. 21:23
1. 문제 📚 https://www.acmicpc.net/problem/1759 2. 입출력 예 📋 3. 알고리즘 ✅ 백트래킹 문제이므로 조건을 제대로 봐야한댜 조건1. 중복된 문자가 없을 것 조건2. 알파벳이 암호에서 증가하는 순서대로 배열 됐을 것 조건3. 최소 한개의 모음 최소 2개의 자음 4. 소스코드 💻 처음에 실패해서 뭐지 했는데 조건3을 안따졌었다 아래는 백준 질문게시판에 있던 반례이다 input: 3 6 a e i c d z output: acd acz adz cde cdi cez ciz dez diz import sys input = sys.stdin.readline L, C = map(int, input().strip().split()) alphabet = sorted(input()...
-
[Python] 3190 뱀Algorithm/백준 2023. 1. 18. 21:15
1. 문제 📚 https://www.acmicpc.net/problem/3190 2. 입출력 예 📋 3. 알고리즘 ✅ 처음에 문제를 이해하는 데만 오래걸렸다;; 초기 시작을 (0, 0)으로 두고 1초라고 둬야한다 보기 쉽게 $을 뱀 @ 을 사과라고 뒀다 예제1을 출력해보면 time: 1 direction: Right $ . . . . . . . . . @ . . . . @ . . . . . . . . . . @ . . . . . . . . . time: 2 direction: Right . $ . . . . . . . . @ . . . . @ . . . . . . . . . . @ . . . . . . . . . time: 3 direction: Right . . $ . . . . . . . @ . . ..
-
[Python] 1744 수묶기Algorithm/백준 2022. 12. 28. 21:22
1. 문제 📚 https://www.acmicpc.net/problem/1744 2. 입출력 예 📋 3. 알고리즘 ✅ - 최대가 나오기 위해선 음수에서 경우의 수 1) 음수 * 음수 경우의 수 2) 음수 + 음수 경우의 수 3) 음수 * 0 경우의 수 4) 음수 4가지 중에 최대 값을 양수는 경우의 수 1) 양수 * 양수 경우의 수 2) 양수 + 양수 경우의 수 3) 양수 3가지 중에 최대 값을 더해야한다 따라서 인풋을 따로 따로 받아주어 모든 경우의 수를 따져준당 4. 소스코드 💻 import sys input = sys.stdin.readline N = int(input().strip()) negative_arr = [] zero_arr = [] positive_arr = [] for i in ran..
-
[Python] 1541 잃어버린 괄호Algorithm/백준 2022. 12. 27. 02:14
1. 문제 📚 https://www.acmicpc.net/problem/1541 2. 입출력 예 📋 3. 알고리즘 ✅ 그리디 -> 최소로 만들려면 - 앞에서 괄호로 묶어서 -를 최대한 많이 만들어줘야함 4. 소스코드 💻 import sys input = sys.stdin.readline().strip() input_arr = [] num = '' index = 0 temp = input # 숫자와 기호를 분리해주는 작업 while len(input) != 0: if input[0] == '-' or input[0] == '+': input_arr.append(int(num)) num = '' input_arr.append(input[0]) else: num += input[0] index += 1 inp..
-
[Python] 2309 일곱 난쟁이Algorithm/백준 2021. 10. 15. 02:43
1. 문제 📚 2. 입출력 예 📋 3. 알고리즘 ✅ 2명만 제외하면 100이 되니, 이중 for문을 이용하여 모든 경우의 수 중, 일곱명의 키 합 - (두개를 더한 값) = 100이면 그 두개만 -1로 변경해주어 출력해주었다. 4. 소스코드 💻 import sys height_list = [] for i in range(9): height_list.append(int(sys.stdin.readline())) height_sum = sum(height_list) is_exist = False for i in range(len(height_list) - 1): for j in range(i + 1, len(height_list)): if height_sum - (height_list[i] + height_l..