00. 들어가며 테스트 주도 개발(TDD, Test-Driven Development), 말 그대로 테스트가 메인이 되는 소프트웨어 개발 방법론으로 선 개발 후 테스트가 아닌, 선 테스트 후 개발 방식을 의미한다. TDD가 반드시 필요한가 혹은 유리한 것인가에 대한 다양한 포스트들이 존재하지만, 현재 필자는 TDD가 필요하다는 입장이다. 현재 서비스 운영회사를 다니고 있고, Legacy와의 전쟁이 이어지고 있는 가운데 리팩토링 과정에서 수정으로 인한 사이드이펙트를 발생시키지 않기 위해서는 TDD를 도입하는 것이 바람직할 것이라고 생각하기 때문이다. 또한 동료들이 TDD에 대한 관심도가 상당히 높은 편인데, 스스로 많이 부족하다고 생각하여 본격적으로 TDD에 대한 공부도 함께 하고자 한다. 다른 카테고리의..

보다 유연하고 확장성 있는 설계를 하기 위해 나는 과연 객체에 대해서 온전히 이해하고 있을까? 사내스터디로 조영호님의 오브젝트라는 책을 공부하게 된 배경이다. Chapter 3를 통해 언급될 역할, 책임, 협력은 실생활에서도 적용된다고 보는데, 내가 회사에서 맡고 있는 역할과 책임을 다하기 위해 그리고 보다 나은 협력을 구축하기 위해 공부하고 있는 내용을 블로그에도 추가적으로 정리하고자 한다. 앞으로 해당 카테고리에 기재할 내용들은 모두 앞서 말한대로 조영호님의 오브젝트 책을 보고 공부한 내용을 정리한 게시글들입니다. 반드시 기억해야 할 내용들을 요약함과 동시에, 공부하며 든 생각을 함께 정리합니다. Chapter 01. 객체, 설계 여느 공학보다 상대적으로 짧은 역사를 가지고 있는 소프트웨어 분야는 이..

1. 문제 2642번: 전개도 입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지의 정수들이 여섯 개 있고, 숫자 사이에는 빈칸이 하나씩 있다. 1에서 6까지의 숫자는 전개도의 면을 나타내고, 0은 전개도의 바깥 부분을 나 www.acmicpc.net 2. 풀이 문제에서 요구하는 것은 간단하다. 전개도가 주어졌을 때, 정육면체를 만들 수 있는 전개도인지 판단하고 가능하다면 숫자 1이 써져 있는 면의 반대 면에 위치한 숫자를 출력하는 것이다. 그렇다면 당연하게도 우리는 주어진 전개도가 정육면체를 만들 수 있는지 여부를 어떻게 판단할 것인가를 고민해야 한다. 2.1 정육면체 전개도의 종류 먼저 정육면체를 만들 수 있는 전개도의 종류는 아래 이미지와 같이 총 11가지가 있다. 그럼 첫 번째로, 11가지 유..

1. 백트래킹? DFS? 백트래킹과 DFS는 어떻게 보면 분리하기가 애매한 개념이다. 굳이 분리해서 의미를 부여하자면 끝까지 가느냐 돌아오느냐로 간단하게 생각해볼 수 있다. DFS 역시 재귀를 통해서 구현하므로 시작 기점으로 돌아오는 개념이 들어가 있기는 하지만, 백트래킹의 경우 현재 가는 길이 더 이상의 해가 아니라고 판단되면 되돌아오는 것을 의미한다. 간단하게 DFS 개념을 정리하자면, 가능한 모든 경로를 깊이 우선으로 탐색하는 것을 의미한다. DFS에 대한 자세한 내용은 아래 게시글을 통해 알아보자! DFS(Depth-First Search) + BFS 복습 깊이 우선 탐색(DFS, Depth-First Search)을 알아보기 이전에 그래프에 대한 개념을 이해해야 하므로, 먼저 아래 포스팅을 참고..

1. 문제 20304번: 비밀번호 제작 서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부 www.acmicpc.net 2. 풀이 결과적으로 어떤 답을 만들어내야 하는가가 다소 헷갈릴 수 있는 문제의 유형이라 생각한다. 그 중 먼저 문제의 핵심인 안전거리와 안전도를 판단하는 방법을 알아본다. 2.1 안전거리와 안전도 3, 4 두 가지의 비밀번호가 입력된 적 있을 때, 2라는 비밀번호를 설정했을 때의 안전거리를 알아보자. 먼저 2, 3, 4를 이진수로 변환하면 아래와 같다. 3: 0011 4: 0100 2: 0010 (2,3)의 경우 서로다른 비트가 한 개이기 때문에 안전거리는..

1. 문제 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net 2. 풀이 본 문제는 크게 두 가지 방법으로 풀이가 가능하다. 다만, 두 가지 경우 모두 사전 작업이 한 가지 필요한데 이는 바로 주어진 쿼리가 수행 가능한 쿼리인지 먼저 확인하는 것이다. 여기서 수행 가능한 쿼리란 어떤 것을 의미하는 것일까? 문제에서 주어진 순열의 인덱스가 과연 존재하는 인덱스인지 검증이 필요하다는 것이다. 서로 다른 문자로 이루어진 문자열로 순열을 만드는 방법은 (순열의 길이)! 이다. 즉, 입력 받은 순열의 길이 팩토리얼 값을 가지고..

1. 문제 14534번: String Permutation First line of the input contains T (1 ≤ T ≤ 200), the number of test cases. For each test case, there will a string of characters, L (1 ≤ L ≤ 5). www.acmicpc.net 2. 풀이 백트래킹의 가장 기본적인 유형인 순열 만들기 문제다. 집합의 요소를 사용했는지를 판단할 boolean 배열을 선언하여, 각 요소들의 사용여부를 변경해가며 순열을 만들면 해결할 수 있다. 다만 현재 문제는 조합(Combination)이 아닌 순열(Permutation)이므로, 백트래킹을 할 재귀 함수 내에서 시작지점은 항상 첫 요소로 설정해야 한다. 시..

1. 문제 6148번: Bookshelf 2 Here we use cows 1, 3, 4, and 5, for a total height of 3 + 3 + 5 + 6 = 17. It is not possible to obtain a total height of 16, so the answer is 1. www.acmicpc.net 2. 풀이 문제를 간단하게 요약하면 다음과 같다. John이 가지고 있는 소들을 책장 높이 이상으로 쌓았을 때, 책장과 소들의 높이의 차이가 최소가 되는 경우를 구하라는 것이다. 조건들은 아래와 같다. N ≤ 20 (N은 소의 총 숫자) H_i ≤ 1,000,000 (소의 높이) 1 ≤ B ≤ S (B = 책장 높이, S = 전체 소 높이의 합 조건들로부터 유추할 수 있는 점..

1. 문제 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 2. 풀이 본 문제는 다소 복잡해 보이지만, BFS를 이용한 구역나누기 문제이며 잡다구리한 비즈니스 로직(빙산이 녹는 것)은 시뮬레이션 문제라고 볼 수 있다. 문제에 주어진 조건들을 순수하게 따라서 비즈니스 로직을 구현하고, 빙산이 녹아서 두 구역으로 나뉘어졌는지만 그래프 탐색을 통해 해결한다면 어렵지 않은 문제! 중요한 조건인 빙산이 부리되지 않고 한 번에 모두 녹는 경우 0을 반환하는 조건만 잘 체크해준다면 큰 어려움 없이 풀 수 있다. 3...

깊이 우선 탐색(DFS, Depth-First Search)을 알아보기 이전에 그래프에 대한 개념을 이해해야 하므로, 먼저 아래 포스팅을 참고하도록 하자. 그래프와 BFS(Graph & Breadth First Search) BFS(너비 우선 탐색) 알고리즘에 대해 알아보기 전에 필수적으로 알아봐야 할 자료구조는 바로 그래프(Graph)다. 그래프는 실질적으로 프로그래밍 언어 라이브러리 상에서 제공하기 보다는 추상적 kwanik.tistory.com 1. 깊이 우선 탐색(DFS, Depth-First Search) 이전 포스트와 '깊이 우선 탐색'이라는 이름에서 알 수 있듯이, '깊이 우선 탐색'은 먼저 한 방향으로 갈 수 있는 경로를 먼저 탐색하는 방식이다. 이는 그래프 탐색의 가장 단순하면서도 고전적..