📊 Algorithm/Algorithm 주제별 정리45 🧚♂️알고리즘🧚♂️ - 동적 계획법(DP) 10 보호되어 있는 글 입니다. 2023. 11. 30. 🧚♂️알고리즘🧚♂️ - 비트마스킹 🧚♂️ 비트마스킹🧚♂️ 정수의 이진수 표현을 자료구조로 쓰는 기법 🧚♂️연산🧚♂️ AND 연산 (&): 대응하는 두 비트가 모두 1일 때, 1 반환 OR 연산 (|): 대응하는 두 비트가 하나라도 1일 때, 1 반환 XOR 연산 (^): 대응하는 두 비트가 서로 다르면, 1 반환 1010 & 1111 = 1010 1010 | 1111 = 1111 1010 ^ 1111 = 0101 NOT 연산 (~): 비트의 값을 반전하여 반환 ~1010 = 0101 왼쪽 Shift (): 오른쪽으로 비트를 옮긴다. (수 / 2^k) # k=2일때 결과 00001010 > k = 000010 🧚♂️활용🧚♂️ visited = [False] * 10 visited = 0b0000000000 < 집합에서 원소 추가.. 2023. 11. 28. 🧚♂️알고리즘🧚♂️ - 동적 계획법(DP) 9 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net Traveling Salesman problem (TSP) 외판원 순회 문제 - 한붓그리기 - 다시 처음 노드로 돌아올 수 있어야 함 - 최솟값 으엥 이게 디피문제인가 최소 신장 트리 아닌가?? . . . 아 이런 멍청한놈,, mst는 사이클만 안 생기면 통과다 그리고 외판원은 몸이 한 개다 한붓그리기 import sys from queue import PriorityQueue N = int(sys.stdin.readline.. 2023. 11. 28. 🧚♂️알고리즘🧚♂️ - 동적 계획법(DP) 8 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 부분 문제를 구해 큰 문제를 해결하는 방법-! D[i][j] : i - j 구간의 행렬을 합치는 데 드는 최소 연산 횟수 1개의 행렬로 합치는 데 드는 횟수 : D[1][N-1] +D[N][N]+a(두 행렬을 합치는 데 드는 값 점화식을 재귀 형태로 구현 톱 다운 방식 import sys input = sys.stdin. readline N = int(input()) M = [] D = [[-1 for j in range(N + 1)] for i in.. 2023. 9. 27. 🧚♂️알고리즘🧚♂️ - 동적 계획법(DP) 7 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 맨 처음에 두 발 0 동시에 움직일 수 없음 같은지점 누르기 -> 1 중앙에서 이동 -> 2 인접 위치 이동 -> 3 노인접 위치 이동 -> 4 최소 힘으로 누르기 D[N][L][R] : N개의 수열 수행 후 왼발 위치 L, 오른발 위치 R 일 때 누적 힘 D[N][L][R] = D[N-1][L][i] + "i -> R로 이동한 힘" D[N-1][i][R] + "i -> L로 이동한 힘" 중 최솟값! 오낑 import sys i.. 2023. 9. 25. 🧚♂️알고리즘🧚♂️ - 동적 계획법(DP) 6..ing 아 악 플래티 넘이잖 아 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 상근씨는 대체 누굴까? 백준씨의 강아지일까? D[N][L][R] : N개의 빌딩일 때 왼쪽 L 오른쪽 R 개가 보일 때 가능한 경우의 수 내일..채플 포기 이 문제나 이해해야지 2023. 9. 20. 🧚♂️알고리즘🧚♂️ - 동적 계획법(DP) 5 골드 4 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 가장 큰 정사각형의 넓이 == 가장 큰 정사각형의 한 변의 길이를 구하는 문제로 생각해볼 수 있음!! 점화식 생각하기 : D[i][j] : i j 위치를 꼭짓점으로 하는 정사각형 중에 최대 정사각형 해당 자리 위 왼쪽 완쪽 대각선 값이 모두 1 이상일 경우 더 작은! 값 + 1 하기 큰값은 정사각형이 아님 제일 큰 값을 제곱한 값이 정답이 됨 from sys import stdin N,M = map(int, stdin.readline().split()) D = [[0 for _ in range(1001)]for _ in r.. 2023. 9. 18. 🧚♂️알고리즘🧚♂️ - 동적 계획법(DP) 4 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS(Longest Common Subsequence, 최장 공통 부분 수열) 2ckdnjs fltmxm todtjd 오 이해가 안되는데~ import sys sys.setrecursionlimit(10000) input = sys.stdin.readline A = list(input()) A.pop() B = list (input()) B.pop() DP= [[ 0 for j in range(len(B) + 1.. 2023. 9. 16. 🧚♂️알고리즘🧚♂️ - 동적 계획법(DP) 3 골5 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속된 수를 선택해서 구할 수 있는 가장 큰 합 구하기 중간에 하나 뺴도 됨 작은 문제로 나누기! 왼쪽에서부터 인덱스를 포함한 최댓값 구하기 오른쪽에서부터 '' 그럼 하나 뺀 최댓값 구하기 가능 wow-- from sys import stdin N = int(stdin.readline()) nlist = list(map(int,stdin.readline().split())) result = nlist[0] #왼쪽으로부터의 최댓값 구하기 (수 하나 삭제용) L =.. 2023. 9. 14. 🧝🏻♀️ 알고리즘 re🧝🏻♀️ - 자료구조 1. ...ing 백준 코드플러스 강의~!~!~! 다시 기초부터 힘차지 않게 시작~!~! 이제..파이썬 없이 c++로 한다..!! 알고리즘 기초 1/2 알고리즘 기초 code.plus 1강 쉭 2강 쉭 문제를 열심히 풀자 c++로! 200 - 자료구조 1 스택 단어 뒤집기 괄호 스택 수열 에디터 큐 조세퍼스 문제 덱 단어 뒤집기 #include #include #include using namespace std; int main() { int T; string sen; stack st; cin >> T; cin.ignore(); while(T--){ getline(cin, sen); sen += ' '; // 맨 끝에도 공백 추가 for (int i = 0; i < sen.size() ; i++){ if (sen[i] =.. 2023. 9. 10. 이전 1 2 3 4 5 다음
