ORTHODOX

안녕하세요 오늘은 스택을 이용하면 정말정말 간단하게 풀리는 문제를 풀어보도록 하겠습니다. 전략: 1. 스택을 선언해주고 K번 반복하는 for문을 만들어서 만약 0이 들어왔으면 스택의 가장 위를 지우고, 그게 아니라면 넣어준다. 2. 스택 사이즈로 si라는 변수를 선언해주고, si만큼 반복하는 for문에서 result에 스택의 가장 위를 더해주고, pop으로 그 숫자를 스택에서 뺀다. 코드: #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long result = 0; int K; cin>>K; stack s; for(int i = 0; i>x; if(x==0){ s.pop(); }..

안녕하세요 오늘은 stack을 이용하여 문제를 풀어보도록 하겠습니다. 전략: 1. char 타입으로 stack을 선언해줍니다. 2. 모든 입력을 getline으로 받아서 한줄씩 받을 수 있도록 한다. 만약 들어온 입력이 "."이면 while문을 끝낸다. 3. 들어온 문자열의 길이만큼 반복하는 for문을 만들어서 각 문자가 '('인지, '['인지등등 판단한다. 4. 만약 (이거나 [이면 stack에 push해주고, 만약 )이면 stack이 비어있는지 확인하고, 또는 stack의 맨 위가 (이면 bool타입의 result에 false를 대입해주고, for문을 break 해준다. 그게 아니라면 result에 true를 대입하고 stack의 맨 위를 pop으로 없앤다. ]도 마찬가지로 처리해준다. 코드: #in..

안녕하세요 오늘은 이분탐색을 이용한 문제를 풀어볼 것입니다. 전략: 1. long long int type으로 vector를 선언해줍주고 입력을 받는다. 2. l(low)를 1로, h(high)를 vector의 최댓값으로 선언해주고, while문을 만든다. 3. while문이 시작되자마자 l가 h보다 크면 while문이 끝나도록 코드를 짜고, long long int타입의 mid라는 변수를 들어서 l, h의 평균을 입력해준다. 4. 나무를 자른 길이를 cnt에 더해주고, cnt가 M보다 크면 max변수와 mid를 비교하여 더 큰 값을 max에 넣어준다. 코드: #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); co..

안녕하세요 오늘은 스택을 이용하여 스택 수열이라는 문제를 풀어보도록 하겠습니다. 전략: 1. int 타입의 스택 s, string타입의 변수 result를 선언해준다. 2. 입력받은 n번만큼 반복하게 while문을 설정해주고 각 반복마다 x변수를 받아준다. 3. while(n--) 전에 cnt변수를 1로 선언해준다. 그 뒤, while(cnt>n; stack s; string result = ""; int cnt = 1; while(n--){ int x; cin>>x; while(cnt

안녕하세요 오늘은 이분탐색, 매개변수 탐색 알고리즘을 이용하여 풀어야하는 문제를 풀어보겠습니다. 전략: 1. 벡터에 랜선의 길이를 대입하고 sort를 해줍니다. 이때 sort해서 가장 뒤에 있는 원소가 max 변수에 대입됩니다. 2. 매개변수로 l(left), r(right)를 선언해줍니다. l은 1, r은 max로 선언해줍니다. 3. 갖고있는 랜선의 개수를 mid로 나눈 몫의 총합이 K보다 크거나 같으면 result와 sum을 비교해서 더 큰 값을 result에다가 대입해줍니다. 그리고, l = mid+1을 해줍니다. 4. 만약 아니라면 r = mid-1을 해준뒤, 만약 l>r이면 break하도록 if문을 설정해줍니다. 코드: #include #include using namespace std; int..

안녕하세요 오늘은 해시함수를 구현해야하는 문제를 풀어보겠습니다. 전략: 1. const int 타입을 통해 MOD, MUL 상수를 선언해준다. 2. string 타입의 문자를 선언하고 반복문과 -96을 통해 알파벳 숫자를 구해준다. 3. 문제에 나와있는 대로 더하고 나눈 나머지를 sum에 대입한다. 코드: #include using namespace std; const int MOD = 1234567891; const int MUL = 31; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N; long long int sum = 0; cin>>N; string M; cin>>M; long long R = 1; for(int i= 0; i

안녕하세요 오늘은 스택을 이용해서 간단하게 문제를 풀어보겠습니다. 전략: 1. 한 글자씩 비교할 것이므로 char타입을 stack을 선언해준다. 2. 만약 스택의 제일 위가 ')'이면 count++, s.pop()을 해주고, 그게 아니라면 count--, s.pop()을 해줌으로 count가 음수가 되면 실행이 끝내게 한다. 3. 만약 (, )짝이 맞는다면 count는 결론적으로 0이 될 것이므로 만약 0이면 YES를 출력하고 그것이 아니면 NO를 출력한다. 코드: #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cin>>T; for(int i= 0; i>N; int len =..

안녕하세요 오늘은 큐를 이용하여 간단하게 문제를 풀어보겠습니다. 이 문제에서 큐를 사용해야 하는 이유는 첫 줄에 있습니다. N명의 사람이 '원'을 이루면서 앉아있다고 했습니다. 그래서 K번째 사람을 셀 때, q.push(a.front), q.pop을 k-1번 반복한다음, q.pop을 하면 구현이 됩니다. 전략: 1. queue를 선언해주고, 1부터 N까지 자연수들을 q.push()함수를 통해 대입해준다. 2. while 문에 0~k-2까지 반복하는 for문을 만들어 q.push(q.front()), q.pop()을 통해 앞에 있는 숫자를 뒤로 보내주고, q.front()를 출력해준다. 코드: #include using namespace std; int main(){ ios::sync_with_stdio(..

안녕하세요 오늘은 동적 계획법(다이나믹 프로그래밍)을 이용한 문제를 풀어보겠습니다. 역시 동적계획법 문제는 점화식이 많은 것 같습니다. 이 문제는 w(a, b, c)인 변수가 3개가 필요한 함수이므로 피보나치 풀이와는 다르게 '3'차원 배열을 만들어서 풀겠습니다. 전략: 1. 3차원 배열 arr를 각각 101의 크기로 선언한다.(주어진 범위가 -50~50이기 때문) 2. int w(int a, int b, int c) 함수를 선언한다. 이 함수는 처음 하는 행동이 x = a+50, y = b+ 50, z = c+50을 해준 다음, 만약 arr[x][y][z]가 있으면 계산 할 필요 없이 바로 return해준다. 이부분이 동적 계획법이라고 할 수 있는 부분일 것이다. 3.그 외에는 문제에서 주어진 함수와 ..

안녕하세요 오늘은 이분탐색으로 풀면 빨리 풀리는 문제를 풀어보겠습니다. (다른 방식으로 푼 저는 엄청난 메모리와 시간을 맛봤지요 맞긴했지만..) 두가지 방법으로 문제를 풀어보겠습니다만, 2번째 방법을 추천드립니다. 전략1 1. 범위를 확인한 후, 20000001길이의 벡터를 선언해준다(어레이로 선언하면 배열 길이 제한때문에 안된다) 2. x+= 10000000을 해준후, x+1번째 배열의 원소 값에 1을 더해준다. 3. 2번째 입력때 x+= 10000000을 해준다음 그 위치에 있는 원소값을 출력한다. 코드1(내가 한 번에 풀었던 방식): #include #include using namespace std; int main(){ vector arr(20000001); ios::sync_with_stdio..