개발왕 양선규

전통적인 그리디 문제이다. 부분 최적해가 전체 최적해가 된다.can_eat 함수의 슬라이싱 부분은, 투포인터나 슬라이딩 윈도우 성질도 띈다. import sysinput = sys.stdin.readline"""N: 식탁의 길이K: K 이하 거리 햄버거 먹기 가능table: 사람과 햄버거의 위치사람 기준 순서대로 왼쪽이든 오른쪽이든 가장 가까운거 먹으면 될거같은데..? 그리디?K가 최대 10이니 가능할거같다. K 햄버거와 사람을 따로 보지 않고, 매핑되는 관계로 간주한다.왼쪽부터 K범위를 순차 탐색하며, 매핑될 경우 두 요소를 방문처리한다."""def can_eat(idx, K): # 기준 (사람 또는 햄버거) point = table[idx] # idx 뒤로 K거리만큼 잘라낸다 (슬라이..

주어진 예산 안에서 요청받은 금액을 배정해 주어야 한다.예산이 충분하다면 요청받은 대로 전부 다 주면 되지만, 예산이 부족하다면 상한가를 정해서 최대한 많은 예산을 배분해야 한다.즉 상한가를 정하고, 모든 예산을 전부 소모한다면 최적의 해다. import sysinput = sys.stdin.readline"""1. 모든 요청을 줄 수 있다면 다 준다2. 상한액을 정해서, 상한액 이상인 요청엔 상한액만 준다. 상한액 이하의 요청은 그대로 준다"""N = int(input())reqs = list(map(int, input().split()))budget = int(input())def calc(limit, arr): """ 상한가를 고려해, 지급해야 할 금액 계산 limit: 상한가 ..

2018 KAKAO BLIND RECRUITMENT에 출제된 문제이다. 구현, 문자열 문제이고 문제 조건이 크게 어려운 건 아닌데, 구현 문제다 보니까 디테일한 부분에서의 실수가 없도록 주의해야 하는 문제이다. def solution(msg): """인덱스 -> 문자열, 문자열 -> 인덱스 사전 제작""" idx_to_str = [''] + [chr(i) for i in range(ord('A'), ord('Z') + 1)] str_to_idx = dict() for i in range(26): char = chr(ord('A') + i) str_to_idx[char] = i + 1 """메인 로직, 문자열을 전부 압축할 때..

2020 KAKAO BLIND RECRUITMENT에 출제된 문제이다.구현, 완전탐색 문제이며 보드 확장 아이디어를 떠올리지 못한다면 풀기 까다로울 수 있는 문제이다. def solution(key, lock): """ 90도 회전시키는 함수 자물쇠가 열리는지 확인하는 함수 -> 열쇠를 보드에 적용 + 자물쇠값 모두 1인지 확인 + 열쇠를 보드에서 제거 확장된 보드를 만든다 자물쇠를 보드 중앙에 배치한다 열쇠를 4방향으로 회전시키며, 모든 가능한 위치에서 열기 시도한다 """ """키를 시계 방향으로 90도 회전하는 함수""" def rotate_key(key): return [list(row) for row in zip(..

2023 KAKAO BLIND RECRUITMENT에 출제된 문제로써, Union-Find가 사용되는 문제이다.Union-Find는 특정 그룹으로 묶고, 나누고, 그룹을 찾고 하는 것에 특화된 알고리즘이며, 표 병합같은 문제에 딱 맞는 알고리즘이다. def solution(commands): """ find: 대표를 찾는 함수, 재귀 구현 union: 병합 함수, merge 구현 """ """1차원 리스트 사용, 처음엔 자기 자신이 대표""" parent = [i for i in range(2601)] values = ["" for _ in range(2601)] # 처음엔 전부 빈 값 """좌표를 1차원 인덱스로 변환하는 함수""" def..

그래프 기초 문제로써, "연결 성분"의 개수를 구하는 문제이다. 즉 연결되지 않은 그래프의 개수를 구하면 된다. 크게 어렵지 않은 문제였다. from collections import dequedef solution(n, computers): table = [[] for _ in range(n)] # 인접리스트 형태 변경 for i in range(n): for j in range(n): if i == j: continue if computers[i][j] == 1: table[i].append(j) visited = [False..

테스트 코드처음으로 테스트 코드라는 것을 작성해 보았다. 단위 테스트, 통합 테스트에 대해 공부하고 그것을 적용해 테스트 코드를 작성했다. 테스트 코드는 말 그대로 테스트이기 때문에 간단할 것이라고 생각했지만 생각보다 고려할 것이 많았다. 물론 그냥 내 맘대로 짜면 짤 수도 있었겠지만, 무엇이 좋은 테스트인가? 어떤 것을 테스트해야 하는가? 모킹은 어느 정도 수준까지 해야 하는가? 테스트 해야 할 흐름은 어떤 것들이 있는가? 즉, 최적의 테스트 라는 게 무엇인지를 깊이 탐구하는 것과, 그것을 알기 위해 테스트라는 것 자체를 깊게 이해해야 했기에 많은 시간이 걸렸던 것 같다. 테스트는 보는 이로 하여금 테스트의 의도가 명확히 전해져야 하고, 그것을 위해 조금의 불편함도 감수할 수 있어야 한다. 쓸데없이 복..

일반적인 Hard Delete 방식을 사용했다면 외래키 관계를 이용한 엔티티와 DB 레벨에서의 cascade를 이용할 수 있었을 테지만, 중고차 거래 플랫폼 특성상 데이터의 신뢰도가 중요했기 때문에 Soft Delete 방식을 채용했다. 그로 인해 연쇄 삭제 기능은 서비스 레벨에서의 delete() 메서드 조합이나 QueryDsl 커스텀 쿼리를 통해 직접 구현해야 했다. 처음엔, 모든 엔티티가 상속받는 BaseEntity에 존재하는 softDelete() 메서드를 Facade 서비스 클래스에서 전부 호출해서 삭제할까 생각했다. 하지만, 그러면 제공되는 인자는 CarListing.id(판매 차량 id) 한개 뿐일텐데 이걸로 repository 조회해서 연관된 엔티티 id를 얻고 하는 일련의 작업을 서비스 ..

스프린트 3이 종료되었다. 스프린트 2 회고에서 차량 등록, 조회를 어떻게 구현할지 걱정했지만 훌륭히 구현해 냈다.이번에 구현한 기능은 아래와 같다.차량 등록판매 차량 상세 조회 차량 정보를 다루는 엔티티가 무려 10개였기 때문에, 백엔드 코드 작성이 매우 매우 어려웠다. 애플리케이션 레벨에서 관계는 어떻게 정의하며, repository와 service는 어떤 구조로 작성하고 관리하는지, 쿼리는 어떻게 최적화 하는지 등등… 고민해보지 못했던 문제들을 많이 만났다. 스프린트 2의 유저 관련 로직을 짤 때보다 10배는 더 어려웠던 것 같다. 이번 스프린트 3을 진행하며 가장 크게 배운 것은 객체지향적 설계와 SOLID원칙, 그리고 쿼리 최적화이다. 백엔드에서 어려웠던 점 - 객체지향적 설계와 N+1, 카테시..

차량 상세조회 기능을 구현하며 차량 관련 엔티티 10개를 조회해야 했는데, 이 과정에서 Lazy Loading, fetchJoin, BatchSize를 공부하고 적용해 보았다. 백엔드에서 쿼리 짜는 게 제일 어려운 것 같다. 아래는 Lazy Loading, fetchJoin(), BatchSize에 대해 내가 정리한 글이다.https://yskisking.tistory.com/316 JPA 쿼리 최적화 - Lazy loading, fetchJoin(), BatchSize개인 프로젝트 썬카에서 차량 상세 조회 기능을 만들다가 쿼리 최적화 문제에 부딪혔다.무려 10개의 엔티티를 전부 조회해야 했고 성능 부분을 신경쓰지 않을 수 없었기에, 자연스럽게 Lazy loadingyskisking.tistory.com..