본문 바로가기

📊 Algorithm92

🧚‍♂️알고리즘🧚‍♂️ - 동적 계획법(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.
🥉🥈브실브실🥉🥈 브실컵! 브실브실한 뻥골드인 나에게 딱 맞는 대회~라고 생각했는데 아침에 눈을 떴더니! 11시였다! 대회는 12신데~!~!~! 앞으로 다시는 늦게 자지 않겠다 지하철에서 한문제 풀고 1시에 도착해서 시작 6시까지 아무것도 못 먹고 문제 푸는데 탈주가 너무 하고 싶었다 547명 중에 70등이면 어떤 거지 내가 예배 안 드리고 튀어서 기분 별로인 엄마가 70등이란 말 듣고 못한 거 아니냐 해서 나름 괜찮다고 우기긴 했는데 으엉 임스랑 슬라임은 왜틀렸지???ㅠㅜ>? 6시간 동안(난 5시간) 비슷한 난이도 비슷한 로직 문제 계속 푸니까 좀 nojam..다음에 열리면 안 나가야겟당 끝나고 맛잇는 스파게티를 먹으니 기분이 좋아졌다 스트릭용 문제 또 풀어야 한다는 거 알고 다시 기분이 나빠졌다 배경이랑 뱃지가 예쁘지 않을 시.. 2023. 9. 10.
🧚‍♂️ 알고리즘 🧚‍♂️ - 기하(CCW) 🧚‍♂️CCW(counter-clockwise)🧚‍♂️ 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘 CCW 공식 점 A(x1, y1) , B(x2, y2), C(x3, y3) CCW = (x1y2 + x2y3 + x3y1) - (x2y1 + x3y2 + x1y3) 1) CCW 결과 0 점 세개 배치 : 반시계 방향 +) 결과값 / 2 삼각형의 넓이 골드 5 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net from sys import st.. 2023. 9. 10.
🧚‍♂️알고리즘🧚‍♂️ - 조합/순열 2 골드 5 1722 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 자릿수에 따른 순열의 경우의 수를 미리 구하기 N자리일 때 각 자리 경우의 수는 [N!개][N-1!개][ ]..... 면 1. k 가 주어졌을 때 값 구하기 각 자리 순열은 높은(앞) 자릿수부터 먼저 결정. 결정시에는 뒷 자리의 경우의 수 참고. 2. 값이 주어졌을 때 k값 구하기 앞자리부터 봐서 순서대로 봤을 때 미사용 수가 있으면 해당 자리의 경우의 수 카운트 from sys import stdin N = in.. 2023. 9. 6.
🧚‍♂️알고리즘🧚‍♂️ - 동적 계획법(DP) 2 실버 3 2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net - 0으로 끝나는 이친수의 개수와 1로 끝나는 미친수의 개수를 카운팅하는 배열을 만들어서 DP ㄲㄱ ㄱ 1은 0을 낳 0은 1과 0을 낳 0은 이전 0,1 합 1은 이전 0 개수 from sys import stdin N = int(stdin.readline()) # N자리 Nlist = [[0,1]] for i in range(N-1): zero = Nlist[-1][0] one = Nlist[-1][1] nlist = [zero .. 2023. 9. 5.
👑 Atcoder / CodeForces 👑 ..ing 👑Atcoder👑 Atcoder Beginner Contest. 매주 토요일 9시-10시 40분 AtCoder Problems kenkoooo.com 👑계획 - 시험기간 제외하고 / 약속 제외하고 전부 근데... 이번달에 되는날이 없네 👑목표 흠 👑CodeForces👑 무서운걸 👑계획 👑목표 2023. 9. 3.
🧚‍♂️ 알고리즘 🧚‍♂️ - 백트래킹 🧚‍♂️ 백트래킹🧚‍♂️ 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하던 중 원하는 값과 불일치하는 부분이 발생하면 이전 단계로 돌아가는 알고리즘 (DFS 연관) 실버3 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net def backTracking(): if len(ans) == M: # 배열의 길이를 확인 print(" ".join(map(str, ans))) # 1 2 3 이런 상태로 출력하기 위해 return for i in range(1, N+1): # 1 ~ N 까지 if i not in an.. 2023. 9. 2.

티스토리툴바