비밀일기

5-1) 그래프노드와 엣지의 집합 유니온 파인드그래프의 사이클이 생성되는지 판별하는 알고리즘위상 정렬사이클이 없는 방향 그래프에서 사용가능.그래프의 노드들을 선형으로 정렬. 정렬 결과가 꼭 한개는 아님 ex)수강신청다익스트라시작점이 존재하고 그 노드에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘.단 음수 간선은 있으면 안됨  =>최단거리 알고리즘 벨만-포드다익스트라 알고리즘인데 음수 간선이 가능함.  음수 사이클이 존재하는가=>최단거리 알고리즘 플로이드-워셜벨만 -포드 알고리즘 인데 시작 노드가 없음. 즉 모든 노드 사이의 최단거리 측정. (시간복잡도가 안좋음)=>최단거리 알고리즘 최소 신장 트리 mst. 그래프에서 최소의 가중치 합으로 모든 노드를 연결할 수 있게 해주는 알고리즘. 사이클이 없..

5-1) 반복반복문이 사용되는 이유: 반복적인 수행을 간결하게 작성하기 위해. 특정 코드를 반복해서 실행할 때 사용된다. 반복문에는 while 과 for 문이 존재함 5-2) while문 1while(조건){문장} 조건을 확인하고 조건이 충족될 경우 블럭 속 문장이 시행된다.조건이 만족되지 않을 경우 루프가 계속 실행된다. 5-3) while문 2문제) 숫자가 1씩 증가할때 1,2,3, 덧셈   식을 바꾸고 싶을 때 변경해줄 변수가 적다는 것이 장점 문제)i 부터 end까지 num 개 더하는 식   10 부터 1씩 증가하는 숫자를 3개 더해주는 루프10+11+12=33임 확인 가능 5-3)do while문while문과는 다르게 조건을 만족하지 않아도 한번은 문장을 수행함. do{      문장}while..

4-1)소수 구하기 핵심 이론소수: 1과 자기 자신 외 약수가 존재하지 않는 수 기본 원리에라토스테네스의 체:1. 구하고자 하는 범위만큼 1차원 배열 생성2. 2부터 시작하고 현재 숫자가 지워지지 않을 때 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지움.이때 처음 선택한 숫자는 지우지 않는다.3. 배열의 끝까지 반복해준 후 배열에남아 있는 모든 수 출력이중 for문을 사용하므로 시간 복잡도는 N^2최적화 정도에 따라서 실제 속도는 n(log(logn))임.배수 삭제 과정에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문에라토스테네스의 체는 소수를 구하는 일반적 방법으로 이용된다.  4-2)오일러 피자주 등장하지는 않음오일러 피 함수 p(n)의 정의는1부터 n까지의 숫자중..

4-1)조건문 특정 조건에 따라 다른 코드를 실행하는 문장조건문을 만족하면 블럭 안 문장이 실행되고 아닌 경우 else가 실행되거나 else문이 없는 경우 다음 문장으로 넘어간다.  4-2)else-if문여러가지 케이스가 존재하는 경우 사용된다.if문의 나열을 통해서도 케이스를 검사할 수 있지만 그럴 경우 코드가 불필요하게 길어지고 앞에서 검사한 부분을 뒤에서 다시  검사하게 되는 상황이 발생하게 된다.이 상황에서 결과를 중복 확인하는 상황을 피하기 위해 else if문 사용.else문은 있어되 되고 없어도 된다.4-3)if문과 if-else문 if(조건)...if(조건) 각각의 조건을 서로에게 영향을 받지 않고 검사하는 경우 if(조건)...else(조건)각각의 조건을 검사하되 공통되는 부분의 검사는 ..

동전의 크기가 오름차순으로 주어지기 때문에 동전의 개수를 구하는데 나머지 연산가 몫 연산을 제대로 수행해주면 되는 문제.#includeusing namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, count=0; int long account; cin >> n >> account; int mUnit[11]; for (int i = 0;i > mUnit[i]; } for (int j = n-1;j>=0;j--) { count += (account / mUnit[j]); account = account % mUnit[j]; } cout 처음에 j의 범위를 n부터 0까지로 설정해 오류가 났었음..

요세푸스 문제#include#includeusing namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); int size, num,count; cin >> size >> num; count = num-1; dequeyo; for (int i = 1;i 0) { count = (count + num - 1) % size; } if (! yo.empty()) { cout '; return 0;} size를 하나씩 줄여가며 식을 수행하는데 zerodivision 에러가 일어나고 있었던걸 눈치채는데 좀 오래걸렸다.어쩐지 마지막 '>' 부분만 계속 출력이 안되더라..원형 자료구조를 이용하면서 인덱스로 접근하고 싶어서 데크를 ..

행운의 바퀴https://www.acmicpc.net/problem/2840#include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); dequelucky_chain; int size, m; cin >> size >> m; lucky_chain.assign(size, '?'); int flag = 0; for (int i = 0;i > num >> alph; flag = (flag + num) % size; if (lucky_chain[flag] != alph && lucky_chain[flag] != '?') {..

듣보잡두 map에서 겹치는 원소를 찾기 위해 추가적으로 result map을 이용하였다.모든 요소들을 result에 추가하면서 벨류를 증가시켜 겹치는 키의 벨류가 증가하도록 하였다.interator가 가르키는 요소의 키값이 존재하고 2번 입력받았다면 count를 증가시키고 아니라면 result 에서 원소를 삭제했다.count로 겹치는 요소의 개수를 출력해주었다.result에 남은 요소는 겹치는 요소만 남긴 것이기 때문에 result의 요소를 모두 출력해줘 프로그램을 완성했다. #include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); map see; map ..

서로 다른 부분 문자열의 개수0번 인덱스부터 1개, 2개,...,n개1번 인덱스부터 1개, 2개,...,n-1개..n번 인덱스부터 1개형태로 루프를 구성하여 문자열을 슬라이싱 해준 뒤 set 집합에 넣어 중복 원소를 제거해주었다.슬라이싱을 위한 메소드로는 str.substr(시작 인덱스,개수); 를 입력해주면 된다 #include#include#includeusing namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); setset_str; string str; cin >> str; for (int i = 0;i

최소 힙최대 힙과 거의 유사하게 풀이해주었다. 최소힙을 구성하기 위해서는prioirty_queue,greater>min_heap;으로 선언해주었다.#include#include#includeusing namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); priority_queue, greater>min_heap; long long num; int x; cin >> num; for (int i = 0;i > x; if (x == 0) { if (min_heap.empty()) { cout