본문 바로가기

728x90

실버26

[백준/Python] 1874 스택 수열 문제: https://www.acmicpc.net/problem/1874 사용 알고리즘: 스택 입력첫 줄에 n (1 둘째 줄부터 n 개의 줄에는 수열을 이루는 1 이상 n 이하의 정수가 하나씩 순서대로 출력됨. (같은 정수 2번 나옴x) 1 부터 n 까지의 숫자를 스택에 넣고 빼면서 입력으로 주어진 수열을 만드는 문제단, 스택에 숫자를 넣을 때는 무조건 오름차순으로 넣어야 함 -> 1 부터 n 까지 차례로 넣어야 함 1. 스택에 숫자를 넣고 빼면서 주어진 수열을 만들 수 있는 경우스택에 숫자를 넣을 때는 '+' 출력스택에서 숫자를 뺄 때는 '-' 출력2. 스택에 숫자를 넣고 빼면서 주어진 수열을 만들 수 없는 경우에는 'NO' 출력 수열 만들기 파이썬은 스택 자료구조를 제공하지 않음! -> 만들.. 2024. 7. 26.

[백준/Python] 1260 DFS 와 BFS 문제: https://www.acmicpc.net/problem/1260 사용 알고리즘: DFS, BFS 문제 제목대로 DFS, BFS 를 구현하면 되는 문제 그래프 표현 방법에는 2가지가 있기 때문에 2가지 방법으로 풀어보았다. 인접행렬(adjacency matrix): 인접성을 행렬(2차원배열/리스트)로 표현인접리스트(adjacency list): 정점에 인접한 에지만을 연결리스트로 표현 1. 인접행렬(adjacency matrix) - 입력N, M, V = map(int, input().split())graph = [[0] * (N+1) for _ in range(N+1)]for _ in range(M): a, b = map(int, input().split()) graph[a][.. 2024. 7. 18.

[백준/Python] 9184 신나는 함수 실행 문제: https://www.acmicpc.net/problem/9184 사용 알고리즘: 재귀, DP 사실 문제를 처음 읽고 어엉? 했지만 다시 보니 주어진 코드를 거의 그대로 사용해서 풀 수 있는 문제였다. 문제에서 주어진 코드는 재귀만을 사용해서 w(a, b, c) 를 구하기 때문에 시간이 너무 오래걸린다. 시간을 단축하기 위해 DP 를 사용해서 전에 계산했던 값을 가져다 쓰면서 시간을 줄였다. - dp 배열 초기화 문제에 주어진 코드를 읽어보면 a, b, c 중 한개라도 20 을 초과하는 값이 있다면 w(20, 20, 20) 로 통일해 버린다. 그래서 n 값은 최대 50 까지 가능하지만, dp 배열은 51 까지 만들 필요없이 21 까지만 만들면 된다. dp = [[[0 for _ in ran.. 2024. 7. 14.

[백준/Python] 11055 가장 큰 증가하는 부분 수열 문제: https://www.acmicpc.net/problem/11055 사용 알고리즘: DP 수열 A 가 주어졌을 때, 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램 구현ex) A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} -> 1, 2, 50, 60 합 113 입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)둘째 줄에는 수열 A를 이루고 있는 Ai(1 ≤ Ai ≤ 1,000) dp[i] -> 수열 A 의 0 번째 인덱스부터 i 번째 인덱스까지의 부분 합 중 가장 큰 부분 합 i 는 현재 위치, j 는 처음~현재 위치까지 수들을 비교하기 위한 인덱스 현재 위치를 고정시켜놓고 현재 위치까지 수열을 돌면서 현재 위치 값과 방문한 수열의 .. 2024. 7. 3.

이전 1 2 다음

728x90

티스토리툴바