백준 사이트에 있는 구현 문제는, 대다수가 브루트 포스로 풀리는 경우가 많습니다. 코딩 테스트를 준비하시는 분들도 적지 않으실 거 같은데요. 그것들을 잘 풀기 위해서, 이론적인 지식 3~4편 정도만 올리고, 실전에 들어가도록 하겠습니다. 백트래킹 탐색은, 다음과 같은 알고리즘으로 동작합니다. 뭔가 복잡해 보이는데요. 제일 중요한 부분은, (1)번과 (3)번, (5)번이라고 할 수 있어요. 이 셋만 잘 작성하면 끝났다고 볼 수 있어요. 그런데, 아직 이해가 안 가는 부분이 많습니다. 들어올 수 있는 상태들은 대체 무엇을 의미할까요? 예를 들어, 스토쿠를 생각해 봅시다. 빈칸에 숫자를 넣어야 할 때, 1부터 9까지만 넣을 수 있어요. 즉, 우리가 빈 칸에 넣을 수 있는 숫자들의 집합은 {1, ... , 9}..
분류 전체보기 검색 결과
오늘은 ps에 심심하면 많이 등장하는 '문자열을 숫자로 바꾸는' 함수에 대해서 알아보도록 하겠습니다. 이건 구현 문제를 풀다 보면, 정말 심심하면 하나씩 툭 튀어나옵니다. 보통 저는 sscanf로 문자열을 숫자로 convert를 하고, 역변환을 할 때에는 sprintf를 쓰는 편입니다. 그런데 사실, atoi 정도는 알아두셔도 크게 나쁘지는 않을 듯 싶네요. int atoi(const char *pat); pat을 받아서, 숫자로 변환을 해 줍니다. 당연하게도 변환을 할 수 없는 경우에는 0이 리턴이 되는데요. "0"을 atoi한 결과와 구분이 되지 않기 때문에 주의해야 합니다. 기본 예제를 보도록 하겠습니다. 7번째 줄에, 두 개의 문자열을 입력받았습니다. 각각 "-27"와 "3"을 입력했습니다. 그 ..
오늘은, 간단하게 지역변수에 대해서 알아보도록 하겠습니다. 그 전에, 변수를 visible 할 수 있는 범위, 즉 scope하고, life time에 대해서 집중적으로 보도록 합시다. 8번째 줄에 정의된 t는 어디에 선언이 되었나요? foo 라는 함수 내부에 정의가 되었습니다. block 내부나, 프로그램 단위 (함수)에 정의된 변수들을 지역 변수라고 부릅니다. 그러면, 이것이 어떠한 특징을 가지는지, 위에 있는 코드를 한 번 실행해 봅시다. 결과가 0이 나오는데요. 차근 차근 설명해 보겠습니다. 먼저, 4번째 줄의 int t = 0; 이라는 문장을 실행하면, 변수 t에 0이 대입이 됩니다. 그러면 이렇게 상황을 그릴 수 있습니다. 다음에, foo(t)를 호출하게 되는데요. 6번째 줄에 보면 매개변수 a..
고급 자료구조 이론에 들어가기 전에, 복습 겸 코딩 테스트에 자주 나오는 LRU 알고리즘을 간단하게 구현해 보도록 하겠습니다. 어떠한 페이지를 찾아야 한다고 해 봅시다. 메모리에서. 그런데, 그 페이지가 없어요. p라는 페이지가. 이 때, 메모리에서 어떤 페이지를 제거해야 할까요? 가장 오래 전에 사용이 된 것을 제거하는 것을 LRU 알고리즘이라고 합니다. 약어로는 Least Recently Used한 것을 제거하는 것이죠. 보통, 이러한 문제를 만났을 때, 저는 map 2개로 많이 코딩하라고 이야기를 합니다. 그런데, STL을 쓸 수 없는 환경에서는 어떻게 해야 할까요? 코딩하기도 어려운 레드 블랙 트리를 500줄 가까이 작성해야 할까요? 아니면 포인터의 향연에서 벗어날 수 없는 skip list를 작..
strcat 함수는 문자열을 이어 붙이는 함수입니다. char *str(char *dest, const char *ori); dest에 ori를 붙입니다. 어렵지 않네요? 먼저 시간 복잡도 먼저 분석해 보도록 합시다. 보통, string 뒤에 붙이는 것은, O(|ori|)인 경우가 많기는 해요. 끝 위치만 알고 있다면, 그 위치에서부터 뒤로 붙여버리면 되거든요. 단, 공간이 충분하다는 전제 하에서요. 물론, Java의 StringBuffer나 StringBuilder 같은 경우에는, 크기가 변할 수 있는, 동적 배열이긴 합니다. 그러니, 공간이 부족하다 싶으면 expand를 호출을 할 거고요. 그러면, 이 친구는 어떻게 동작할까요? 끝 위치를 저장하고 있을까요? 이 코드는 단순합니다. str에 계속 "a..
최근댓글