Problem Solving/SW Expert Academy10 그리디 & 완전 탐색 & DP 그리디 마주하는 모든 문제들이 그리디로 풀리는 문제인지 일일이 증명할 수 없으므로 직관 + 판수로 감각을 익혀야겠다. 문제를 푸는 방법이 바로 떠오르지 않을 때 한 번쯤은 혹시 그리디로 풀리나? 하고 의심하는 것도 좋은 방법일 듯. 완전 탐색 개인적으로 문제를 접근함에 있어 가장 우선돼야 하는 방법이라고 생각한다. 완전 탐색으로부터 시작하여 규칙을 찾아내든, dp를 이용하여 연산 횟수를 효과적으로 줄이던지 문제를 이해하기 가장 좋은 접근 방법이다. DP 까다로운 문제가 있었다. state를 나타내기에 필수적으로 필요한 정보들을 잘 생각해봐야겠다. + 같은 상태를 나타내더라도 어떤 정보를 사용하는가에 따라 메모리 크기 차이가 날 수 있다. 잘 고려해주자. P (Polynomial) All decision .. 2022. 1. 21. List & Memory Pool List로 stack, queue(, priority queue)를 구현할 수 있다. Memory pool (PS에 도움이 되는 technique) 예를 들어 Apple이라는 struct의 instance가 최대 100개까지만 필요하다면 (문제에 명시되어 있다면), 필요할 때마다 메모리를 할당했다 지우는 것보다 미리 할당해놓고 계속해서 재사용하자는 것이 memory pool의 핵심. struct Apple { int age; } apple[100]; int apple_idx; void init() { apple_idx = 0; } Apple* make_apple(int age) { apple[apple_idx].age = age; return &apple[apple_idx++]; } int main() .. 2022. 1. 19. Is it necessary to get a bachelor of Computer Science to become a software engineer? 줄곧 생각하던 문제이다. Software engineer가 되기 위해 컴퓨터 과학 전공 학위를 받을 이유가 있는가. 인터넷에는 6개월만 노력하면 (물론 엄청난 노력을 기해야겠지만) 누구나 개발자가 되어 많은 연봉을 받을 수 있다는 글들이 넘쳐난다. 나도 줄곧 이 문제에 스트레스를 받았다. 내가 대학을 왜 다니는 것인지, 전공 공부는 왜 그리 열심히 했는지, 그냥 개발 툴들이나 열심히 익히고 포트폴리오로 보여줄 수 있는 프로젝트들이나 할 것이지. 하지만 정보올림피아드 위원장이시자 건국대학교에서 교수로 재직중이신 김성렬 교수님은 조금 다른 이야기를 하셨다. 기초, 즉 알고리즘적 사고를 할수 있는가가 개발자들에게 있어 가장 중요하다는 이야기를 해주셨다. 그리고 그 사고를 배우기 위해 4년동안 대학을 다니는 것.. 2022. 1. 18. Bit operation & Bit mask Bit operation을 이용해 다른 변수 선언 없이 swap 하는 방법 void swap(int *a, int *b) { *a ^= *b; *b ^= *a; *a ^= *b; } 비트를 이용하여 쉽게 set을 나타낼 수 있다. i번째 원소가 set에 포함되어 있는지 확인하려면 set을 의미하는 값의 i번째 bit이 켜져 있는지를 확인하는 것이다. int나 long long 등의 자료형들이 가질 수 있는 bit 개수를 고려하고 구현하면 된다. 응용으로는 bit mask + dp 문제가 있다. 아주 강력한 방법이지만 자료형의 크기 때문에 가질 수 있는 상태가 제한된다. array 형태로 만들면 확장 가능할 듯. (쓸 일이 있을까?) int array[10]; /* array[0]: 0번부터 31번 원소까.. 2022. 1. 18. 이전 1 2 3 다음
