본문 바로가기

분류 전체보기

 (433)
프로그래머스 - 구명보트(파이썬, LV2) / 그리디(Greedy) https://programmers.co.kr/learn/courses/30/lessons/42885?language=cpp 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 풀이의 핵심은 모든 사람이 보트 1개씩 필요하다고 초기값을 둔다. 그리고 전체 사람들의 무게를 정렬해서 가장 무거운 사람과 가장 가벼운 사람 순으로 같이 갈 수 있는지 같이 갈 수 있을 경우 보트 수를 1개 뺀다(같이 타므로). 이런식으로 전체 사람들을 탐색하여 가장 가벼운 사람과 무거운 사람이 만나는 지점에 달..
프로그래머스 - 큰 수 만들기(파이썬, LV2) / 그리디(Greedy) https://programmers.co.kr/learn/courses/30/lessons/42883?language=python3# 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 이 문제는 그리디로 현재 최상의 값을 계속 골라나가면 된다. 그런데, 최상의 값을 찾기 위한 탐색 범위를 계속 한정지어서 풀려고 했다. 그러나 그렇게 풀어버리니 아래 테스트 케이스의 시간 복잡도를 극복하지 못했다. O(N^2)이 되버린 것이다. "INPUT" number = "1234567890"*100000 k = 999999 "OUTPUT" answer = "99999...." 그래서 결국 다른 풀이를 찾아봤다. (출처 : scarletbreeze의 블로그) 핵심은 O(N)이 되도록 문자열을 한 번씩 파..
프로그래머스 - 조이스틱(파이썬, LV2) / 그리디(Greedy) https://programmers.co.kr/learn/courses/30/lessons/42860?language=python3 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 먼저 strSol을 'AAAA....' 로 두고 시작점 cursor는 0이다. 이 때 strSol cursor의 위치에 해당하는 name 값으로 변경하고, 현재 가장 가까운 A가 아닌 name의 문자열의 위치로 가서 strSol을 바꾼다. 여기서 그리디는 2가지가 된다. 상하의 값 중 현재 가장 최소값으로 변경한..
프로그래머스 - 순위(파이썬, LV3) https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 정답 출처 : 멍토의 IT블로그 와샬플로이드 알고리즘으로 접근하는 방식 그러나, 그렇게까지 생각이 안나서, 로직만을 생각했다. 로직은 맞았으나 구현방식이 계속 틀려서 정답을 참조했다ㅠㅠ win[i] -> {} i가 이긴 사람들 집합 lose[i] -> {} i를 이긴 사람들 집합 의 리스트를 준비하고 경기결과를 전체 파싱해서 채워 넣는다. 그리고 이제 i를 이긴 사람들에게 이긴 사람들은 전부 i를 이길 수 있다 또한 i에게 진사람들은 i가 진사람들에게도 전부 진다. 이..
프로그래머스 - 자물쇠와 열쇠 (파이썬, LV3) https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 2020 KAKAO 문제 간과했던 내용 Lock과 Key의 크기가 다를 수 있던 점 Board(전체 배열)의 크기는 Lock의 2배가 아닌 3배여야 한다는 점 회전 배열이 바로 안떠올랐던 점(값을 적어서 확인해봄) 돌기끼리 부딪혀도 안된다는 점(무조건 매끄러운 1이 되야함, 2도 안됨) 풀이 자물쇠 3배 크기의 전체 배열을 구성한다. 해당 전체 배열에서 자물쇠를 중간(start~end) 부분에 값을 옮긴다. 그..
마이크로 서비스 패턴 #5 비즈니스 로직 설계 개요 비즈니스 로직 설계에 있어 큰 어려움 2가지 도메인 모델은 서로 얽혀있다 트랜잭션 관리 하의 비즈니스 로직 설계 어려움 비즈니스 로직 구성 패턴 2가지 1) 절차적 구성의 트랜잭션 스크립트 패턴 > 복잡한 비즈니스 로직 구현 어려움 2) 도메인 기반 모델 패턴 > 클래스로 나누어 복잡한 비즈니스 로직 구현 가능 VO 와 DAO, DTO 로 나누듯이 상태 클래스와 동작 클래스로 구분지어 설계 DDD(Domain Driven Design) Entity : 영속적인 ID를 가진 객체 Value Object : 값들을 모아 놓은 객체 Factory : 객체 생성 로직이 구현된 객체 Repository : entity 를 저장하는 DB 접근 로직 캡슐 서비스 : entity, VO 에 속하지 않은 비즈니스 ..
프로그래머스 - 가장 긴 팰린드롬(파이썬, LV3) https://programmers.co.kr/learn/courses/30/lessons/12904?language=python3 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 해당 문제는 문자열 핸들링 문제로 접근하였다. 팰린드롬은 reverse를 해도 똑같은 문자열을 뜻하는데, (예 aba, abba) 주어진 문자열 내에서 가장 긴 팰린드롬의 길이를 찾는 문제였다. 처음에는 특정 문자열을 기준으로 계속 앞뒤로 한칸씩 이동해서 같은 문자일 때만 카운트..
마이크로 서비스 패턴 #4 트랜잭션 관리 트랜잭션 관리?(트랜잭션 : 데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업의 단위 또는 한꺼번에 모두 수행되어야 할 일련의 연산들을 의미한다, ACID 트랜잭션이 대표적인 특성) MSA에서는 #3 IPC와 같은 맥락으로 트랜잭션 관리가 조금 더 복합적이다.하나의 DB 트랜잭션으로 처리하던 모놀리틱한 서비스가 아니기에 트랜잭션 관리가 복잡해지는 것이다.자체 DB들을 지닌 여러 서비스들이 각각의 트랜잭션을 어떻게 관리할 수 있을까, 이런 부분들에 대해서 알아보고자 한다.분산 트랜잭션? 사가(SAGA)기존에는 분산 트랜잭션을 통해서 여러 서비스, DB들에 대해 데이터 일관성을 유지할 수 있었다.그렇지만 동기 IPC에서 오는 낮은 가용성에 의해 최근까지 많은 신기술들과 접목하기에는 성..

티스토리툴바