본문 바로가기

전체 글631

백준 14425 문자열 집합 (이분 탐색을 이용한 JAVA 자바 풀이) 백준 14425 문자열 집합 (이분 탐색을 이용한 JAVA 자바 풀이) https://www.acmicpc.net/problem/14425 이분 탐색을 이용한 풀이이다. N개의 문자열로 이루어진 집합 S에서 M개의 문자열 중 집합 S에 속하는 문자열의 개수를 구해야 한다. 자바의 컬렉션 Set의 contains 메서드를 이용하면 간단하게 풀 수 있지만 바이너리 서치를 직접 구현해 풀어보기 좋은 문제여서 바이너리 서치를 이용해 풀어보았다. 먼저 문자열을 sort 해준다. String[] strings = new String[N]; while(N-->0){ strings[N] = bufferedReader.readLine(); } Arrays.sort(strings); -> 시간 복잡도 O(nlogn) 문자.. 2023. 7. 3.
이분탐색 (binary search), 아이디어, 작동 원리, 시간 복잡도/성능, 특징, 자바 구현 코드 이분 탐색 혹은 이진 탐색 정렬되어 있는 집합에서 원하는 값을 찾는 효과적인 탐색 방법으로 알려진 이분 탐색에 대해 알아본다. 아이디어 큰 틀은 분할 정복 원리를 이용한다. -> 배열의 가운데 원소 A[mid]와 탐색키 x를 비교한다. -> 이 때 3가지 케이스로 나뉜다. (1)탐색키=가운데원소 → 탐색성공(인덱스mid반환후종료) (2)탐색키가운데원소 → 순환호출 (이진 탐색(원래 크기 1/2의 오른쪽 부분배열)) *mid = ( 시작인덱스 i + 마지막 인덱스 i )/ 2 - 분할 과정: 배열의 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 분할. 탐색키와 가운데 원소가 같으면 가운데 원소의 배열 인덱스를 반환/종료 - 정복 과정: 탐색키가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진 탐색을.. 2023. 7. 3.
백준 17232 생명 게임 (JAVA 자바 풀이) | 누적합 배열 백준 17232 생명 게임 (JAVA 자바 풀이) 초기 제출 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws IOException { StringTokenizer stringTokenizer = new StringTok.. 2023. 7. 3.
데이터 모델과 트랙잭션 디자인 / 개별 프로세스 운영 관리 및 배포 시스템 디자인 패스트 캠퍼스(The Red: 4천만 MAU를 지탱하는 서비스 설계와 데이터 처리 기술 by 카카오페이지 기술전략이사 윤진석) 필기록입니다. 서버 개발자들은 반드시 영속화 레벨의 데이터에 대해서 문제를 해결하는 일을 마주치게 된다. 논리적 데이터 아키텍처 -> 데이터 스키마 또는 논리적 데이터 모델이라고 함 논리적 데이터 모델은 흔히 (1) 객체 기반의 개체-관계 ER모델 -> Object-based logical models (2) 행 기반의 관계형 모델을 사용 -> Record-based logical models NoSQL 데이터 모델은 모두 (3) nested key value pairs 다차원 모델을 사용한다. -> object도 아니고 record 기반도 아니다 객체지향의 프로그래밍 모델에서는.. 2023. 7. 3.
코드 유지보수성과 확장성을 높이는 디자인 패턴 패스트 캠퍼스 (The Red: 4천만 MAU를 지탱하는 서비스 설계와 데이터 처리 기술 by 카카오페이지 기술전략이사 윤진석) 필기록입니다. 코드레벨에서의 확장성에 대해 알아보자. 프로그래밍 패러다임 절차적 프로그래밍 -> 구조적 프로그래밍 -> 객체지향 프로그래밍 디자인 패턴이란? 베스트 프랙티스(best practice, 모범사례)의 일반화된 디자인 유형 문제를 푸는 것을 패턴화했다고 할 수 있다. 객체 지향 프로그래밍 이후의 점점 복잡해지는 소프트웨어를 해결하기 위해 등장. Object Composition 객 체 합성 구조를 통해 확장성 획득 "Client"는 동기화 서비스인 SyncService 인터페이스만 바라보도록 한다. 환경이나 요구사항에 동기화 메커니즘을 결정할 수 있도록 구체 클래스를.. 2023. 7. 3.

티스토리툴바