개발/알고리즘 검색 결과
67 개의 검색 결과가 있습니다.
개발/알고리즘

[백준 9251] LCS (python)

9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net DP로 해결 [A길이+1][B길이 +1] 배열을 생성한다. for문을 돌며 하나씩 비교해서 저장한다. 마지막값을 출력한다. ※ 비교방법) 만약 ABCD와 DEFC를 비교한다면 A B C , D E F C - 비교할 때 같은 문자라면, A B 와 D E F 비교값에 1을 더해준다. A B C , D E F - 비교할 때 다른 문자라면, A B C 와 D E 비교값과, A B 와 D E F 비교값 중 큰 값을 저장한다. ..

2021. 4. 7. 18:24
개발/알고리즘

[백준 1753] 최단경로 (python)

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 우선순위큐에 다익스트라 알고리즘을 사용한다 v_arr: 최단경로 저장 arr: 간선 저장 heap: 계산할 것들 저장 heap(우선순위 큐)에 [0, 시작점]을 넣는다. 시작점에 연결되있는 것들을 v_arr와 비교한 뒤에 더 작다면 v_arr를 수정하고, heap에 넣어줌 반복 계산 v_arr 출력 import sys import heapq input = sys.stdin.readline V, E = map(int, input().sp..

2021. 3. 30. 03:00
개발/알고리즘

[백준 1918] 후위 표기식 (python)

1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 피연산자들은 바로 print, 연산자들은 우선순위 고려해 스택에 저장 )가 나오면 (가 나올때까지 연산자 프린트 피연산자라면 출력 ( 라면 스택에 저장 )라면 ( 나올때까지 연산자 출력 연산자라면 스택에 있는 연산자들중 우선순위가 낮은 것들 출력 나머지 남아있는 연산자 출력 import sys input = sys.stdin.readline prior = {"/": 2, "*": 2, "+": 1, "-": 1, "(": 0} stack = [] _st..

2021. 3. 29. 19:02
개발/알고리즘

[백준 11724] 연결 요소의 개수 (python)

11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net DFS로 연결 되있는 것들을 파악하자 이차원배열에 연결되어 있는 것들을 넣어준다 체크했었는지 visited로 흔적을 남겨놓는다 visited 하지 않았다면 answer늘리고 visited에 연결요소들 1로 바꾸어준다 몰랐던 점 - sys.setrecursionlimit(10000) -> 재귀 depth가 정해져있으므로 바꾸어 주어야한다 인접행렬 만들때 0,1로 다 채웠었는데 행마다 값을 넣어주는 방법도..

2021. 3. 19. 23:18
개발/알고리즘

[백준 2630] 색종이 만들기 (python)

2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net queue를 만들어서 확인할 색종이들을 저장해서 해결 전체에서 색이 다르다면, queue(꼭지점 네개)에 4등분 해서 넣어줌 같다면 blue, white 카운팅 import sys from collections import deque input = sys.stdin.readline N = int(input()) arr = [] for i in range(N): arr.append(list(map(int, input().split()))..

2021. 3. 19. 21:10
개발/알고리즘

[백준 2606] 바이러스 (python)

2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net DFS로 탐색 인접행렬과 방문흔적 남기는 배열을 생성한다 방문하지 않았고, 연결되있는 것들을 체크한다. import sys input = sys.stdin.readline N = int(input()) answer = 0 def dfs(x): global answer for i in range(N+1): if matrix[x][i] == 1 and check[i] == 0: answer += 1 matrix[x][i] = 0 matrix[i][x] = 0 check[..

2021. 3. 19. 18:47