문제 유형이 문제는 2차원 DP(동적 계획법) 유형이다.각 칸에서 만들 수 있는 가장 큰 정사각형의 크기를 이전 칸들의 결과를 이용해 계산한다.DP 상태board[i][j]를 다음 의미로 사용한다.(i, j)를 오른쪽 아래 꼭짓점으로 하는 가장 큰 정사각형의 한 변 길이원래 값은 0 또는 1이지만, 계산하면서 DP 값으로 바꿔 저장한다.점화식현재 칸이 0이면 정사각형을 만들 수 없다.board[i][j] = 0현재 칸이 1이면:board[i][j] =min(위쪽, 왼쪽, 왼쪽 위 대각선) + 1코드로는:board[i][j] = min({board[i - 1][j], board[i][j - 1], board[i - 1][j - 1]}) + 1;세 방향 중 하나라도 작으면 ..

DP(Dynamic Programming) 핵심 정리DP는 이전에 계산한 결과를 저장해두고, 다음 계산에서 재사용하는 방식이다.핵심은 코드를 외우는 게 아니라 먼저dp[i]가 무슨 뜻인지 정의하는 것이다.1. DP 문제 풀이 순서DP 문제를 보면 이 순서로 생각한다.① dp[i]가 무엇을 의미하는가?② 현재 상태에서 어떤 선택이 가능한가?③ 그 선택을 이전/다음 dp와 어떻게 연결하는가?④ 최대값인가? → max 최소값인가? → min 경우의 수인가? → +⑤ 어떤 값이 먼저 계산되어 있어야 하는가? → 반복 방향 결정⑥ 초기값 설정예를 들어:dp[i] = i일까지 얻을 수 있는 최대 수익이라고 정의했다면,오늘 일을 한다오늘 일을 안 한다두 경우를 비교해서:dp[i] = max(한다, 안 한다..

기본 로직:정렬이 되어있는 상태에서 start 와 end 의 mid 를 이용하여 target 값 찾기 #include #include #include #include using namespace std;int N = 8;int M = 32;vector arr = {23,87,65,12,57,32,99,81};int binarySearch(int target){ int start = 0; int end = N-1; int mid; while (start target){ // arr 중간 값이 target보다 크다면 end = mid - 1; // 끝점을 옮긴다. } else{ // arr 중간 값이..

** pop 과 visited 설정을 잘 하자// 70. 그래프 - 1에서 각 정점으로 가는 최소 이동 거리#include #include #include #include using namespace std;int N = 6;int M = 9;vector ch(N+1,-1);vector> graph = {{1,3},{1,4},{2,1},{2,5},{3,4},{4,5},{4,6},{6,2},{6,5}};vector> tree(N+1);int min(int a, int b){ if (a q; q.push(1); ch[1] = 0; while (!q.empty()){ int idx = q.front(); q.pop(); for (int i = 0;..

그래프 탐색 / 최단거리 알고리즘 정리그래프 문제를 보면 먼저 “무엇을 구하는 문제인지”를 판단해야 한다.문제 특징사용 알고리즘가능한 경로를 전부 탐색DFS연결 요소 / 네트워크 개수DFS / BFS가중치가 없는 최단거리BFS모든 간선 비용이 동일한 최단거리BFS가중치가 0 또는 10-1 BFS양수 가중치 + 한 출발점에서 최단거리다익스트라모든 정점 → 모든 정점 최단거리플로이드-워셜핵심은 다음과 같다.모든 경우를 직접 돌아본다 → DFS몇 번 이동했는지가 중요하다모든 이동 비용이 동일하다 → BFS간선마다 이동 비용이 다르다한 지점에서 최단거리 → 다익스트라모든 노드 사이의 최단거리가 필요하다→ 플로이드-워셜1. 가중치 그래프 저장예를 들어 다음 그래프가 있다고 하자.1 --2--> 21 --5--> ..

- maps 복사할때 &maps 해서 주소 참조 하는거로 진행하기#include #include #include using namespace std;vector> arr = { {0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 1, 0}, {0, 0, 0, 1, 0, 0, 0}, {1, 1, 0, 1, 0, 1, 1}, {1, 1, 0, 0, 0, 0, 1}, {1, 1, 0, 1, 1, 0, 0}, {1, 0, 0, 0, 0, 0, 0}};int answer = 0;void DFS(int x, int y, vector> &maps){ if (x == 6 && y == 6){ answer += 1; return; ..

// 64번 경로 탐색#include #include #include using namespace std;// 정점의 수 Nint N = 5;// 간선의 수 Mint M = 9;vector> line = { {1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 3}, {2, 5}, {3, 4}, {4, 2}, {4, 5}};vector> graph(N+1,vector(N+1,0));// 1번에서 5번 까지만 가면 됨ㅇㅇint answer = 0;vector tmp;void DFS(int L,vector visited){ if (L == N){ answer += 1; return; } for(int i = ..

// 85 수식 만들기 #include #include #include #include using namespace std;int n = 3;vector arr = {5, 3, 8};vector cal = {1,0,1,0}; // 0: +, 1: -, 2: x, 3: /// 연산을 했을때 최댓값과 최솟값 리턴하기int max_ = -10000000;int min_ = 10000000;void DFS(int L, int total, vector ch){ if (L == n - 1){ if (max_ total){ min_ = total; } return; } for(int i = 0; i 0){ ch[i] -=..

Python → C++list → vectorappend → push_backset → unordered_setdict → unordered_maplen() → size()x in s → find(x) != end()x not in s → find(x) == end()for x in s:→ for (char x : s)print(x)→ cout > x;split()→ stringstreamheapq→ priority_queue 추가로 자주 쓰는 것[-1] * 26→ vector v(26, -1);'a'~'z' → 0~25→ c - 'a' ---#include // string 문자열#include // vector 동적 배열#include // cin, c..

세포: 생명체를 이루는 기본 단위세포는 생명체의 구조와 기능을 이루는 가장 기본적인 단위다. 사람, 동물, 식물, 세균은 모두 세포로 구성되어 있다.세포는 구조에 따라 크게 원핵세포와 진핵세포로 구분한다. 원핵세포진핵세포대표 생물세균, 고세균사람, 동물, 식물, 곰팡이핵막없음있음DNA 위치세포질의 핵양체 영역핵 내부세포소기관제한적미토콘드리아, 소포체 등 존재세포질 리보솜70S80S사람은 진핵생물이고, 장내 마이크로바이옴 분석의 주 대상인 세균은 원핵생물이다.원핵세포에는 DNA를 둘러싼 핵막이 없다. 반면 진핵세포는 핵막으로 둘러싸인 핵 안에 DNA를 보관한다. 이 구조적 차이 때문에 세균과 사람의 유전정보 처리 방식, 단백질 합성 장치, 약물 반응이 서로 다를 수 있다.DNA: 유전정보를 저장하는 분자D..

마이크로바이옴:- 미생물(Microbe)와 생태계(Biome)의 합성어- 몸 속 미생물과 그들의 유전체 전체- 면역, 대사, 뇌 기능에 깊이 관여하여 제 2의 장기라고 불림 마이크로바이옴 데이터: 인체에 존재하는 미생물의 구성과 기능을 수치화한 데이터 DNA를 추출해 미생물 종류와 풍부도를 분석하고, 이를 질병 상태·건강검진·생활습관 정보와 연결한다. 1. CRC Gut Microbiome ML Data이 데이터셋은 장내 미생물 정보로 대장암(Colorectal Cancer, CRC) 여부를 분류하는 머신러닝 분석용 데이터다. 16S rRNA 시퀀싱 결과를 DADA2로 전처리한 뒤, 미생물 조성표와 환자 메타데이터를 제공한다.구분내용분석 대상대장암, 건강인, 선종분석 기술16S rRNA 시퀀싱표본 수60..

1. 해시완주하지 못한 선수from collections import Counterdef solution(participant, completion): answer = '' Counter_p = Counter(participant) Counter_c = Counter(completion) for c in Counter_c: Counter_p[c] -= Counter_c[c] for p in Counter_p: if Counter_p[p] > 0: answer+= p return answer 폰켓몬from itertools import combinationsdef solution(nums): answer = 0 ..