알고리즘 썸네일형 리스트형 알고리즘 코딩기법 - 8. 쉬어가기 안녕하세요. 17-2기 조일룡입니다. 기말고사 시험기간인데 다들 공부 잘 하고 계신지 모르겠네요. 저는 이번 기말고사 션하게 말아먹을 것 같습니다. ㅠ 기말고사 시즌인 관계로 이번 블로그는 머리를 식힐겸 퍼즐을 하나 준비했습니다. 이건 18-2기 여러분들 들어오셨을 때 집중세미나 시간에 했던거 재탕인데요.. 뭐 뒷북이지만 괜찮겠지여 ㅋㅋ 지뢰찾기 퍼즐 지뢰찾기는 다 해보셨으리라 생각되므로 자세한 설명은 생략하겠습니다. 위의 지뢰판에서 숫자는 자기과 양옆의 칸에 있는 지뢰의 수를 알려줍니다. 한 칸에는 최대 하나의 지뢰만이 있을 수 있습니다. 그렇다면 위의 그림에는 몇 개의 지뢰가 있을까요? 지뢰찾기 고수분들은 그림 대충 보고 지뢰가 어디에 있는지 금방 찾으실거라 생각되는데여 사실 지뢰찾기 한 번도 해보지.. 더보기 알고리즘 코딩기법 - 7. Bit 연산 Brute Force 안녕하세요 조일룡입니다. 이번에는 2진수를 이용하여 모든 경우의 수를 탐색하는 Brute Force에 대해 알아보겠습니다. Brute Force Brute Force는 문제를 해결할 수 있을지도 모를 모든 후보 해를 전부다 탐색하여 정말로 문제를 풀 수 있는 해를 찾는 방법입니다. 쉽게 생각해서 문제가 1 + x = 100 인 경우 이 문제의 해 x가 [0, 100] 사이의 자연수라는 것을 안다고 가정했을 때 단순히 x에 0부터 100까지 모두 대입해 보고 문제가 풀리는 x값을 찾는식의 방법입니다. 물론 저 문제를 저렇게 푸는 바보는 없어야 하겠죠? 여튼 위의 '예' 처럼 Brute Force는 해법이 간단하고 쉬운 반면 모든 후보해를 탐색해야하기 때문에 상당히 느리다라는 단점이 있습니다. 그럼에도 Br.. 더보기 알고리즘 코딩기법 - 6. 상태를 나타내는 값싼 방법(bits) 안녕하세요 17기 조일룡입니다. 이번 포스팅에서는 2진수를 사용하여 상태를 나타내는 기법에 대해서 살펴보겠습니다. 많은 경우에 어떤 상태는 Yes나 No로 나타낼 수 있습니다. 예를 들면 쟁반위에 사과가 있냐/없냐 와 같은 상태가 있을 수 이겠네요. 초기에 쟁반위에 사과, 배, 참외, 수박, 포도가 있었는데 누군가 과일을 먹어서 어떤 것은 없어졌습니다. 이때 가능한 상태는 모두 32(=2^5)가지가 됩니다. 프로그램을 작성하면서 위와 같은 상태를 나타내야 하는 경우는 종종 발생합니다. 그리고 어떻게든 나타내게 되겠지요.. 각각의 과일마다 boolean type의 변수를 하나식 만들 수도 있고 좀 더 똑똑한 누군가는 boolean type의 배열을 선언할 수도 있습니다. 오늘 포스팅에서는 bit를 이용하여.. 더보기 알고리즘 코딩기법 - 5. STL 안녕하세요 조일룡입니다. 오늘은 C++에서 표준 라이브러리로 채택된 STL에 대해 간략하게 알아보겠습니다. STL은 Standard Template Library의 약자로 템플릿을 이용한 표준 라이브러리.. 뭐 이정도의 의미를 가지고 있습니다. 아래의 주소에서 STL에 대한 모든것을 알 수 있습니다. http://www.cplusplus.com/reference/stl/ 이번 포스팅에서는 템플릿에대해 잠깐 짚어보고, STL에서 제공하는 컨테이너 중 가장 흔히 사용하는 'vector'에 대해 알아보겠습니다. Template 템플릿을 건너뛰고 싶었지만 역시 언급을 해야할 것 같습니다. 템플릿은 컴파일타임에 자료형을 확정하여 그 자료형에 맞는 코드를 생성하는 C++에서 제공하는 기능입니다. 두개의 정수형 변수.. 더보기 알고리즘 코딩기법 - 4. 바이너리서치 안녕하세요. 오늘은 바이너리서치(Binary Search) 의 코딩법에 대해서 알아보겠습니다. 숫자맞추기 참이슬을 까고나면 병뚜껑을 꼬은 다음에 손가락으로 쳐서 끊어지면 그 전사람이 벌주를 마시는 게임이 있죠?? 그리고 나서 벌주를 마신 사람은 병뚜껑에 있는 숫자를 보고 업&다운을 해서 그 숫자를 부른 사람이 또 벌주를 마십니다. (이거 우리 학교만 하나요?) 혹시나 모르시는 분이 있을까봐 부가 설명을 드리겠습니다. 참이슬 병뚜껑에는 [1, 50] 사이의 숫자가 찍혀있습니다. 한사람씩 숫자를 부르면 정답을 아는 사람이 정답에 지금 부른 숫자보다 큰지 작은지를 알려줍니다. 그 다음 사람은 좁혀진 범위 내에서 숫자를 다시 부릅니다. 그럼 범위가 점점 좁혀지고 누군가 숫자를 맞추게 되는데 그 사람이 벌주를 마.. 더보기 알고리즘 코딩기법 - 3. 재귀호출 안녕하세요.. 저번 포스팅에서 예고해드린데로 이번에는 재귀호출에 대해서 다뤄볼까합니다. 물론 멤버십에 계신분들중에 재귀호출을 어려워 하실 분들은 없으리라 생각하는데요, 학교에서 주위를 살펴보면 재귀호출을 잘 못하는 친구나, 후배나, 등등 많은 것 같습니다. 그 만큼 재귀호출이 직관적으로 이해가 잘 안되는 부분인가 봅니다. C++과 싸우다 보면 포인터에서 한 번 좌절을 하게 되고 포인터를 넘고나면 재귀호출이 또다시 태클을 건다는.. 뭐 그런 전설이 내려오는데요.. 저도 지금 재귀호출을 어떻게 다뤄야할지 막막합니다 ㅠㅠ 뭐.. 어쨌든..... 각설하고 시작하겠습니다. 재귀(Recursion) 주어진 문제를 재귀적으로 푼다는 말은 문제의 답이 그 문제와 동일한 형태의 더 작은 부분문제(sub problem)의.. 더보기 알고리즘 코딩기법 - 2. 차수 안녕하세요. 이번에는 지난 포스팅에 이어 알고리즘의 차수에 대해서 알아보겠습니다. 지난글의 마지막에 이번시간부터는 본격적으로 코딩기법에 대해서 포스팅하겠다고 했는데 생각을 해보니 일단 차수에 대해서는 언급을 하고 넘어가야 할 것 같아서 순서를 바꿨습니다 ^^ 알고리즘의 분석 알고리즘이 문제를 얼마나 효과적으로 해결하는지를 결정하기 위하여 알고리즘을 분석할 필요가 있습니다. '알고리즘 코딩기법 1 - Introduction' 에서 소개했던 순차검색과 이분검색의 비교가 바로 알고리즘의 분석이라고 할 수 있고 분석결과 n이 커질수록 이분검색이 유리하다고 결론을 내렸었는데요, 이번 파트에서는 알고리즘의 분석에 대해서 좀 더 자세히 알아보겠습니다. 복잡도 분석(complexity analysis) 시간을 기준으로.. 더보기 알고리즘 코딩기법 - 1. Introduction 안녕하세요 SSM17.2기 (17-2기 라고 해야 맞는건가요?) 조일룡입니다. 온라인 개인형 맞춥시그 - 가칭 주제없는 시그 - 에서 제가 맡은 주제는 '알고리즘 코딩기법' 입니다. 주제는 뭐 저렇구요.. 코딩 얘기만 하는 것이 아니라 이것 저것 다양한 주제로 포스팅을 해 볼까 합니다. 주로 참고할 레퍼런스로는... The Art of Computer Programming / Donald E. Knuth (ISBN:9788979144307) Introduction to Algorithm / Cormen (ISBN:9788979143171) 생각하는 프로그래밍 / Jon Bentley (ISBN:9788995300930) 와 각종 인터넷을 참고하겠습니다. 우선 오늘은 첫 포스팅이니 만큼 가벼운 주제로 시작.. 더보기 이전 1 다음
