- 범위 확인을 통한 시간 복잡도 예측
- 문제의 핵심 알고리즘 정의
- 문제풀때 상단에 문제풀이 순서 적기
- 과도한 cin,cout 시, 아래 코드 사용
ios_base::sync_with_stdio(false); cin.tie(NULL); - 비트마스킹 사용시, (1<<?) 가 10억(1초)을 넘어서서 한칸씩 옆으로 넘어가면 시간이 10배씩 증가하여 시간초과가 잘 발생함.
- 프로그래머스에서 함수에 시스템의 argument 배열을 매개변수로 넣을 때는 크기떄문에 오류가 발생할 수 있으므로, argument 배열자체를 전역배열로 옮겨서 사용하기. - 모두0으로만들기
- 다중 조건문 관련 구현법
if(maxi<cnt||(maxi==cnt&&maxi_zero<zero)) { maxi = cnt; maxi_zero = zero; maxi_idx = new int[] {i,j}; }
두배열 사이의 교집합을 제거하는데는 map을 활용하는게 find로 제거하는거보다 더빠른듯.
map2[x]--; 시 x가 map2에 존재하지않아도 -1로 생성됨.
map1[string]++를 하고 다시 --를 해서 0이되도 map1에 남아있음.
map도 vector형태로 변형시켜 저장가능함. set과 같은 방식 -> vec.assign(map.begin(),map.end())
getline(cin,x,'\n') 형태는 default로 /n만나면 종료되고, cin.getline(x,100,'\n') 형태는 글자수가 99가 넘거나, /n을 만나면 종료됨.
cout.setf(ios::fixed)로 소수점 아래부분만 출력범위 설정.
cout.precision(4)를 연속해서 쓰면 소수점아래 4자리만 출력. 원래는 총합 4자리.
if(cin.eof())로 eof만나면 종료되게 설정.
string은 index가 초과되어도 오류가 발생하지 않았음. 아마 null로 나오는듯? -> substr 시
iterator로 map 접근하는대신 for(auto pair : m) 처럼 접근해보기
vector 내에서 하나만 존재하는 특정 값 삭제는 erase와 find 조합으로 해결함. 여러개 존재하는 특정 값 삭제는 erase와 remove 조합으로 해결함. 문자열에서 공백제거를 erase와 remove 조합으로 해결함. 위의 방법은 vector에도 적용됨. 한 문자열에서 동시에 여러 인덱스를 지워야 되는 상황이면 인덱스들의 문자를 공백으로 바꾼 후, 공백제거를 사용함. -괄호제거
string erase는 vector erase와 똑같이 iterator를 사용하지만, string erase는 추가적으로 erase(0,4) 처럼 시작 idx부터 특정 개수만큼 제거가능함. substr과 유사함. 이외에 나머지는 전부 vector처럼 해야함. - 괄호변환
문제를 해결하면서 배열을 점차 삭제해야 하는 문제는 삭제를 하지않고, 'X'로 두어서 해결할 수 있는지도 생각해야 함. 배열 내에서 삭제된 배열을 고려하며, 배열 내에서 삭제, 이동, 복원이 이루어지는 문제는 링크드 리스트로 해결해야 시간복잡도를 가장 최적화시킬 수 있음. 링크드 리스트의 전형적인 문제임. - 표편집
다음에는 LCA알고리즘 사용해서 풀어보기.
LCA알고리즘은 분리집합처럼 parent를 생성하고, 첫번째 정점의 parent를 모두 true로 만든뒤 두번째 정점의 parent도중 true를 발견하면 그 정점이 공통조상임.
일반적으로 부모노드가 주어지는 문제는 각 노드의 부모노드만 설정해도 쉽게 해결할 수 있음. 다만 분리집합은 시간단축을 위해 부모노드가 최상단의 부모노드로 설정될 뿐임. - 가장 가까운 공통조상
preorder,postorder,tree형성함수(addNode) 구현, vector answer(2)로는 내부벡터 사용불가.
트리의 경우 단절선과 단절점 파악이 쉽다는 점을 생각해야했음. 제발 어려워보이면 푸는 알고리즘보다 아이디어부터 생각하기.
트리의 지름은 어느 노드에서 가장 먼 노드의 다시 가장 먼 노드까지의 거리임. 이진검색트리는 Node 자체를 구현하면서 진행하지만, 일반트리는 vector a[100] 처럼 그래프식으로 진행하면 됨. 가중치가 있다면, 다익스트라처럼 Edge를 활용함. dist배열을 구해야하는 다익스트라는 queue에 첫번째 노드를 집어넣어야하고, dist말고 전체길이만 구하면 되는 최소스패닝트리는 첫번째노드의 Edge들을 queue에 넣어야 함. - 트리의 지름
중위순회한 결과가 주어지는 문제는 보통 루트노드를 사용한 분할정복 개념임. - 트리
부모자식 관계를 통해 트리형성이 가능함. - 다단계칫솔판매
트리에 루트를 지정해주지 않으면 모든 노드가 루트가 될 수 있음. - 모두0으로만들기
BFS를 쓰려면 거리이동시 필요값이 1이여야함.
투포인터를 이중변수 for문으로도 작성할 수 있음. - 서강근육맨
set의 insert, erase는 element 단위로 이루어지고, vector의 erase는 iterator 단위로 이루어짐.
배낭들에 보석들을 넣어 최대가격을 구하는 문제에서 배낭마다 넣을 수 있는 보석 중 최대 값을 구해야 하는데 이걸 2중for문으로 구현하는 대신, Priority_Queue를 사용하여 특정 배낭에 넣을 수 있는 보석들을 전부 PQ에 넣어가며, 시간을 단축시킬 수 있음. 아이디어가 시간단축에 유용할 듯함. - 보석도둑
x*1 보다 x+1이 더 큼. 두 수의 곱셈은 항상 덧셈보다 크다는 그리디적 사고의 반례임. 알아두면 유용할 듯함. - 수묶기
DP문제는 문제가 분할정복처럼 점차 작게만들면서 답을 유도할 수 있나 확인한 뒤, 점화식을 메모장에 써서 정확히 구한 뒤에, 가능하면 BottomUp 방식으로 풀기.
DP문제를 파악할 때, 점차 작아지도록 생각할 수도 있는 반면, 점차 커지는 방향으로도 생각할 수 있음. 둘 중 하나로 생각하는데, 시간초과가 난다면, 다른 방법도 생각해야 함. d[n] = d[m] + a[n]; m < n 작아짐. d[n+t[n]] = max(d[n+t[n]],d[n]+p[n]) 커짐. - 퇴사2
배열을 일반적인 순서인 왼쪽에서 오른쪽으로 채우는 방식이 아니면, TopDown을 통한 재귀방식을 사용하는 게 좋음. 배열을 왼쪽에서 오른쪽에서 채워 문제를 해결할 수 있는지 직접 판별해야 BottomUp과 TopDown을 정할 수 있음.(중요) - 팰린드롬, 파일합치기
점화식을 세울 때, 중간에 있는 임의의 값은 k같은 변수로 둬서 생각해야 함. - 점프
재귀방식을 사용할 때, 메모이제이션 배열값이 0이 될 수 있는 경우 if(d[x]!=0) return d[x] 방식은 안됨. 따라서 meset으로 전부 -1로 초기화해주는 게 좋음.
피보나치 수열은 점화식을 재귀로 풀게되면, 너무 많은 재귀가 발생함. 이럴 경우, 메모이제이션(DP)를 사용하는 것임. 사용할 값을 배열에 저장해가면서 점화식을 진행해나감. - 피보나치 수
점화식은 TopDown, BottomUp 방식으로 풀수 있는데, TopDown은 재귀함수, BottomUp은 반복문임. 이때, 재귀함수는 일반적인 재귀함수가 아닌 메모이제이션을 활용한 재귀임. 점화식을 일반 재귀함수로 풀게되면, 진행과정에서 중복되는 계산이 너무 많아지게 되므로 재귀과정에서 결과를 배열에 값으로 집어넣어 다음 재귀에 활용함. 재귀함수는 당연하게 맨아래까지 내려간 후, 배열입력이 진행되면서 다시 올라옴.
TopDown 방식은 재귀를 통해 맨아래로 내려가 다시 올라오면서, 과정에서 필요한 배열을 점차 완성시켜서 올라옴.
문제에서 주어지는 N의 범위가 1이상이여도, 메모이제이션을 할때, 구해야 하는 배열의 N조건이 0부터일 수도 있음. 구현을 생각하면서 잘 판단해야 함. - 합분해
DP문제에서 배열로써 주어지는 값 구조 그대로 배열에 넣을 필요는 없고, 필요하다 싶으면 자신이 원하는 구조대로 값을 넣어도 됨. 예를 들어 a[x][y]에서 x를 열로 봐도 됨. - 스티커
메모이제이션 배열이 두 종류 이상 필요한 경우도 있음. - 바이토닉, 연속합2
순환배열 문제라고 해서 idx%배열크기 를 매번 적용시킬게 아니라, 맨 처음 칸과 맨 마지막 칸을 조작하여 해결할 수 있으면 최대한 후자를 사용함. - rgb거리2
경우의 수가 오름차 순이 되도록 하는 방법은 오름차 순으로 하나의 수만으로 메모이제이션을 하면 됨. - 1,2,3더하기 4
점화식을 세울 때, 마지막 칸을 더하냐, 더하지 않냐처럼 케이스가 나눠지는 문제는 왠만하면 배낭 문제의 형태임. 따라서 무게 또는 볼륨을 추가하여 2차원 배열로 해결해야 함.(중요) - 평범한배낭,기타리스트,뮤탈리스크
메모이제이션 배열의 인덱스가 0 미만으로 떨어지는 게 가능하면, 재귀방식으로 처리하는 게 좋음. - 뮤탈리스크
비트마스킹을 사용하는 DP 방법도 있음. - 외판원순회
6C3 같은 조합, 순열 문제는 이미 점화식이 정해져 있으므로, 재귀말고 DP(메모이제이션)으로 풀 수 있음.
5C3 같은 컴비네이션을 점화식(DP)으로 세우기 위해서는 우선 5C1 5C5 와 같이 고정된 값을 가지는 애들을 먼저 선언해주고, 모든 컴비네이션값을 먼저 구해줘야 함.
bottom-up방식에서도 현재를 과거값을 통해 갱신하는 방법과 미래를 현재값을 통해 갱신하는 방법 두가지가 있는데, 과거값을 통해 갱신하는 방법에만 익숙해져 있음. 고집부리지 않고, 문제에 따라 현재값으로 미래를 갱신하는 방법을 사용해야 함. - 코딩테스트공부
배열의 크기때문에 시간제한이 걸릴거같은 문제중, start,end로 범위를 나눌수 있는 문제는 투포인터로 시도해보기, 위 문제는 같은 경우는 배제해야만 풀수 있음.
else는 else if보다 훨씬 빠름. - 팀빌딩
vector의 set변형 -> set a(vec.begin(),vec.end())
**int형들을 다 더해서 long long으로 만들수 없고 따로 long long으로 형변환뒤 덧셈을 해줘야함. 형변환 해야하나 고민될때, 일단 형변환하기.
string의 erase는 (a,b) a:시작인덱스 b:지울개수
vector의 erase는 (a,b) a:시작iterator b:마지막iterator
max,min 함수내에 size() 같은 함수는 못쓰임. - 회전초밥
연속 부분수열 관련 컨벤션은 문제에 따라 약간씩 변형될 수 있음. - 부분합
달팽이모양 패턴을 간결하게 분석하는게 중요함.
이런종류의 문제는 칸마다 쪼개서 생각해보기.(분할정복) -> 빗물같은 2차원 그래프 문제
vector에서 clear()쓰면 넣어둔 원소들이 0 이되는게 아니라 다 제거됨.
배열 회전하는 함수(rotate) 익히기, 고난이도 배열구현 문제임. 아래 코드에서 v랑 tmp_v만 바꾸면 반시계방향 회전임.
-> for(int i=0;i<x;i++) { for(int j=0;j<y;j++) { tmp_v[j][x-i-1] = v[i][j]; } }
블록내리기 알고리즘 유용할듯 -> 프렌즈4블록
결과값의 1234567로 나눈나머지값을 리턴하라는 문제는 계산도중 int형범위를 초과하니 계산내에서도 나누기를 적용하라는 의미. -> 피보나치
굳이 permutation안쓰고 다중for문으로 풀수있으면 안쓰는게 좋음, substr의 두번째인자 안들어가면 마지막까지라는 뜻임.
Map을 사용해야 하는 상황이면 배열로써 대체할 수 있는지 확인하기. - 소가길을건너간이유1
map을 사용해야 할 것같은 문제는 배열로 해결할 수 있는지 확인하기. - n진수게임
while(true) 문은 for(int i=0;;i++) 처럼 for문으로 표현할 수 있음. - 다음큰수
2차원 그래프에서 점이 아닌 간선, 네모 칸 단위로 문제를 풀어야 할 경우 기준점 하나만 설정해서 해결할 수 있음. - 기둥과보설치
사이클 만드는지 여부를 확인하는 문제, bool형 dfs, 왔던곳 다시방문할수 있는 dfs -> twodots
그래프에 bfs를 적용하여 거리계산. 최단거리 계산문제는 다 bfs
반환형int 재귀함수 구현, 그래프에서의 사이클 탐색, 다중 시작점에서의 bfs거리 계산,반환형있는 재귀함수인데 최종반환형없게해서 dfs도중 마지막에서 튕겨져나올때 오류발생함.반환형 재귀함수는 최대한 마지막 튕길때 오류발생 고려하기. -> 서울지하철2호선
일반배열은 memset, vector는 fill로 초기화, 모든 그래프가 연결되지 않고 연결요소로 이루어질수도 있음.
check배열을 solution내에서 선언하면 시간초과발생하는데 오류같음.
완전탐색->이분탐색->bfs순으로 풀이법을 유추할수 있어야함. bfs를 쓰는데 집의 범위가 주어져있지 않으므로, check배열을 쓰지 않고 set을 사용함. 또한 dist배열에 거리를 담고 마지막에 다더하는게 아닌 집을 놓는 상황마다 정답에 거리를 추가해야하므로, while(!q.empty())내에서도 q.size()만큼 돌리고 넘어가면 dist에 +1을 해주는 식으로 생각해야함. 뱀과사다리 게임과 해당문제 같은 이분탐색과 비슷한 모형의 문제에서 bfs를 생각하지 못함. -> 샘터
tuple사용을 통한 3차원 구현. + get<0>(personInfo),get<1>(personInfo),get<2>(personInfo) -> tuple 사용문제 만나본적 거의없음.
factorial 구현
long long factorial(int num)
{
if(num<=1) return 1;
return num*factorial(num-1);
}
2차원 memset은 동일스코프에 있을 때만 memset(dist,-1,sizeof(dist))처럼 가능하고, 외부의 배열을 다루는 경우, for문 + memset(dist[0],-1,sizeof(dist[0]))처럼 사용해야 함.
n개중 m개를 고르는 재귀함수 구현은 n과m4 문제의 방식을 사용함. - 연구소
단순 최소거리 계산 bfs가 아닌, 최소 커브계산 bfs문제처럼 변형된 bfs문제도 해결할 수 있어야 함. 최소 커브계산 bfs는 한쪽으로 쭉 이동하며 Queue에 넣어주는 방식을 사용해야 함. 또한, bfs문제에서 이미 계산된 칸은 checked처리하여 무시할 수 있었지만, 해당 문제는 쭉 이동하는 칸들에 이미 계산된 칸이 섞여있을 수 있으므로, 무시하고 넘어가줘야 함. 이미 최소거리가 계산된 칸은 그게 최소거리이므로, 덮어 쓰는 것처럼 절대 건들면 안됨. 그러면 현재 최소거리를 나타내는 최소 커브수가 깨지게 됨. - 레이저통신
2차원 배열에서 최소거리, 또는 도달여부를 판별할 때만 bfs를 쓰고 최대 거리가 얼마나 되는지는 사용할 수 없음. 도달여부가 가능한 것도 최소거리가 뜨지 않으면 도달할 수 없음으로 판별가능한 것임. 원하는 거리단위가 무엇인지 꼭 확인해야함. - 알파벳
점차 이동하거나 퍼지는 특정 칸들의 현재 칸, 다음 칸을 피해야 하는 상황에서 먼저 해당 칸들을 이동시키거나 퍼지게 하는 방식대신, 먼저 타겟이 되는 칸들을 이동시킨 후, 다음 while문에서 해당 칸이 피해야 하는 칸으로 바뀌었는지 확인해주는 게 좋을 듯함 -> 이동 후 칸이 바뀌었는지 확인하면 일단 해당칸은 이동한 상태가 되므로 잘못된 이동을 하게 됨. 따라서 불이나 물을 먼저 이동시킨 후 사람이 이동하도록 순서를 바꿔주는 게 맞음. - 움직이는 미로탈출, 탈출
bfs를 사용할 때 도중에 열쇠를 만났는지와 같은 상태값을 저장하려면 좌표인 x,y와 함께 상태값을 묶어서 Queue에 넣어주면 됨. 여기서는 비트마스크를 사용하여 상태값을 나타냄. 또한 이렇게 상태값을 구분한다면, check배열이 3차원으로 바뀌게 됨. - 달이차오른다가자
사다리 타기 문제나 해당 문제처럼 출발하는 곳을 기준으로 하지 않고, 도착하는 곳을 기준으로 문제를 접근해주면 매우 간단해짐. 발상의 전환이 필요한 부분인 듯함. - 부대복귀
달이차오른다가자, 양과늑대처럼 그래프에서 노드 간 이동할 때, 다시 왔던 곳으로 돌아갈려면 상태값을 고려한 3차원배열을 설정해주면 됨. 이때, 방문점에 도달하기 전 상태를 배열조건으로 설정해주는 게 맞을 듯함.
단순히 2차원 그래프에서 최단거리를 찾기 위한 BFS가 아닌 특정 최솟값을 구하기 위해서는 BFS+DP가 필요함. BFS+DP는 주로 위에서 언급한 상태값을 통한 3차원배열을 주로 사용하여 2차원 점화식이 적용됨.
set을 통한 중복성검사, 비트단위 연산할때 무조건 괄호치기
연산자 배열과 숫자 배열의 합을 구하는 최적의 방법. -> 0만들기
swap함수를 이용한 배열인자 바꾸기
시간복잡도 파악을 못해서 시간초과걸림. 2차원 check배열을 활용하여 안되는 조합을 미리 제외함. 조합 내 포함되면 안되는 조합문제는 이렇게 check배열 활용하면 좋을듯함. -> 한윤정2422
순환배열에 % 사용
직사각형도 정사각형과 같이 90도 rotation가능, 단, N에 유의하고, vector<vector>를 복사 할 경우, 크기가 다르면 안됨. resize()를 통해 크기 변환후 복사하기. - 스티커붙이기 nxm 시계방향회전 ->
void rotate(vector<vector<int>> &a)
{
int n = a.size();
int m = a[0].size();
vector<vector<int>> tmp_a(m,vector<int>(n,0));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
tmp_a[j][n-1-i] = a[i][j];
}
}
a.resize(m,vector<int>(n,0));
a = tmp_a;
}
dfs문에 이중for문 집어넣고 돌리면 시간복잡도 매우커짐. 그러니 이중for문말고 idx/m,idx%m으로 이중for문 처럼 구현하기. 처음 dfs문이 돌아가는 순간 이중for문이면 처음이 이중for문만큼 시작됨. -> 종이조각14391
string도 array 취급이라 next_permutation 허용됨.
전체 배열 중 특정 개수의 배열 조합을 찾으려면, next_permutation 대신 check배열과 vector를 사용하는 dfs를 먼저 사용하는 게 좋음. 근데 (1,3)과 (3,1)이 같은 취급을 받으면 check배열 대신 idx를 통한 dfs 접근을 하는 게 좋음. - 두 스티커
n개의 집합에서 모든 부분 집합을 구하는 것은 비트마스크를 사용하는 게 간편할 듯함. - 도영이가 만든 맛있는 음식
for문은 무조건 첫 루프는 돌게되어 있음. maxi를 설정할 때, 음수가 될 수 있으면, max() 함수대신 *max_element를 쓰는 게 좋음. if(maxi==-1) 를 통해 초기값을 설정했다가, 다시 -1인 값이 나오면 꼬이게 됨. - 괄호추가하기
map을 사용하여 문제를 해결할 때는 map의 search과정에서 발생하는 시간복잡도도 생각해야함. - 단어수학
비트마스킹을 통해 구슬탈출 종류의 문제를 해결할 수 있음. 이때 2진수를 4진수로 바꾸는 함수를 알고 있어야함. 또한 해당 문제는 한번에 방향으로 싹 이동하면 안되고, 합쳐지는 것을 고려하기 위해 한칸씩 옮겨줘야함. 배열을 왼쪽으로 한칸씩 옮기는 문제는 미세먼지 안녕 문제이고, 구슬탈출 종류인데 왼쪽으로 한칸씩 옮기는 문제는 해당문제임. - 2048(Easy)
시뮬레이션처럼 보이는 문제를 풀기 전에, 시뮬레이션을 돌리지 않아도 정답을 찾을 수 있는지 확인하는 게 중요함. - SWEA2805농작물수확하기
함수내부에서 배열을 선언할경우 전부 초기화시켜줘야함. 아니면 쓰레기값. 주변8칸할때 dx,dy값 정확하게 입력하기.
비가 전체내린후에 물복사버그를 진행하는것과 비가 내리는 도중 물복사 버그를 진행시키는 것이 다른것처럼 진행순서 잘확인하기 -> 마법사상어와 비바라기
floor()기호 알아둬야함(아래L).
배열 시뮬레이션 중 한쪽으로 계속 도는 cycle 구현해야함. -> 미세먼지 안녕
굳이 이렇게 어렵게 vector를 매번 생성해주지말고 map[100][100]을 생성해놓고 매번 초기화해서 풀면 훨씬 쉬웠을듯. -> 이차원배열과 연산
시뮬레이션 문제는 빨리풀면서 최대한 구현에 실수가 없도록 하는게 중요한듯. 같은 거리의 적이 많을경우, 가장 왼쪽이라는 조건을 실수해서 오래걸림. -> 캐슬디펜스
3초가 지난 폭탄을 터뜨리는 과정에서 2차원 순차탐색으로 터뜨리면 터뜨리는 과정에서 다른 폭탄이 유실되어 결과값이 달라짐. 따라서 함수내에 임시2차원 배열 설정후, 폭탄을 터뜨리는 과정을 가상화한 뒤, 마지막에 해당 배열을 진짜 배열에 대입함.
시간단위로 진행되는 시뮬레이션은 시간 카운트를 while(true) 문 맨 마지막이 아닌 맨 앞에서 먼저 해주면 생각하기 편함. -> 봄버맨
해당 영역을 찾을 때마다 진짜 배열에 값 계산을 해줘도 다음 번 영역을 찾을 때 영향을 주지 않으면, 바로바로 바꿔주는게 시간복잡도에 효율적임. 처음에 찾았던 영역을 나중에 다시 찾는 것이 비효율적임. -> 인구이동
배열왼쪽과 오른쪽이 연결된 경우는 y인덱스가 음수이면 양수가 될때까지 +N 을 함. - 마법사 상어와 비바라기
vector 합치는 건 result.insert(result.end(),temp.begin(),temp.end()); 처럼 해결하는데, 합치기 전에 result가 합쳐지는 크기가 아니어도 됨. - 드래곤커브
시뮬레이션 문제에서 특정 배열 칸을 이동하는 문제는 방향(dir)과 좌표(x,y)를 뽑아낸 뒤, 배열에서 해당 칸을 일반화시킨 후, 방향과 좌표로 조작함. - SWEA1873상호의배틀필드, 아기상어
특정 배열 칸이 여러 개라도, 좌표로 뽑아내어 좌표로써 이동시켜주는 게, 전체 배열모습을 매번 갱신해주는 것보다 효율적임. - 캐슬디펜스
아기상어의 위치와 같은 시작값을 좌표로 뽑아내어 활용하는 것은 괜찮은데, 장애물이라던가 여러 타겟 위치들을 좌표들로 뽑아내어 List로 관리하는 것은 값을 뽑아내는 것보다 배열값을 변화시킴으로써, 접근하는 게 훨씬 간단할 수 있음. 문제를 보고 더 나은 것을 판단해야 할 듯함. - 아기상어
배열의 세로,가로 크기인 N,M으로 모든 인덱스를 다룰때는 x<N,y<M 인덱스를 다루지만, 특정 인덱스 값으로 모든 인덱스를 다룰때는 x<=sx,y<=sy로 인덱스를 다룸. 매번 실수함. - 미세먼지안녕
무엇을 이분탐색기준으로 잡을것인가 잘생각하기.
이분탐색은 lowerbound, upperbound개념으로 생각해보기.
이분탐색은 답이 여러개일때, 등호를 초과에 넣느냐, 미만에 넣느냐에 따라 도달하는 위치가 달라짐. 여러 답 중 최대값을 원하면 올라가도록 등호를 넣어줘야 최대값에 도달함.
그래프탐색에서 bfs,dfs는 한점에서 특정한 다른점까지 이동할 수 있는지를 탐색하는 용도임. 다익스트라나, 최소스패닝트리는 최소거리를 구하는 용도임. - 중량제한
안될거같으면 애초에 for문에서 거르는게 백트래킹이라고 이해.
set에 vector집어넣을때 순서상관있음.
백트래킹 문제는 for문에서 전부 예외처리 되는 경우도 생각해주어야함. 위문제는 모든 계란이 깨져있어 for문이 생략된 경우, dfs(x+1)이 동작하지 않아 멈춰버림. -> 계란으로계란치기16987
dfs문을 사용할 때, 0,1 반복으로 구현할 수 있으면 그렇게 하는게 편함. 0,1 반복되는 dfs문은 비트마스크 사용하는게 편함. 특정 비트마스크가 다른 비트마스크의 Sub비트마스크인지 확인하려면 해당 문제처럼 해결함. - 후보키
백트래킹 문제를 풀 때, n개중 c개를 고르는 문제인지, n개중 모든 부분집합을 구하는 문제인지 확인해야 함. 전자면, n과m3 방식, 후자면, 비트마스킹으로 해결함. - 부분수열의 합
변칙적인 형태의 백트래킹 구문을 해결할 수 있어야 함. - 계란으로계란치기
배열은 전역변수로 선언될때만, 기본값으로 전체0을 가짐. 지역변수로 선언시, 쓰레기값 들어감. - 연산자끼워넣기
백트래킹의 재귀함수 과정에서 이전에 사용된 값을 알아야 할때, prev 같은 매개변수로 이전값에서 넘겨주는 방법이 유용함. - 줄어드는 수
비트연산의 대상이 되는 0은 2진수의 0으로 처리됨. 비트마스킹의 전형적인 문제임. 26Ck 는 2^26의 시간복잡도를 가짐. - 가르침
재귀함수를 사용해서 dfs를 진행할 때, 시간복잡도가 넘어가는 크기이면 다른 방법을 생각해야함. 해당 문제는 사용가능한 연산자 풀의 개수가 40이상이기 때문에 실제 계산에 필요한 연산자 칸의 개수를 기준으로 재귀함수를 사용해야함. - 연산자끼워넣기2
스도쿠형 백트래킹 문제는 재귀함수의 for문내에 return이 들어갈 수 있음. 현재의 0이 해결되지 못하면 다음으로 넘어가면 안되고, return을 해줘야 함. 재귀함수에서 exit(0) 를 통해 강제종료 가능함. - 스도쿠
if(dfs(nx,ny,limit)) return true;처럼 재귀함수의 조건충족시, 전체 재귀를 완전히 탈출하는 방식을 써야할 때가 있음. 아마 twodots와 서울지하철2호선 문제에서 사용했던 것 같음. - 빵집
백트래킹 과정에서 이전에 왔던 길을 지울 필요가 있는지 확인하는 게 시간 단축에서 중요할 듯함. - 빵집
분명 백트래킹 문제인데, 몇개를 선택하는지 나와있지 않아 범위가 상당할 경우, 문제의 조건으로 몇개를 선택할 수 있도록 주어졌는지 확인하기 - 사다리 조작
이제 시뮬레이션 같은 문제는 2중벡터문으로 구현하지말고 전역배열로 설정하자. index범위만 좁혀서보면 크기가 작아져도 전역배열로 커버가능함. 문제푸는 아이디어부터 주석으로 적어놓은다음 풀자.
점화식을 세울줄 알아야 하는 문제. - 투에모스 문자열
분할정복에서 원하는 타겟 행,열 값으로 빠르게 줄여나가기 위해 4분할에서 원하는 분할쪽으로만 내려갈 수 있음. - Z
특정 List에서 매번 원하는 값을 search해야 하는데 시간이 O(N)걸리지만 loop문 내에 이것이 들어가서 시간초과 문제가 발생한다면,
position Array를 만들어서 position[target] = i처럼 List의 요소에 대한 인덱스를 저장하는 배열을 만들면 O(1)의 시간 밖에 걸리지 않음. List의 search 시간복잡도를 단축하기 위해서 매우매우 유용할 듯한 아이디어임. - 트리의 순회
SWEA 파리잡기 문제처럼 2차원 배열의 특정 영역을 계속 증감하려면 범위에 따라 시간복잡도가 초과할 수 있음. 따라서 누적합 개념을 사용하여 증감해야 할 총량을 미리 계산한 뒤, 마지막에 한번에 더해줌. - 파괴되지않은건물
0/1 정의가능한데 0/0정의안됨, int/int는 double형이 되지 않아 강제형변환필요. erase같은거할때 복사배열쓰는지 꼭확인하기, floor(), ceil() 알아두기, find(vector.begin(),vector,end())로 값찾기 가능,vector find와 string find 다름.
kmp알고리즘 적용방식 익히기.(문자열내에 원하는 문자열찾기) failfunc함수의 vector에서 a[i]의 값은 다음에 같아야할 인덱스임. -> 부분문자열16916
시간문제는 왠만하면 분이나 초로 통일시킨후 해결
문자열 분할할때 마지막 index까지 완전히 처리됐는지 확인하기(ex 배열 끝에 공백추가해야 마지막에 temp에 저장된 내용 사용가능함), next_permutation같은거 돌릴때 원본배열말고 복사배열로 사용해야하는지 꼭 확인하기
stringstream(sstream)을 활용한 공백문자 구분, string.c_str()을 활용한 strtok(https://blockdmask.tistory.com/382) -> 오픈채팅방
1/1000한다고 해서 0.001이 나오려면 형변환 추가적으로 해야함.
집합배열에서 중복되지 않는 값 찾기위해 find(vector.begin(),vector.end())사용 -> 튜플
sort는 같은 경우에는 순서 바꿔주는데 stable_sort는 같은 경우에는 냅둠. 그래서 stable 써야함.
algorithm 라이브러리에 vector나 set이 사용할 수 있는 find, count 함수가 있고, set은 STL로써 스스로 find, count 함수를 가지고 있음.
문자열이 특정 조건을 만족하는 문자열인지 확인할 때, 정규표현식(regex)으로 처리할 수 있는지 확인하기. - 염색체
문자열에서 반복되는 구간을 처리할 때, 찾을 때마다 제거해줘야 하는 문제는 stack을 사용하고, 특수한 처리를 해줘야 하면 char now 를 설정하고 해결함.
ceil,floor,round 함수는 그대로 쓰면 정수범위이고, 소수점 아래 범위를 사용하려면 floor(x*100)/100 처럼 사용하면 됨. transform(str2.begin(),str2.end(),str2.begin(),::tolower)을 통해 전체 string 대소문자 변환 가능함. - 뉴스클러스터링
우선순위 문제는 sort, next_permutation으로 해결가능함. 계산식 문자열 파싱은 정해진 컨벤션대로 하는 게 좋을 듯 함. - 수식최대화
map의 값설정은 전역으로는 안됨. sort는 시간 오래 잡아먹음. 다중 조건 탐색은 해당 문제처럼 해결함. core dumped 발생하면 프로그래머스처럼 디버깅 할수 없는 상황이면 의심가는 부분 주석처리하면서 예외 발생 구간을 직접 찾아내야 함. - 순위 검색
strtok을 활용한 문자열 파싱, 00:00처럼 시간문제는 초나 분으로 환산하여 계산, 조건이 같을 경우 먼저 주어진 값을 반환할때, vector와 sort 활용 대신 max값으로 계산해야 함. 조건이 같은 경우, 기존 상태유지는 stable_sort활용함. - 방금그곡
pair<vector<>,int> 처럼 사용할 경우, vector<> 내에 int를 넣어서 vector<~> 로 단순화할 수 있는지 확인하기 - 파일명정렬
공백파싱, 특정문자파싱은 그냥 전부 strtok으로 해결하기. 기존에는 공백파싱은 stringstream으로 해결해왔음. - 최대값과최소값
strtok을 사용하지 않고, 직접 for문을 통해 문자열 파싱을 해야하는 경우, for문의 마지막 부분을 조심해야 함. - jadencase문자열만들기
펠린드롬 문제는 무조건 재귀함수가 사용되며, 메모이제이션이 필요한 경우 DP문제가 되고, 메모이제이션이 필요없는 경우, 투포인터 문제가 됨. - 회문
플로이드 와샬 : https://chanhuiseok.github.io/posts/algo-50/ / 모든 노드들의 서로 간 최단거리를 한번에 구할 수 있음. 다익스트라를 노드의 개수만큼 실행하면 되긴하는데 시간이 오래걸림.
1차원 배열내 최소이동거리 구하기위한 bfs는 이 방식이 유용할듯함. deque나 priority_queue를 사용하여 가중치가 다른 경우 문제를 해결할 수도 있음. bfs문제에서 가중치가 다르면 다익스트라로 풀어야됨. - 숨바꼭질3
memset은 0,-1말고 다른값으로 초기화불가능함. 방향그래프는 양방향그래프가 아님.
다익스트라랑 최소스패닝트리의 구현방식을 구분할 때, 다익스트라는 pair(-거리,인덱스) 최소는 Edge를 pq의 원소로 사용함. 또한 다익스트라는 첫번째 노드에 대해 dist[i] = 0 을 초기화해주고 pq에 투입하는데, 최소는 check[i] = true 를 초기화해주고 pq에 투입하지 않음.
(0,0)에서 (n-1,n-1)로 이동하기 위한 최소비용경로를 DP로 풀기 위해서는 이동할 수 있는 경우가 오른쪽, 아래, 대각선만 가능해야 함. 사방으로 이동할 수 있으면 DP로 해결 불가능함. bfs에 직접 다익스트라를 적용하는 방법을 사용함. - 녹색옷
일반 최단거리 계산 다익스트라말고 등산코스 정하기 문제와 같이 변형된 다익스트라를 사용할 때는 pq에서 뽑은 가중치가 현재 노드의 가중치보다 작은지 판단해줘야 함. - 등산코스 정하기
선행되어야 하는 작업들이 모두 끝나야(ind==0) 다음 작업을 할수 있고, 선행작업들마다 최소시간이 다름을 확인해야함. -> 작업2056
queue에 똑같은 값이 다시 들어가지 않는다면, check배열을 설정하지 않아도 됨. - 줄세우기
연결그래프인지 비연결그래프인지 알수없는 상황에서 주어진 정점들이 연결되어 있나 확인하기 위해서는 분리집합을 만들어서 모든 Find(i)가 같은지 확인하면 됨.
Union에서는 랭크조절을 위한 weighted union, Find에서는 경로압축을 하여 유니온파인드 속도증가시키기. 유니온파인드의 목적은 분리집합(자료구조)을 만드는 것.
분리집합은 트리를 만든다고 생각. 전역변수로 생성된 배열은 default로 0값 가짐.
분리집합을 할때 Union(x,y)나 Union(y,x)는 차이가 없는듯함.
분리집합에서 parent[x]는 항상 Find(x)가 아님. parent[x]의 값이 다른 집합에 합쳐지면 parent[x]와 Find(x)가 달라짐. - 로봇조립
기존의 분리집합 방식과는 다르게 매번 그룹의 사이즈를 구해줘야함. 원래는 그룹의 사이즈를 구할 때, 전체에서 같은 부모를 가진 노드들의 개수의 합으로 구했는데, 배열의 크기가 너무 커서 이 방법이 안됨. 따라서 group으로 그룹의 사이즈를 매번 갱신함. - 친구네트워크
문제 조건 내 연결 그래프라는 조건은 모든 정점이 연결되어 있다는 뜻이고, 최소 간선을 통해 모든 정점을 방문하라는 말은 MST라는 뜻. MST의 간선의 개수는 정점수-1 임.
pq는 맨 마지막에서 pop()이 일어남. 또한, 그래프가 연결그래프가 아니면 최소스패닝트리가 될 수 없음. - 도시건설
시간복잡도를 해결하기 위해 크루스칼을 사용하고, 그리디적인 해결방법을 알아야 함. 기존 트림방식은 V*E의 시간복잡도를 가지는데, 크루스칼 알고리즘은 ElogE의 시간복잡도를 가짐.- 행성터널
소수찾기 : 에라토스테네스의 체 사용법 -> 소수찾기2, 일반 checkPrime -> 소수찾기 / 소수인지 확인해야 하는 수가 많을 때, 메모이제이션 느낌으로 에라토스테네스의 체를 사용함.
예외처리 : #붙은 알파벳들은 map을 통해 다른 문자로 전환 -> 방금그곡
유클리드 호제법(두 수의 최대공약수 알고리즘, 파라미터의 순서는 상관없음) : -> N개의최소공배수
진수 변환 : -> n진수게임(char배열을 통한 진수변환 사용)
queue를 사용하지 않고 vector로도 해결할수 있는문제는 사용안하는게 좋을듯. -> 캐시
vector를 subvec하려면 copy를 쓰는게 좋을듯.
copy(start,end,temp.begin()) -> end보다 한칸적게 카피되고 temp사이즈는 이미 잡혀있어야함.
while(x--) 형식으로 permutation배열 만들때 x가 음수면 무한대로 진행, 문자열vector sort면 알파벳순
vector의 크기가 고정되지 않았다면, 크기가 다른 vector라도 참조를 바꾸는 것으로 vector swap이 가능함. - 두개의숫자열1959
2차원vector도 크기가 고정되지 않았다면, 크기가 다른 vector로 참조로 바꾸는 것이 가능함. 해당 문제에서 2차원vector 배열을 생성한 뒤, 해당 배열에 2차원vector를 직접 대입해서 넣어줬음. - 숫자배열회전1961