본문 바로가기

Algorithm💻/Baekjoon24

[백준,Python] 1260번 - DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 깊이 우선 탐색(dfs)와 너비 우선 탐색(bfs)으로 실행 시킨 값을 출력하는 문제이다. 두가지의 차이점을 확실히 아는 것이 중요할 것 같다. 코드 import sys input = sys.stdin.readline n,m,v = map(int,input().split()) visited = [False]*(n+1) graph = [[] for _ in.. 2022. 11. 15.

[백준,Python] 9465번 - 스티커 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 해당 문제는 도저히 점화식이 떠오르지 않아 구글링을 했다. 위의 표를 예시로 들어보자. 좌측에서부터 해당 스티커의 위치에 최대값이 될 수 있는 경우를 생각하면 된다. 우선 해당 위치에서 좌,우,위,아래 숫자는 선택할 수 없다. 1번 인덱스에서는 왼쪽 대각선의 0번 인덱스의 숫자를 더할 수 있다. 2번 인덱스부터는 이 전까지 최댓값을 더한 숫자를 저장하고 있는 왼쪽 대각선의 숫자와 .. 2022. 11. 13.

[백준,Python] 9095번 - 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 d[4]를 구한다고 하자. 3을 만들 수 있는 경우의 수에서 +1을 한 것, 2를 만들 수 있는 경우의 수에서 +2를 한 것, 1을 만들 수 있는 경우의 수에서 +3을 한 것을 합치면된다. 즉, d[4] = d[3] + d[2] + d[1] 이라고 볼 수 있다. d[n] = d[n-3] + d[n-2] + d[n-1] 이라는 식이 나온다. 해당 그림은 정리를 깔끔하게 하셔서 참고를 했다. [Python] 백준 #9095 - 1, 2, 3 더하기 (tistory.com) 코드 d=[0]*11.. 2022. 11. 12.

[백준,Python] 17626번 - 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 연산을 사용하는 횟수의 최솟값을 구하기 위해서 큰 수로 처음부터 나누는 것이 제일 빨리 1로 도달할 것이라 생각하지만 힌트에서와 같이 10의 경우에는 10 - 5 - 4 - 2 - 1로 푸는 방법보다 처음부터 1을 빼고 10 - 9 - 3 - 1을 만드는 방법이 최솟값인 것을 알 수 있다. 즉, 그리디 방법을 사용하는 것이 아니라 동적 계획법을 이용해야 한다. 동적 계획법으로는 1을 빼는 경우, 2로 나누는 경우, 3으로 나누는 경우에 대한 모든 경우를 확인할 수 있다. 연산의 홧수를 저장해두는 d 리스트.. 2022. 11. 11.

[백준,Python] 7662번 - 이중 우선순위 큐 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이 처음 문제를 보자마자 queue로 구현은 다 했는데 시간초과가 계속 떴다... 그러다가 문득 최소값, 최대값을 찾는 문제의 경우 힙을 이용하는 것이 좋다고 생각이 들어서 다시 구현을 해보았다. heapq는 기본적으로 최소힙 기능만을 제공하기에 최대힙은 따로 구현을 해주어야 한다. - 삽입 - 먼저 최소힙과 최대힙 형태를 선언하고 문자가 I일 때는 각 힙에 값을 삽입해주면 된다. 이때, 최.. 2022. 10. 31.

이전 1 2 3 4 5 다음

티스토리툴바