코테준비 (9) 썸네일형 리스트형 LCS(Longest Common Substring) 알고리즘 두 문자열에서 최장 공통 부분문자열(연속) 찾기 DP(Dynamic Programming) 이용int dp[n][m];int a[n];int b[m];if(i==0 && j==0) dp[i][j] = 0;else if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1]+1;else dp[i][j] = 0; dp배열의 최댓값 => 최장 공통 부분문자열 길이 [알고리즘] 위상정렬 위상 정렬, topological sort순서가 정해져있는 작업을 차례로 수행해야 할 때 사용DAG(Directed Acyclic Graph)에만 적용 가능 / 사이클이 발생하지 않는 방향 그래프시간 복잡도: O(V+E)/정점 개수 + 간선 개수 예시> 대학의 선수과목(prerequisite)만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. Queue로 구현- 깊이가 0이 정점 큐에 삽입- 큐에서 정점 꺼내서 연결된 모든 간선 제거- 간선 제거하면서 방문한 정점은 깊이 1씩 감소-.. [softeer/c++] 좌석 관리/string 비교 string 비교함수 compare#include string s;if(s.compare("string") == 0) cout compare함수는 두 문자열이 같으면 0, 다르면 -1 반환 틀렸을 때- sqrt 함수 사용한 safety 변수를 double로 받아야 하는데 int로 했었음- 메모리 해제를 안 했음 #include #include #include #include #include #include using namespace std;int N, M;int **seat; //N+1*M+1 배열double cal_safety(int x, int y){ //(x,y) 좌석의 안전도 구하기 double min = 40.0; for(int i=1; i max_safety(){ //안전.. [그래프] 백준 1389 c++ 케빈 베이컨의 6단계 법칙 오 어려움 예전에 풀려고 했다가 못 풀었던 거 같음 브루트포스가 아닐까 하는 생각 ... for(int i=1; i> M; int min_dist[101][101] = {0, }; vector con; vector v; con.push_back(v); // 친구 배열 채워주기 for(int i=0; i> r >> c; arr[r][c] = 1; arr[c][r] = 1; } for(int i=1; i [그래프] 백준 1260 c++ / Nested Functions, 정적배열과 동적배열, memset .. 몇 가지 궁금점 그래프 탐색 결과를 출력해야 하는데 문득 main 함수 내에 dfs, bfs 함수를 정의할 수 있을지 궁금해졌음 -> 바보같은 생각 걍 main 밖에 함수 정의하고 cout 하면 됨 그래도 중첨 함수 선언에 대해 알아보자 Nested Functions, 중첩 함수 Nested functions이란 다른 함수의 내부에 정의된 함수이다. nested function 예시) foo (double a, double b) { double square (double z) { return z * z; } return square (a) + square (b); } GNU C 확장에선 지원되지만 GNU C++에서는 지원되지 않는다고. 참고: https://gcc.gnu.org/onlinedocs/gcc.. [브루트포스] 백준 1107 C++ / 또 무수한 틀림과 하 또 막혔다 또 #include #include #include using namespace std; int N, M; int *broken; int calMin(int num) { // 1. 100에서 +, -해서 움직이는 횟수 int fromHundred = abs(100-num); //2. 앞자릿수부터 고장난 숫자 있는지 검사 string cp = to_string(num); for(int i=0; i N >> M; broken = new int[M]; for(int i=0; i> broken[i]; // N이 100이면 0 출력 if(N == 100) { cout [분할정복] 백준 1074 c++ Divide and conquer algorithm, 분할 정복 알고리즘 : 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 보통 재귀함수를 통해 구현 function F(x): if F(x)의 문제가 간단 then: return F(x)을 직접 계산한 값 else: x를 y1, y2로 분할 F(y1)과 F(y2)를 호출 return F(y1), F(y2)로부터 F(x)를 구한 값 어렵다.. 처음에는 2차원 배열의 모든 칸을 돌면서 숫자를 써넣은 다음 r, c에 맞는 칸의 값을 출력하는 방법을 생각했는데 어떻게 코드를 작성해야 할 지 감이 잘 안 옴 제출 코드 #include #include using namespace std; int **arr; int r, c; int n =.. [그래프] 그래프 탐색, DFS, BFS 앞의 글에서 푼 백준 1012번이 그래프, DFS였음 뭔지도 모르고 풀었나 심각함 하지만 이젠 알아야 함 마침 2-2 알고리즘 강의 ppt가 있음 그래프 표현 정점 개수 E 간선 개수 V 공간 복잡도 인접 리스트 (Adjacency-list) directed graph, undirected graph 모두 공간 복잡도 Θ(E+V) 인접 행렬 (Adjacency-matrix) directed graph, undirected graph 모두 공간 복잡도 Θ(V^2) 그래프가 sparse하다면, 간선의 개수가 적다면 인접 리스트가 더 나음 그래프가 dense하다면, 간선의 개수가 많다면 인접 행렬이 더 나음 모든 정점을 방문하는 데 시간 복잡도 인접 리스트: Θ(E+V) -> 더 효율적 인접 행렬: Θ(V^2.. 이전 1 2 다음
