안 쓰던 블로그

약수 1: https://www.acmicpc.net/problem/4375 약수: https://www.acmicpc.net/problem/1037 C가 A의 약수라면, A/C도 A의 약수가 되어야 한다 C=3, A=24라면, 24/3=8도 24의 약수가 되어야 한다 그러면 중간을 기준으로 대칭을 이루게 된다 이 아이디어로 전체 약수를 구할 때 더 빠르게 구할 수 있다 전체 약수 구하기 1. 1~A로 모두 나눠보기: O(A)걸림. N개 수에 대해서 연산하므로 N*O(N) = O(N^2) 2. 1~루트(A)로 모두 나눠보기: O(루트(A))걸림. N개 수에 대해서 연산하면 N*O(루트(N))=O(N*루트(N)) 이런 아이디어는 범위가 클 때 사용 가능하다 N

[1번 케이스] #include #include using namespace std; int main() { string s; int n = 100000; for (int i = 0;i < n;i++) { s += "A"; } return 0; } 이것은 O(N)의 복잡도가 걸린다 [2번 케이스] #include #include using namespace std; int main() { string s; int n = 100000; for (int i = 0;i < n;i++) { s = s + "A"; } return 0; } 이것은 O(N^2)의 복잡도가 걸린다 1번 케이스는 문자열 s의 마지막에 "A"가 추가되는 방식으로 돌아간다. 2번 케이스는 매번 새로운 문자열을 만든다고 할 수 있다. 즉, ..

관련 문제 -이진 검색 트리: www.acmicpc.net/problem/5639 (전위->이진트리) -완전 이진 트리: www.acmicpc.net/problem/9934 (중위->이진트리) 이진 검색 트리 문제부터 본다 전위 순회한 결과 값으로 후위 순회하는 문제이다 전위 순회는 루트-왼쪽-오른쪽 순으로 방문한다 이진 트리는 들어온 값을 루트부터 시작하여 값이 큰지 작은지 비교, 왼쪽/오른쪽 어느 서브 트리로 보낼지를 결정해야 한다 이 문제에서 전위 순회 결과로 이진트리를 만드는 작업은 다음과 같이했다(참고: www.acmicpc.net/problem/1539 ) 1. 전위 순회는 무조건 첫 값이 루트이므로 첫 값은 루트로 넣는다 2. 값을 하나 입력 받는다 3. 현재 노드를 나타낼 now변수를 둔다..

순열 next_permutation()과 prev_permutation() 직접 구현하기 다음 순열, 이전 순열, 모든 순열 순열 크기 n이 3인 수열을 사전순으로 나열하면 다음과 같다 123 132 213 231 312 321 n=3인 수열은 총 6개가 있다 여기서 먼저 알 수 있는 사실은 크기가 n인 순열을 총 n!개 존재한다는 것이다 첫 번째 오는 수를 n가지 중에서 선택, 그 다음 수를 n-1가지 중에서 선택, 그 다다음 수를 n-2가지 중에서 선택..을 반복하기 때문에 총 가지 수는 n*(n-1)*(n-2)*...*2*1 즉, n!이다 또 알 수 있는 사실은 첫 순열은 오름차순, 마지막 순열은 내림차순이라는 것이다 그러므로 중간 순열을 구하고 싶다면 첫 순열에서 다음, 다음, 다음으로 넘어가서 ..

1. cin, cout, endl 사용금지(느림) printf, scanf, \n사용 이런 식으로 언어마다 사용하면 좋은 입출력 함수가 있어서 자기 언어 관련으로 백준 입출력 팁을 구글에 검색해서 보면 도움이 될 것 같아요 2. for문 줄이기 특히 중첩 for문 3. 끝나지 않는 while(1) 1. 비주얼 스튜디오, vs code등의 컴파일러나 ideone등의 웹 컴파일러에서 미리 코드 실행!!! 코드 실행으로 컴파일 에러는 대부분 해결!! 2. 백준에서 알려주는 에러 메시지를 잘 확인 3. 문법 에러 4. 함수에 적당한 헤더를 가져왔는지 확인하기. 원래는 안 되는 코드인데 컴파일러에서 임의로 돌게 해 주는 것들도 있음 예: #include 에서 strlen 함수를 쓰지 마세요 strlen은 stri..

스택 개념 -스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능 -top의 위치에서만 원소를 삽입하므로, 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓이는 구조 -마지막에 삽입(Last-In)한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제(First-Out)됨. 이런 구조를 후입선출 구조 (LIFO, Last-In-First-Out)라고 한다 –스택에서의 삽입 연산 : push –스택에서의 삭제 연산 : pop 스택의 원소 삽입/삭제 과정

그래프 순회=그래프 탐색: 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하여 처리하는 연산 깊이 우선vs너비 우선 깊이 우선 탐색 순회 방법 -시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다가 더 이상 갈 곳이 없을 때, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와 다른 방향의 간선으로 탐색을 계속 반복하는 식 -가장 마지막에 만났던 갈림길 간선의 정점으로 돌아가야 하기 때문에 후입선출 구조 스택을 사용한다 구현 1. visited라는 방문 체크 배열을 전부 false(하나도 방문하지 않은 상태)로 초기화 2. 스택 생성 3. visited[v]=true; 시작하는 첫번째 위치는 방문했다고 표시 4. 스택이 empty가 아닐 때까지, 현재 노드의 인..