본문 바로가기

Algorithm/Basic

(15)
알고리즘 메모장[자바] 보호되어 있는 글입니다.
프로그래머스 레벨 1 ALL SOLVED, 오답정리 요약1. 문자열 선언할 때 오타ex) string arr[10] = {"zer","one", "two", "thr", "fou", "fiv", "six", "sen", "eig", "nin"};2. string 띄어쓰기 단위로 분류https://chbuljumeok1997.tistory.com/423. 시간복잡도, 공간복잡도 계산4. 전체적인 구성 생각 후 코딩5. 중간 중간 생각대로 코딩됐는지 cout 등으로 찍어보기6. 중간 계산값이 int형 범위를 넘는 경우7. 문자열 변환 실수ex)int n = 12;(char)(n +'0')8. 테스트 케이스 추가하기ex) 답이 없을 경우, 최솟값, 최댓값, 전부 같은 경우, 전부 다른 경우, 전부 답인 경우, 전부 답이 아닌 경우첫 제출에 백점이 아닌 문제들 ..
다이나믹 프로그래밍[Dynamic Programming] 문제풀이-2 (10문제) 11048 이동하기 https://www.acmicpc.net/problem/11048문제의 특징 1. 시작-> 도착 2. 이동방향3. 양의 정수 이동할수록 문제의 크기가 작아진다. 위나, 왼쪽으로 이동 못하므로 -> 항상 문제가 작아지므로 다이나믹 프로그래밍이라고 알 수 있다. 풀이 1O(NM) = NxMx1D[i][j] = (i, j)로 이동할 때 가져올 수 있는 최대 사탕 개수D[i][j] = Max(D[i-1][j-1], D[i][j-1], D[i-1][j]) + maps[i][j];for(int y=1; y풀이 2현재 d[i][j]까지 값을 채웠고 다음 3가지 방법을 채우는 방법 (1번과 순서가 다름)D[i][j+1] = D[i][j] + maps[i][j+1]; = max(D[i][j+1]);..
알고리즘 문제풀이 메모장 Codeforces등 대회 전에 읽어보려고 두서 없이 쓴 글..  요즘 실수 하는 것들 문제를 정확히 안봄, O(n)계산으로 충분히 정확한 방법을 생각안함.답이 long long인지 처음에 생각하기  헤더파일 #include  : 모든 헤더포함vector, algorithm, stack, set, tuple, queue, map,  memset, memcpy 등 사용할때 컴파일 에러 주의visual studio는 자동호출 하지만 cstring 호출 필요 string와 cstring, string.h의 차이점 인지 시간 입력속도 비교 https://www.acmicpc.net/blog/view/56  최대입력개수가 100만개 이상일 경우cin, cout, coutendl은 개행문자를 출력할 뿐만 아니라 출..
트리(Tree) 트리 : 사이클이 없는 그래프, 정점의 개수 : V, 간선의 개수 : V-1 루트가 있는 그래프 : 루트를 1번이라고 하며, 루트부터 아래로 방향을 정할 수 있다.부모(Parent)자식(Children)단말 정점(Leaf Node, Terminal Node) : 자식이 없는 노드형제(sibling) : 같은 부모를 가지는 노드깊이(Depth) : 루트에서 부터 거리(루트의 깊이는 0 or 1로 표기가능)높이(Height) : 깊이중 가장 큰값조상(Ancestor) : 자기자신을 포함하여 루트와 이어지는 노드자손(Descendent) : 조상과 반대트리의 지름(Diamater) : 트리에 존재하는 모든 경로 중에서 가장 긴 것의 길이 - 2번의 탐색으로 구할 수 있다. - 1. 루트에서 모든 정점까지의 거..
그래프(Graph) 그래프(Graph) : 정의 구성 : 정점(Vertex), 간선(Edge) G = (V, E) 경로(Path) 사이클(Cycle) 단순 경로와 단순 사이클(Simple Path and Simple Cycle) : 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클(일반적인 경우) 방향 있는 그래프(Directed Graph) 방향 없는 그래프(Undirected Graph,) : 양방향 그래프(Bidirection Graph) 간선 여러개(Multiple Edge) 루프(Loop) 가중치(Weight) 차수(Degree) 연결요소(Connected Component) 이분그래프(Bipartite Graph) : DFS또는 BFS 탐색으로 이분 그래프인지 아닌지 확인가능 플러드 필(Floo..
정렬(Sorting), Stable_Sorting youtu.be/kPRA0W1kECg 정렬 알고리즘을 소리로 표현한 영상이다. 정렬 방법은 30가지가 넘는 여러가지가 있다., 정렬 알고리즘의 종류로는 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 힙 정렬, 병합 정렬, ...... 등 여러가지가 있지만, 알고리즘 문제풀이에서 주로 사용하는 것들은 정렬시간이 O(NlogN)이 걸리는 정렬을 사용한다. 정렬을 직접 구현하는 것보다는 STL에 있는 sort를 사용하는 것이 좋다.
수학 1. 나머지 연산 2. 최대공약수와 최소공배수 3. 소수 4. 에라토스테네스의 체 5. 골든바흐의 추측 6. 관련문제 수학문제 복습! 1. 나머지 연산(Modular Arithmetic) 컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 답을 M으로 나눈 나머지를 출력하라는 문제가 등장한다. 더보기 예를 들어, 다이나믹 문제를 풀때 경우의 수가 너무 큰경우 int값이나 long 값을 넘어서, 값을 처리를 하기 위해서 큰 정수값(big integer)을 구현하기 보다는 몇으로 나눈 나머지를 처리하라는 문제가 많다. (A+B) mod M = ((A mod M) + (B mod M)) mod M (AXB) mod M = ((A mod M) X (B mod M)) mod M 나누기의 경우에는 성립하..