안 쓰던 블로그

스택이란 ‘쌓아올린 더미’를 말합니다. 책을 쌓아서 탑을 만들면 스택이고, 편의점 냉장고에 캔음료수가 일렬로 줄 서 있는 것도 스택입니다. 이렇듯 스택은 마지막으로 들어온 것부터 나가는 특징을 가지고 있습니다. 책 탑에서 맨 아래 책을 빼면 무너지고, 편의점에서 음료수를 앞에서부터 빼지 못 하는 점을 생각하면 됩니다. 그런 현실의 개념을 추상화한 것이 바로 스택입니다. 스택을 가지고 주로 삽입, 삭제, 검색 작업을 하는데, 스택의 특징에 따라 가장 최근에 들어온 데이터를 빼고, 아니면 그 뒤에 새로운 데이터를 넣게 됩니다. 스택의 특징을 영어로는 LIFO(Last In First Out), 한자로는 후입선출이라 합니다. 여기서 중요한 건, 편의점의 캔음료를 중간에 있는 것부터 뺄 수 없듯 이 스택에서도 ..

자주 쓰는 비트연산 정리 (feat. 펜윅트리) (1

https://www.acmicpc.net/blog/view/88 펜윅 트리 200% 활용하기 흔히 lazy propagation을 사용하여 푸는 것으로 알려진 이 두 문제는 사실 펜윅 트리만으로 풀 수 있습니다. 구간 덧셈, 포인트 쿼리 다음 연산을 효율적으로 수행하는 자료구조를 만들어 봅시다. 이것으로 16975번 - 수열과 쿼리 21을 풀 수 있습니다. $A_L$, $A_{L+1}$, $\cdots$, $A_R$에 각각 x씩 더한다. $A_k$를 출력한다. $B_1 = A_1$, $B_k = A_k - A_{k-1}$이라고 두면, 각각의 쿼리 www.acmicpc.net https://blog.naver.com/jh05013/221475142152 BOJ 16975부터 16979까지 16975 수열..

단순 구현 어떤 알고리즘을 써서 문제를 풀 때도 구현이라고 하지만 여기서는 말 그대로 '문제를 읽고, 문제 자체를 구현'하는 단순 구현 문제를 의미합니다 단순 구현 문제는 보통 문제에 답이 있는 경우가 많으며, 문제를 읽고 가장 단순하게 생각해서 푸는 문제들도 단순 구현에 속합니다. 이렇게 단순 구현 문제들을 풀어둔다면 나중에 더 어려운 문제를 접하더라도, 문제를 단순하게 푸는 방법을 생각한다->시간이나 메모리를 더 줄일려면 어떻게 해야되지? 어떤 알고리즘을 써야되지? 이런 식으로 생각을 넓혀갈 수 있습니다. 단순 구현 문제는 간단히 풀리는 경우가 많으므로 문제풀이 공부에 회의감이 들거나 자존감이 낮아졌을 때, 재미로 풀면서 다시 공부하고자 하는 의지를 충전 할 수 있습니다. 먼저 문제만 보고 풀어본다-..

음수를 나머지 연산하려면 어떻게 해야 할까요? 질문에 앞에 먼저 음수 나눗셈을 해봅시다. 10/-2를 한다고 했을 때, 10/-2는 ‘-2를 몇 번 더해야(빼야) 10이 나올까?’와 같은 의미입니다. 10은 -(-2) -(-2) -(-2) -(-2) -(-2) 라고 쓸 수 있는데, 횟수로는 5번이지만 -2를 더하면 안 되고 빼야 되기 때문에 10/-2는 -5입니다. 같은 의미로 10=-2*-5도 ‘10은 -2를 -5번 더한(뺀) 수다’라고 할 수 있겠네요. 그러면 이제 나머지를 구해봅시다. 7/-3의 몫은 -2입니다. 그러면 나머지는? -(-3)-(-3)을 한 뒤 남은 수는 1이니까 나머지는 1입니다. -7/-3은 어떻게 나올까요? -7을 만들기 위해서는 -3-3-3을 해야 합니다. 몫은 3이고 -9가 ..

수학 수학2에서는 수학1에서 다뤘던 내용을 기반으로 조금 더 응용하는 문제를 다뤄보겠습니다. 수학1 게시글(https://foxtrotin.tistory.com/95)을 보고 오면 도움이 되실 겁니다. 1. 나머지 연산 나머지 연산을 쓰는 유형에는 몇 가지가 있습니다. 나머지의 값이 필요할 때, 특정 수의 배수인지 판별, 짝수인지 홀수인지 판별, 몇 개의 수를 계속 돌리고 싶을 때, 너무 큰 수가 정답일 때 나머지 연산 후 정답을 출력할 때 등등.. 여기서는 몇 개의 수를 계속 돌리고 싶은 경우 어떻게 해야 하는지 알아보겠습니다. #include int main(){ int a[3] = { 1,2,3 }; for (int i = 0; i < 6; i++) { printf("%d ", a[i % 3]); ..

수학 입출력 글(https://foxtrotin.tistory.com/90)에서 알고리즘 문제풀이의 과정을 (1)문제를 읽고 (2)입력을 받아서 (3)계산하고 (4)결과를 출력한다 라고 했었습니다. 하지만 엄밀히 따지면 이 과정은 전체 과정 중 ‘구현’ 부분에 해당합니다. 그러면 ‘구현’ 이전에 해야 하는 과정은 또 뭐가 있을까요? 바로 문제를 해결할 방법을 생각하는 것입니다. 위에 네 단계에서는 (1)과 (2) 사이에 들어가는 과정이겠네요. 아무리 뛰어난 코딩 실력이 있어도 어떻게 풀지 모른다면 코딩 실력은 무의미해질 것입니다. 그래서 ‘문제 해결 능력’이 보통 문제 풀이에서 가장 중요한 능력으로 여겨집니다. 이번 주에는 우리가 잘 알고 있는 수학 몇 가지를 다루면서 문제를 어떻게 해결하는지, 어떻게 ..