본문 바로가기

백준55

20230614 [Java] 문제풀이 20230614 [Java] 문제풀이 [백준] 10818 최소, 최대 배열을 이용하여, 주어진 숫자들의 최소와 최대값을 찾으면 된다 파이썬을 이용할 때에 N개의 입력값을 공백으로 주어진 것을 한번에 리스트로 받아서, for문을 돌며 최소와 최대값을 찾았다 자바 같은 경우 scanner.next(); 를 사용하여 하나의 for문에서, 입력값을 받으면서 최소와 최대값을 찾아냈다 만약에 배열을 출력하고 싶을 때에는 Arrays 를 import 받고, Arrays.toString(배열이름) 으로 출력하면 된다 import java.util.Arrays; import java.util.Scanner; public class Baekjoon10818 { public static void main(String[] a.. 2023. 6. 14.
[Java] 백준 25556 포스택 [Java] 백준 25556 포스택 풀이 랜덤으로 되어있는 순열을, 4개의 스택을 이용해서 오름차순으로 정렬을 하는 것이다 여기서 중요한 것은 각 모든 스택은 오름차순으로 나열이 되어 있어야 한다 이유는, 제일 큰 수를 오른쪽부터 왼쪽으로 숫자가 1씩 떨어지면서 정렬을 해야 하는 상황이다 그래서 만약에 스택에 모든 숫자를 넣을 수 있다면, 오름차순으로 정렬이 가능하다 반대로 스택에 숫자 하나라도 못 넣으면, 정렬이 불가능해진다 코드를 보게 되면, 스텍에 값들을 넣었지, 빼는 것은 생략했다 import java.util.Stack; import java.util.Scanner; import java.util.ArrayList; public class Main{ public static void main(S.. 2023. 6. 13.
[Python] 백준 14888 연산자 끼워넣기 🧑‍💻 [Python] 백준 14888 연산자 끼워넣기 Silver 1 - DFS DFS로 풀이를 했다 코드 min_num = 1e9 max_num = -1e9 N = int(input()) numbers = list(map(int, input().split())) operators = list(map(int, input().split())) def dfs(num_depth, total, plus, minus, multiply, divide): global min_num, max_num if num_depth == N: min_num, max_num = min(total, min_num), max(total, max_num) return if plus > 0: dfs(num_depth + 1, total.. 2023. 4. 7.
[Python] 백준 9663 N-Queen 🧑‍💻 [Python] 백준 9663 N-Queen Gold 4 - Backtracking Queen은 위, 아래, 오른쪽, 왼쪽, 대각선, 8 방면 모두 공격을 할 수 있다 N이 주어지고, 체스판 사이즈는 N x N 이고, N 개의 Queen을 넣었을 때 서로 공격할 수 없는 때의 경우의 수를 찾는 것 1차적으로 자세히 보면, 각 행과 열마다, Queen은 하나씩 배치할 수 있다 이 뜻은 굳이 체스판 자체를 안 만들어도 된다 board = [0, 3, 1, 4, 2] 아래 사진을 표현한 리스트 (board의 인덱스가 열/row, board의 값이 행/column) board 안에 있는 값들은 모두 달라야 한다 row (board의 인덱스) column (board의 값) 0 0 1 3 2 1 3 4 4.. 2023. 4. 5.
[Python] 백준 15650 N과 M 2 🧑‍💻 [Python] 백준 15650 N과 M 2 Silver 3 - Backtracking 쉽게 itertools의 combinations를 사용해서 풀 수 있는 문제다 하지만 Backtracking을 공부하고 싶어서 풀었던 문제다 기본적으로 if len(nums) == M: 을 통해서 재귀 함수의 base case를 만든다 안 만들면 무한 루프 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 backtracking(start)를 다시 돈다 여기서 중요한 것은, 수열이 오름차순이어야 한다는 것이다 그래서 재귀함수를 돌릴때마다 backtracking(start + 1)를 해야 한다 그렇게 하면, for문에서 전에서 backtracking() 했던 것보다, 큰 수부터.. 2023. 4. 2.
[Python] 백준 15649 N과 M 🧑‍💻 [Python] 백준 15649 N과 M Silver 3 - Backtracking 쉽게 itertools의 permutations를 사용해서 풀 수 있는 문제다 하지만 Backtracking을 공부하고 싶어서 풀었던 문제다 기본적으로 if len(l) == M: 을 통해서 재귀 함수의 base case를 만든다 안 만들면 무한 루프 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 dfs()를 다시 돈다 그리고 l.pop()을 해야, 리스트에 숫자가 사라지고, 다른 경우의 수를 넣을 수 있다 코드 백트래킹 사용 N, M = map(int, input().split()) l = [] def dfs(): if len(l) == M: print(" ".join(ma.. 2023. 4. 2.
[Python] 백준 1213 팰린드롬 만들기 🧑‍💻 [Python] 백준 1213 팰린드롬 만들기 Silver 3 - Dictionary 딕셔너리에, 각 알파벳과 알파벳의 개수를 넣는다 key는 알파벳 | value에는 알파벳의 개수 알파벳 개수 중 홀수가 2개 이상이면, 팰린드롬을 만들 수 없다 if sum([al % 2 for al in al_dict.values()]) > 1: 홀수 이면 al % 2 를 할 때 1이 나온다 반대로 짝수면 0이다 즉 팰린드롬이 되려면, 모든 알파벳의 개수가 짝수거나, 개수 하나가 홀 수 일 때에 팰린드롬을 만들 수 있다 for key, value in sorted(al_dict.items()): 을 통해서, 알파벳을 정렬한다 코드 flag = True al_dict = {} alp = input() for a .. 2023. 4. 1.
[Python] 백준 1915 가장 큰 정사각형 🧑‍💻 [Python] 백준 1915 가장 큰 정사각형 Gold 2 - Backtracking 행렬을 순회하면서, 1을 찾게되면, 그 1에 대한 모든 경우의 수를 가지고 최소값을 구하는 것이다 예) 찾은 1을 기준으로 1X1 색종이를 덮을 경우 예) 찾은 1을 기준으로 2X2 색종이를 덮을 경우 예) 찾은 1을 기준으로 3X3 색종이를 덮을 경우 예) 찾은 1을 기준으로 4X4 색종이를 덮을 경우 예) 찾은 1을 기준으로 5X5 색종이를 덮을 경우 56번째 줄이 끝나면, 대부분의 1은 0으로 바껴져 있을 것이다 (만약 한 사이즈의 색종이를 5장을 넘기면, 1로 유지가 될 것이다) 코드 matrix = [list(map(int, input().split())) for _ in range(10)] count.. 2023. 3. 31.
[Python] 백준 1915 가장 큰 정사각형 🧑‍💻 [Python] 백준 1915 가장 큰 정사각형 Gold 4 - DP 인덱스가 벗어나지 않는 선에서, 위, 왼쪽, 외쪽 위의 숫자들 중 min 값을 구한 다음에 1을 더해준다 코드 N, M = map(int, input().split()) matrix = [list(map(int, input())) for _ in range(N)] dp_table = [[0] * M for _ in range(N)] for i in range(N): for j in range(M): if matrix[i][j] == 1: dp_table[i][j] = 1 if 0 2023. 3. 30.

티스토리툴바