sh1mj1_log

이전 글 https://sh1mj1-log.tistory.com/133 에서 객체지향 설계의 핵심은 역할, 책임, 협력 이라고 했습니다. 협력: 애플리케이션의 기능을 구현하기 위해 메시지를 주고받는 객체들 사이의 상호작용. 책임: 객체가 다른 객체와 협력하기 위해 수행하는 행동. 역할: 대체 가능한 책임의 집합. 책임이 객체지향 애플리케이션 전체의 품질을 결정합니다. 책임 할당은 응집도와 결합도와 같은 설계 품질과 깊이 연관되어 있습니다. 설계는 변경을 위해 존재하고 변경에는 비용이 발생합니다. 좋은 설계는 비용을 최소화하는 것이지요. 응집도가 높고 결합도가 낮은 것이 좋은 설계입니다. 그를 위해서 객체의 상태가 아닌 행동에 집중합니다. 또 그를 위해 객체의 책임에 초점을 맞추는 것이 좋습니다. 이번 장..

유클리드 호제법 유클리드 호제법(Euclidean-algorithm) 은 두 수의 최대 공약수를 구하는 알고리즘입니다. 일반적으로 최대공약수를 구할 때는 소인수분해를 이용하지만 유클리드 호제법을 사용하면 더 간단하게 가능합니다. 유클리드 호제법 원리 먼저 최대 공약수를 구하는 데 사용하는 핵심 연산인 MOD 을 알아야 합니다. 연산 기능 예 MOD 두 값을 나눈 나머지를 구하는 연산 10 MOD 4 = 2 // 10 % 4 = 2 1. 큰 수를 작은 수로 나누는 MOD 연산 수행. 2. 앞 단계에서의 작은 수와 MOD 연산 결과 (나머지값)으로 MOD 연산 수행. 3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택. 270 과 192 의 최대공약수를 유클리드 호제법으로 구하는 그림을 통해 구체..

오일러 피 오일러 피 함수 P[N]는 1부터 N까지 범위의 N과 서로소인 자연수의 개수를 뜻합니다. 실제 오일러 피 함수는 증명과정을 공부해야 완벽히 알 수 있지만 이 포스팅에서는 코딩 테스트에 사용하기 위한 구현 부분만 알아봅니다. 오일러 피 함수의 원리는 에라토스테네스의 체와 비슷합니다. 오일러 피 함수의 원리 1. 구하고자 하는 오일러 피의 범위만큼 배열 초기화 2. 2부터 시작해서 소수일 때(현재 배열의 값과 인덱스가 같으면) 현재 선택된 숫자[K] 의 배수에 해당하는 수를 배열에 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행. 이 때 i 는 K의 배수. 3. 배열의 끝까지 2번 과정을 반복하여 오일러 피 함수를 완성. 그림과 예시와 함께 더 자세히 알아봅시다. 1. 구하고자 ..

정수론 수학에서 정수론은 수의 성질을 공부하는 분야입니다. 실제 코딩테스트에서는 정수론의 분야가 굉장히 방대하기 때문에 가장 많이 등장하는 소수, 오일러 피, 호제법에 관련하여 학습합니다. 소수 소수(prime number) 는 자신보다 작은 2개의 자연수를 곱해서 만들 수 없는 1보다 큰 자연수를 말합니다. 1과 자기 자신 외에 약수가 없는 수입니다. 소수를 구하는 대표적인 방법은 에라토스테네스의 체가 있습니다. 에라토스테네스의 체 1. 구하고자 하는 소수의 범위만큼 1차원 배열 생성. 2. 2부터 시작해서 현재 숫자가 지워지지 않았다면 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 처음으로 선택된 숫자는 지우지 않습니다. 3. 배열의 끝까지 2를 반복한 후에 배열에서 ..

이전 글 https://sh1mj1-log.tistory.com/131 에서 객체 지향 프로그밍을 구성하는 다양한 요소와 구현 기법을 살펴보았습니다. 클래스, 추상 클래스, 인터페이스를 조합하여 객체지향 프로그램을 구조화하는 기본 방법 상속을 이용해 다형성을 구현하는 기법 다형성은 지연 바인딩을 통해 구현됨. 상속은 다형성을 위해 사용. 코드 재사용만 할 때는 캡슐화 측면에서 합성이 더 좋음. 유연한 객체 지향 프로그램을 위해서는 컴파일 타임 의존성과 런타임 의존성이 다름. 역할, 책임, 협력 객체지향의 본질은 역할(role), 책임(responsibility), 협력(collaboration) 입니다. 물론 클래스, 상속, 지연 바인딩이 중요하지만 이는 구현 방법일 뿐 본질은 아닙니다. 계속 반복하여 ..

https://sh1mj1-log.tistory.com/130 글에서 이어지는 포스팅입니다. 백준 1931 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 1. 문제 분석 1개의 회의실에 회의가 겹치지 않도록 최대한 많은 회의를 배정해야 합니다. 이 때는 그리디 알고리즘을 적용해야 합니다. 현재 회의의 종료 시간이 빠를 수록 다음 회의와 겹치지 않게 시작하는 데 유리합니다. 종료 시간이 빠른 순서대로 정렬하면 겹치지 않는 회의실을 적절하게 선택하면 됩니다. 2. 손으로 풀기 1. 회의와 정보와 관련된 데이터를 저장한 후 종료 시간 순으로 정렬. 종..

이전 글 - https://sh1mj1-log.tistory.com/128 : 프로그래밍 패러다임과 객체, 설계 - 코드로 이해하는 객체지향 설계 에서 이어집니다. 객체지향 프로그래밍 책에서는 가상의 영화 예매 시스템을 예로 들어서 설명합니다. 영화 예매 시스템 요구사항 살펴보기 사용자는 영화 예매 시스템을 이용해서 쉽고 빠르게 영화 예매할 수 있다. 영화 : 영화에 대한 기본 정보(제목, 상영 시간(영화 런타임), 가격 정보) 상영: 실제로 관람하는 사건(상영 일자, 시간, 순번) 사용자가 실제로 예매하는 대상은 영화가 아니라 상영이다. 특정 조건을 만족하는 예매자는 요금을 할인받을 수 있다. 할인액은 할인 조건(discount condition)과 할인 정책(discount policy) 으로 결정된..

그리디(Greedy) 그리디(Greedy) 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘입니다. 그래서 동적 계획법(Dynamic Programming) 보다 구현하기 쉽고 시간 복잡도가 우수합니다. 하지만 항상 최적의 해를 보장하지는 못한다는 단점도 있습니다. 그래서 항상 그리디 알고리즘을 사용하기 전 논리에 대해 자세히 살펴보아야 합니다. 그리디 알고리즘의 수행 과정 1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택 2. 적절성 검사: 현재 선택한 해가 전체 문제의 조건에서 벗어나지 않는지 검사 3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 만약 해결할 수 없다면 1의 과정을 반복. 바로 ..

이진탐색 이진 탐색(Binary Search)은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘입니다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해서 데이터의 크기를 절반씩 줄이면서 대상을 찾습니다. 기능 특징 시간 복잡도 타깃 데이터 탐색 중앙값 비교를 통한 대상 축소 방식 O(logN) 구현과 원리가 간단해서 코딩 테스트에서 보통 부분 문제로 포함되어 있는 경우가 많습니다. 이진 탐색의 핵심 원리 이진 탐색을 오름차순으로 정렬된 데이터에서의 예로 찾아보겠습니다. 내림차순으로 정렬되어 있는 경우에도 조건을 반대로 해서 똑같이 실행하면 됩니다.) 이진 탐색 과정 현재 데이터셋의 중앙값(median)을 선택. 중앙값 > 타겟 데이터(찾고자 하는 데이터) 일 때 중앙값 기준으로 왼쪽 데이터..

지난 1년 간 스프링을 공부하고 안드로이드 앱 개발 프로젝트를 하면서 dependency(의존성)을 관리하는 것이 굉장히 중요하다는 이야기를 계속해서 접했고 공부했습니다. Spring boot 에서 bean 과 @Autowired 라는 어노테이션을 통해 의존성을 주입하고, 안드로이드 코트린에서는 hilt 라는 의존성 관리 라이브러리를 사용하여 의존성을 관리했습니다. 이 의존성은 결국 객체지향의 핵심일 것이다. 실무적인 관점에서 의존성을 공부하고 다루어 보니 객체지향을 더 깊게 공부해야 할 때가 온 것 같습니다. 그래서 '오브젝트 : 코드로 이해하는 객체지향 설계 - 조영호' 책을 읽으면서 정리해보고자 합니다. 책의 머릿말에서 이 책은 실무 경험이 있으며 설계에 대한 고민을 충분히 한 사람들이 읽으면 좋을..