코딩

8 동적 계획법 8.1 도입 동적 계획법(dynamic programming)이라는 말은 최적화 문제를 연구하는 수학 이론에서 왔으며, 우리가 전산학 전반에서 일반적으로 사용하는 동적(dynamic), 혹은 프로그래밍(programming)이라는 단어와는 아무런 관련이 없다. 중복되는 부분 문제 동적 계획법은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 동적 계획법을 사용하는 알고리즘들 또한 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문이다. 동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식이다. 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에, 이 문제의 ..

2.1 중복 없애기 정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라. 연결리스트에서 중복되는 원소를 제거하기 위해서는 원소를 추적할 수 있어야 한다. 여기서는 해시 테이블을 사용해서 처리한다. 연결리스트를 순회하며 각 원소를 해시 테이블에 저장한다. 그러다가 중복된 원소를 발견하면, 그 원소를 제거한 후 계속 진행한다. void deleteDups(LinkedListNode n) { HashSet set = new HashSet(); LinkedListNode previous = null; while (n != null) { if (set.contains(n.data)) { previous.next = n.next; } else { set.add(n.d..

1.1 중복이 없는가? 문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라. 문자열은 ASCII 문자열임을 가정하자. 문자 집합은 boolean 타입의 배열로 만들어서 i 번째 원소는 문자열에 해당 인덱스의 문자가 존재하는지를 확인한다. 배열의 길이는 128이 아니라 256이 되어도 괜찮다. boolean isUniqueChars(String str) { if (str.length() > 128) return false; boolean[] charSet = new boolean[128]; for (int i = 0; i < str.length(); i++) { int val = str.cha..

7 분할 정복 7.1 분할 정복 분할 정복(Divide & Conquer)은 가장 유명한 알고리즘 디자인 패러다임으로, 각개 격파라는 말로 간단히 설명할 수 있다. 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다. 이 차이점이 아래 그림이다. 그림 (a)는 항상 문제를 한 조각과 나머지로 쪼개는 일반적인 재귀 호출 알고리즘을 보여주고, 그림 (b)는 항상 문제를 절반씩으로 나누는 분할 정복 알고리즘을 보여준다. 분할 정복을 ..

06 무식하게 풀기 6.1 도입 흔히 전산학에서 무식하게 푼다(brute-force)는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전탐색(exhaustive search)이라고 부른다. 얼핏 보면 이런 것을 언급할 가치가 있나 싶을 정도로 간단한 방법이지만, 완전탐색은 사실 컴퓨터의 장점을 가장 잘 이용하는 방법이다. 컴퓨터의 최대 장점은 속도가 빠르다는 것이기 때문이다. 6.2 재귀 호출과 완전 탐색 재귀 호출 재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다. 예를 들면 ..

오늘은 패스트캠퍼스에서 최근에 수강했던 김태곤님의 강의를 듣고 학습했던 내용을 정리해 보려고 한다. 시작하기에 앞서서 이 강의는 패캠에서 어떠한 대가도 제공받지 않고 직접 수강하고 내용을 정리하는 것임을 밝힌다. 정리는 강의 목차 순서대로 정리했다. 1. 정체되지 않는 프론트엔드 개발자의 일하는 방식 프레임워크를 위주로 공부하다 보면.. 따라가기 급급해진다. 내부적인 원리를 이해하지 못하면 남는 것이 없다. React, Vue는 컴포넌트 기반 개발이라는 공통점 ⇒ 이를 잘 알고 있으면 새로운 기술도 어렵지 않게 배울 수 있다. Homebrew → 패키지 매니저 for Mac VirtualBox → IE 환경 테스트 Frontend Developer : 어플리케이션이 사용자와 맞닿은 접점을 책임지는 사람 ..

이번 포스팅에서는 템플릿 프로그래밍에 대해서 정리해 보려고 한다. 첨부한 이미지는 포큐 아카데미의 C++ 강의 내용 화면이다. 템플릿이란 Java나 C#에서 제네릭(generic) 메서드/클래스와 비슷하다. 컴파일 도중 모든 코드를 만들어 준다. STL 컨테이너 또한 템플릿이라고 볼 수 있다. 템플릿이 가진 첫 번째 장점은 코드를 자료형마다 중복으로 작성하지 않아도 된다는 점이며, 두 번째로는 컴파일러가 미리 코드를 만들어 주기 때문에 런타임에서 돌리면 느린 함수들을 컴파일 시에 미리 호출해서 최종 결과만 상수로 뽑아서 쓸 수가 있다. 함수 템플릿 예를 들어 두 수를 더하는 Add 함수가 있다고 가정해 보자. int를 더할 수도 있고, float를 더할 수도 있고, double을 더할 수도 있다. // ..

내가 프로그래밍을 시작한지는 약 3년, 개발자라는 직군에서 일을 한지는 약 1년 정도가 지났다. 경력자가 보기에는 참 짧은 시간이지만, 나에게 있어서는 원래 전공에서 방향을 틀어서 새로운 분야를 뛰어들었던 나름 꽤 치열하게 살았던 시간들이라고 생각한다. 이번 글에서는 개발자로서 커리어를 어떻게 쌓아가야 할 것이며, 또 내가 중요하게 생각하는 가치는 무엇인지에 대해서 지극히 주관적인 나의 생각을 적어 보려고 한다. 오웬이 걸어온 길 먼저 나에 대해서 이야기를 하면, 나는 어렸을 때 그러니까 대략 고등학교 때까지 문제를 푸는 것을 좋아했다. 자연스럽게 수학, 과학 성적이 좋았고 흥미가 있었으며 이과를 선택하고 공대로 진학을 했었던 것 같다. 암기를 잘 하지는 못 했어서 그러한 과목들은 흥미도 없었고, 점수도..