알고리즘(코딩테스트)

1. 하나 고정하고 나머지 값을 통해 찾기배열에서 세가지 값의 합을 구하는 등의 작업을 할 때, 하나의 값을 고정시켜두고 나머지 값들만 투포인터를 통해서 계산하기 2. 문제https://www.acmicpc.net/problem/2473이 문제는"중간에서 만나기"를 쓰면 추가 공간이 필요하여 메모리가 터진다.n = 5000이기 때문에 n^2은 25,000,000이 되고, 여기서 long long값과 인덱스 2개를 int로 저장하면25,000,000 * (8 + 4 + 4) = 400,000,000 400MB 메모리 필요하므로 메모리 초과가 될 것이다. 풀이더보기#include #include #include #include using namespace std;int n;vector vec;long lo..

1. 중간에서 만나기알고리즘의 전체 탐색 범위를 반으로 나누어, 양쪽에서 동시에 탐색을 시작해 중간에서 만나는 방식으로 시간 복잡도를 줄이는 기법예시00000000~99999999 비밀번호 풀기앞의 4자리와 뒤의 4자리를 따로 계산한 결과 A와 B를 합쳐서 정답이 되는지 확인하기10^8의 연산을 10^4 * 2 의 연산으로 줄여준다A+B+C+D = 0 찾기A+B = -(C+D) 로 계산하기모든 조합의 합을 계산 : n^2C+D를 정렬한 후 A+B를 순환하면서 이분탐색을 하기 : O(N^2logN)N^2사이즈의 A+B 배열을 돌면서 O(N^2)N^2사이즈의 배열을 이진탐색 O(logN^2) 하기 -> O(N^2logN^2)!중요!메모리 제한을 항상 생각하고 쓰기이 방식은 메모리를 많이 사용하게 된다! 2..

1. 개념문자열을 효율적으로 처리하기 위한 트리 자료구조삽입 삭제 탐색에 있어서 O(|S|) 시간이 소요그러나 메모리는 최대 4*글자의 종류 만큼 차지하므로 메모리 효율은 좋지 않다.이론적인 시간 복잡도와 달리 실제로는 트라이가 해시나 이진 검색 트리에 비해 느리다.그러나 이 특징을 사용해야하는 문제가 있다.문자열의 접두사 검색 등과 같은 느낌 2. 구현코드#include using namespace std;const int ROOT = 1;int unused = 2; //새로 추가할 정점const int MX = 10000 * 500 + 5; //최대 등장 가능한 글자 수 -> 최대 500인 문자열이 10000개 들어온 경우bool chk[MX];int nxt[MX][26]; // 각 정점에서 자식 ..

1. 개념방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬을 말한다.예를 들어, 교과 이수 제도가 있다.특정 과목을 듣기 위해서 선수과목이 있는 그런 형태를 말한다.주의할 점같은 그래프에서 여러 가지의 위상 정렬이 있을 수는 있다.단, 그래프의 순환이 있는 경우는 위상정렬이 될 수 없다. 위상 정렬은 사이클이 없는 방향 그래프(DAG) 에서만 정의된다. 2. 구현참고indegree : 자신에게 들어오는 간선의 수동작 방식모든 간선을 순환하여 indegree 테이블 채우기indegree가 0인 정점들을 queue에 넣기queue에서 pop을 통해 위상 정렬 결과에 추가해당 정점으로부터 연결된 모든 정점의 indegree값을 1감소, 만약 이 때 indegree가 0이라면 ..

1. 플로이드 알고리즘모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘방향 그래프나 무방향 그래프 모두 상관없음간선이 음수여도 동작함, 단 음수 사이클은 없어야 함시간 복잡도는 O(V^3)왜 쓸까?예를 들어 정점이 100개 정도일 때 쓸만함 -> 코드가 쉬우니까모든 정점에 대한 거리를 알고 싶을 때 경유지를 고려해야 할 때 (다익스트라 같은 경우는 A->Z 까지의 최단 거리만 구하기 때문)또한 음수 가중치가 있는 경우.. 2. 동작 방식먼저 테이블을 만들어 두고, 각 정점에서 인접한 정점까지의 거리만 업데이트하여 최단 거리 테이블을 만든다.지금까지 적어둔 값은 어떠한 정점을 거치지 않았을 때의 모습이다. 이제부터는 특정 정점을 거쳐가면서 더 짧은 경로가 있다면 업데이트 해주면 된다.아래 모습은 정점 1은..

1. 기본공백 포함 하는 문자열 입력 받을 때string str;getline(cin, str); 문자 -> char'a' -> 97'z' -> 122'A' -> 65'Z' -> 90 2. 특정 문자 고르기int idx = pattern.find('*'); st = pattern.substr(0, idx);en = pattern.substr(idx + 1); 3. 숫자만 있는 string인지 체크하기bool IsNumber(string query){ for (const char& ch : query) { if (!isdigit(ch)) return false; } return true;} 4. char 로 string 만들기https://www.acmicpc.net/problem/1213연속한..

이전 내용https://gbleem.tistory.com/87 1, 2 주차 알고리즘 정리1. STL 기본 구조STL이란C++ 내장 템플릿 기반 라이브러리컨테이너, iterator, 알고리즘으로 구성되어 있다.주요 컨테이너vector동적 배열로 구현된 컨테이너원소 삽입/삭제를 마지막 원소에 할때는 O(1gbleem.tistory.com 1. 정렬https://gbleem.tistory.com/98 버블, 선택, 삽입 정렬 + 퀵 정렬업데이트) 병합 정렬과 이분탐색 알고리즘 추가자세한 예시는 해당 글에 있고, 전반적인 정리는 아래 링크의 글을 참고하면 된다.https://gbleem.tistory.com/128 정렬 및 탐색 알고리즘 정리1. 정렬 알gbleem.tistory.com 버블 정렬앞에서부터 ..

참고자료https://blog.encrypted.gg/1024 [실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MST라고 많이들 부릅니다. 그런데 Spanning이나 신장 이 단어가 너무 낯설지blog.encrypted.gg 1. 최소 스패닝(신장) 트리신장 트리란주어진 방향성이 없는 그래프의 부분 그래프들 중에서 모든 정점을 포함하는 트리를 말한다.부분 그래프란 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 그래프를 말한다.참고) 트리는 무방향이면서 사이클이 없는 연결 그래프그림 예시신장트리가 아닌 예시는 모든 정점을 포함하지 않거나, 사이클이 존재하기 때문..

1. Longest Common Substring두 문자열 사이에서 연속적으로 공통된 문자 중 가장 긴 문자열 찾기 (최장 공통 문자열) 과정2차원 배열을 통해서 하나씩 비교하면서두 문자가 다르면 dp[i][j] = 0같은 문자가 나온 순간 dp[i][j] = dp[i-1][j-1] + 1아래와 같은 표의 형태로 dp 배열을 구성할 수 있다 -ABC DEF-0000000G0000000B0010000C0002000D0000300F0000001E0000010 결론적으로 최장 공통 문자열의 길이는 3이 된다. 2. Longest Common Subsequence최장 공통 "부분수열" -> 중간에 끊기더라도 부분수열로서 연속된 문자열을 찾기 과정2차원 배열을 통해서 하나씩 비교하기두 문자가 다르면 dp[i -..

1. 특징배낭 문제 유형의 경우, 특정 스텝을 나아가는 도중에 "제약조건" 을 가지고 있어서 해당 조건을 체크해주는 작업이 필요하다. 예를 들어,물건들을 고르는 방법의 수를 구하는데 "최대 무게"가 정해져 있음동전을 모으는 방법의 수를 구하는데 "최대 금액" 이 정해져 있음인사를 하면서 얻는 기쁨을 구하는데 "최대 체력"이 정해져 있음  그렇기 때문에, 이중 for문을 사용해야 하는 경우가 많다.step을 밟아 나가는 for문제약조건을 지켜주는 for문 2. 예시https://www.acmicpc.net/problem/1535 이 문제는 가장 스탠다드한 형태의 문제이다.바깥 for문을 통해 step을 밟아 나가면서안쪽 for문을 통해서 제약조건을 지켜준다.더보기#include using namespace..