#. 문제 https://algospot.com/judge/problem/read/PICNIC#* 이 문제의 저작권은 Algospot에 있습니다. [ 문제 ]안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다. 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다..
#. 문제 https://algospot.com/judge/problem/read/BOGGLE* 이 문제의 저작권은 Algospot에 있습니다. 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다. 예를 들어 그림의 (b), (c), (d)는 각각 (a)의 격자에서 PRETTY, GIRL, REPEAT을 찾아낸 결과를 보여줍니다. 보글 게임판과 알고 있는 단어들의..
#. 재귀 호출 ㅇ 재귀 호출(=재귀 함수) recursion(=recursive function) - 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수 - 다양한 알고리즘을 구현하는데 매우 유용하게 사용할 수 있는 도구 - 문제의 특성에 따라 재귀 호출은 코딩을 헐씬 간편하게 해 줄 수 있는 강력한 무기 - 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성 - 완전 탐색을 구현할 때 아주 유용한 도구 ㅇ 완전 탐색으로 해결하기 위해 필요한 과정 1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수가 정확히 비례 - 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두..
참고글 : [Algorithm] 알고리즘 시간 복잡도 분석 #. 프로그램 수행 시간 짐작하기 ㅇ 시간 복잡도의 분할 상환 분석(amoritzed analysis) - 알고리즘의 시간 복잡도를 항상 반복문의 개수를 세는 것만으로 경정하지 않음 - 가끔은 문제의 조건에 따라 그보다 더 정확한 시간 복잡도 계산 가능 ㅇ 수행 시간 짐작하기 - 프로그램을 작성하기 전 입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간을 어림짐작할 수 있어야 함 - 하지만, 프로그램의 동작 속도에 영향을 끼치는 요소는 엄청나게 많음.. - 그러나, 많은 경우 시간 복잡도와 입력 크기만 알고 있더라도 어떤 알고리즘이 시간 안에 동작할지 대략적으로 짐작 가능 ㅇ 수행 시간 짐작을 위한 주먹구구 법칙 - "입력의 크기를 시간..
[Algorithm] 알고리즘 시간 복잡도 분석
참고글 : [Algorithm] 프로그램 수행 시간 짐작하기 #. 알고리즘 ㅇ 알고리즘 - 어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법 - 주관적이거나 모호한 것은 알고리즘이라고 할 수 없음 ㅇ 알고리즘이 사용하는 시간과 공간 - 시간 : 알고리즘이 적은 시간을 사용한다는 것은 더 빠르게 동작한다는 이야기 - 공간 : 알고리즘이 적은 공간을 사용한다는 것은 더 적은 용량의 메모리를 사용한다는 이야기 ㅇ 알고리즘 시간 분석도 분석 - 프로그램의 실행 시간을 알고리즘의 속도를 일반적으로 이야기하는 기준이 되기에는 부적합 - 이유 1. 프로그램의 수행 시간은 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러까지 수많은 요소에 의해 바뀔 수 있음 - 이유 2. 프로그램의 실제 수행 시간이 다..
#. 좋은 코드를 작성하기 위한 원칙 ㅇ 간결한 코드 작성하기 - 가장 간결한 코드, 읽기 쉬운 코드 작성 ㅇ 적극적으로 코드 재사용하기 - 코드의 모듈화 - 코드가 세 번 이상 등장한다면 항상 해당 코드를 함수로 분리해 재사용한다는 기본 원칙을 세우기 - 항상 코드를 깔끔하게 작성하고 유지하는 데 신경을 써보기 - 간결한 코드가 디버깅 시간에 엄청난 차이를 가져다 줌 - 이상적인 세계에서는 한 함수가 두 가지 이상의 일을 해서는 안 된다고 말함 ㅇ 표준 라이브러리 공부하기 - 표준 라이브러리의 사용 - 언어의 문자열, 동적 배열, 스택, 큐, 리슽, 딕셔너리 등의 자료 구조, 정렬 등의 표준 알고리즘 구현 사용법을 반드시 잘 알아 두기 ㅇ 항상 같은 형태로 프로그램 작성하기 ㅇ 일관적이고 명료한 명명법..
#. 프로그래밍 문제 해결 과정 ㅇ 문제 해결 과정 1. 문제를 읽고 이해하기 - 문제 설명을 공격적으로 읽으며 문제가 원하는 바를 완전히 이해하는 과정이 반드시 필요 2. 문제를 익숙한 용어로 재정의하기 + 추상화 - 자신이 다루기 쉬운 개념을 이용하여 문제를 자신의 언어로 풀어 쓰는 단계 - 본질만 남겨두고 축약하여 다루기 쉽게 표현 -> 추상화 - 어떤 부분을 추상화할 것인지를 선택하는 작업과 문제를 재정의하는 방법들에 대한 고찰은 좋은 프로그래머가 되기 위해 필수적인 과정 3. 어떻게 해결할지 계획 세우기 - 문제를 어떤 방식으로 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택 - 문제 해결에서 가장 중요한 단계 4. 계획 검증하기 - 설계한 알고리즘이 모든 경우에 요구 조건을 정확히 수행하..
#. 국내,외 프로그래밍 대회 ㅇ 한국 정보 올림피아드 (https://koi.or.kr/) - 초,중,고 학생 대상 - 대개 4시간 동안 3개의 문제에 대해 답안 코드를 작성 ㅇ ACM-ICPC (ACM 대학생 프로그래밍 경시대회) (http://icpckorea.org/) - 대학생 대상 - 3명의 학생이 팀을 이뤄 한 대의 컴퓨터로 문제 풀이 - 5시간 동안 8~10 문제 ㅇ 탑코더(TopCoder) - 알고리즘 트랙 (https://www.topcoder.com/) - 1~2주 간격으로 온라인 대회 개최 - 1시간 15분 동안 3개의 문제 풀이 ㅇ 구글 코드 잼 (https://codingcompetitions.withgoogle.com/codejam) - 자신이 원하는 언어를 자유롭게 사용 가능..