본문 바로가기
728x90
반응형

Baekjoon243

[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 부분 수열 중 가장 긴 바이토닉 수열의 길이를 찾는 문제이다. 해당 문제는 이전의 백준 11053번 : 가장 긴 증가하는 부분 수열 문제를 응용하면 쉽게 해결할 수 있는 문제이다. DP 알고리즘을 활용하여 처음부터 끝까지 부분 수열 중 앞의 수보다 크면 1씩 해당 위치의 값을 증가하면서 각 위치별로 증가하는 부분 수열의 길이를 알 수 있다. 이를 거꾸로 생각하면 가장 긴 감소하는 부분 수열을 찾을 수 있다. 두 부분 수열의 길이를 위치별로 .. 2023. 12. 27.
[백준] 1904번 : 01타일 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 길이를 입력받아 가능한 모든 2진 수열의 개수를 구하는 문제이다. 길이가 1일 때는 1가지, 2일 때는 2가지의 경우가 나온다. 해당 경우를 구하다 보면 각 경우의 수는 앞선 결과 2개를 더한 값이라는 것을 알게 된다. 0, 1, 2, 3, 5, 8, 13, 21,... 여기에서 해당 결과를 15746으로 나눈 값을 저장한다. 이를 활용해 원하는 길이까지의 경우를 저장하며 마지막으로 해당 길이의 경우의 수를 출력하면 된다. .. 2023. 12. 26.
[백준] 9184번 : 신나는 함수 실행 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 -50부터 50까지 범위에서 3개의 수를 입력받아 w(a, b, c)의 값을 출력하는 문제이다. 문제에 나와있는 함수를 사용하면 재귀를 활용해 해당 값을 계산하므로 값에 따라 많은 시간이 소요될 수 있다. 하여 이미 구한 값을 저장하고 그 값을 사용하는 DP 알고리즘을 활용해 문제를 해결하고자 했다. 또한 해당 문제는 -50부터 50까지의 범위의 수를 입력받을 수 있는데 3개의 수 중 하나라도 0 이하이면 해당 결과는 1이.. 2023. 12. 24.
[백준] 14889번 : 스타트와 링크 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 14889번: 스타트와 링크예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.www.acmicpc.net 1. 문제 설명2. 풀이과정해당 문제는 모든 인원을 정확하게 두 팀으로 나누고 나눈 두 팀의 능력치를 계산하여 그 차이의 최솟값을 구하는 문제이다.팀을 정확하게 두 팀으로 나누어야 하고, 나눈 두 팀에 대해 각 능력치를 구한 뒤, 두 팀의 능력치의 차이를 계산해야 한다. 계산한 능력치의 차이 중 최솟값을 구하면 된다.하여 제일 앞사람부터 첫 번째 팀으로 이동하며 팀을 나눈다.만약 첫 번째 팀의 인원이 전체 인원의 절반이 되면, 남은 사람들은 모두 두 번째 팀이 된다.두 팀으로 나누어졌으면.. 2023. 12. 23.
[백준] 24416번 : 알고리즘 수업 - 피보나치 수 1 - 우당탕탕 개발자 되기 프로젝트 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 1. 문제 설명 2. 풀이과정 처음에 문제를 아래의 코드처럼 풀었다. 문제에 있는 두 함수를 그대로 사용하면서 각 함수가 호출되는 횟수를 구하는 방식으로 문제를 해결하였으나, 시간 초과가 발생하였다. import sys def fib(n): global cnt1 if (n == 1 or n == 2): cnt1 += 1 return 1 else: return (fib(n - 1) + fib(n - 2)) def fibonacci(n): global .. 2023. 12. 22.
[백준] 14888번 : 연산자 끼워넣기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제는 연산자를 각 수 사이에 넣는 순서에 따라 달라지는 연산의 결과 중 최댓값과 최솟값을 구하는 문제이다. 연산자의 개수에 따라 수많은 조합의 결과가 나오기 때문에 많은 시간이 걸린다. 하지만 우선 모든 조합을 전부 계산해 보며 최댓값과 최솟값을 구해보았다. 처음 비교할 최댓값에는 현재 문제에서 가능한 최솟값인 -10억을, 최솟값에는 현재 문제에서 가능한 최댓값인 10.. 2023. 12. 21.
[백준] 2580번 : 스도쿠 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 1. 문제 설명 2. 풀이과정 sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys 빈칸에 적으려는 수가 해당 행에서 겹치지 않는지 확인하는 함수를 정의한다. def rowCheck(row, v) 해당 행의 각 열의 위치를 불러오며 for c in range(9) 만약 빈칸에 적으려는 수가 이미 해당 행에 동일하게 있으면 if (v == sudoku[row][c]) 빈칸에는 해당 수를 넣을 수 없다. return.. 2023. 12. 20.
[백준] 9663번 : N-Queen - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 문제 설명 2. 풀이과정 sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys 퀸을 배치하는 함수를 정의한다. def nQueen(n) 퀸을 배치할 수 있는 모든 경우의 수를 저장할 변수를 외부에서 정의하고 함수 내부에서도 그대로 사용할 수 있도록 global 변수로 가져온다. global count 만약 현재 놓을 퀸이 마지막 퀸이면 if (n == N) 경우의 수를 증가시킨다. count += 1 한 가지 경우를 찾았으.. 2023. 12. 19.
[백준] 15652번 : N과 M (4) - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 문제 설명 2. 풀이과정 sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys 두 자연수를 입력받는다. N, M = map(int, sys.stdin.readline().split()) 수열을 저장할 리스트를 생성한다. li = list() 수열을 생성할 함수를 정의한다. def dfs(s) 만약 수열의 원소 개수가 원하는 개수를 만족하면 if (len(li) == M) 원소를 하나씩 불러 문자열로 바꾸고 .. 2023. 12. 18.
[백준] 15651번 : N과 M (3) - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 문제 설명 2. 풀이과정 sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys 가능한 모든 경우의 수인 중복 조합을 구하기 위해 product() 함수를 불러온다. from itertools import product 두 자연수를 입력받는다. N, M = map(int, sys.stdin.readline().split()) 1부터 첫 번째 자연수까지 각 수를 문자 원소로 가진 리스트를 생성한다. li = l.. 2023. 12. 17.
728x90
반응형

티스토리툴바