백엔드 개발자로 가는길

자바 - 백준 2169 / 로봇 조종하기

https://www.acmicpc.net/problem/2169골드2풀이 방법단순 dfs로 하면 시간 초과 발생합니다. (시간 복잡도: O(3^(N * M))N, M(1≤N, M≤1,000)현재 문제는 “각 칸까지 올 수 있는 최적 해를 모아 두고, 그 위에서 다음 칸의 최적 해를 구한다”가 목표→ DP 생각하기이동 경로 가능 경로: 오른쪽, 왼쪽, 아래따라서 위에서 부터 오른쪽에서 왼쪽으로 갈 때 max값과 왼쪽에서 오른쪽으로 갈 때 max값을 구한 뒤두 값중 더 큰 값을 아래로 내려주면 된다.이때 시작은 0,0에서 하기 때문에 이 경우에는 왼쪽에서 오른쪽의 경우만 생각하면 된다.dp 시간 복잡도매 행마다 두 번의 선형 스윕을 수행하므로 O(N×M)코드import java.util.*;import j..

https://www.acmicpc.net/problem/2109골드3구현 방법하루에 최대 한 강연 + 강연마다 마감일과 강연료가 있음 + 최대 수익이 목표→ 작업 스케줄링 문제⇒ 그리디 알고리즘p 값(강연료)가 높은 순, p값이 같은 경우 d값(마감일)이 작은 순으로 정렬하면 답을 구할 수 있습니다.마감일이 같은 경우, 마감일에 가장 가까우면서 일정을 잡을 수 있는 일자로 선정합니다.visited 배열을 이용하여 가능한 일자를 구합니다.날짜 찾기 최적화기존 방식에서는 visited 배열을 이용해 각 날짜마다 강연이 배정되었는지 확인하고, 빈 날짜를 찾기 위해 매번 O(n)의 선형 탐색을 수행했습니다.이를 개선하기 위해 유니온 파인드의 find() 함수를 이용하기로 했습니다.parent[날짜] = 그 날..

https://www.acmicpc.net/problem/2533골드3구현 방법문제 조건에서 “친구 관계가 트리 구조”라고 했기 때문에 사이클이 없고, 모든 노드가 연결되어 있습니다.따라서 DFS나 재귀를 통해 트리 순회가 가능해집니다.상태는 2가지로 나뉩니다.얼리어답터인 경우 : 자신의 친구는 얼리어답터가 아니여도 됩니다.얼리어답터가 아닌 경우 : 자신의 친구는 무조건 얼리어답터가 되어야 합니다.상태를 보면 각 노드는 하위 서브 트리의 최적해에 의존한다는 것을 알수 있습니다.따라서 DP를 이용하기로 했습니다.결론트리 순회를 하면서 각 노드의 두 가지 상태에 대해 이미 계산된 최적해(최소 얼리 어답터 수)를 저장해두고, 이를 다시 활용함으로써 중복 계산을 피해 최소 얼리어답터인의 수를 구하도록 하겠습니다..

https://www.acmicpc.net/problem/1520골드3구현 방법잘못된 접근BFS를 통해서 상,하,좌,우 를 탐색하여1. 인덱스 범위에 있고,2. 갈 곳의 높이가 현재 높이 보다 작은 경우갈 수 있는 경로를 더해주는 방식으로 구현했습니다.또한 한번도 도착하지 않은 경우에는 큐에 넣어 탐색을 진행할 수 있도록 했습니다. 하지만 이렇게 하는 경우, 나중에 추가된 경로의 개수가 반영되지 않는 문제가 발생했습니다.이는 한 번 방문한 노드의 경우 다시 탐색하는 과정이 없기 때문에 추가된 경로의 개수가 업데이트되지 않기 때문이였습니다. 해결 방법나중에 경로를 추가하는 상황을 만들지 않도록 하면 됩니다.현재 문제에서는 높은 건물에서 낮은 건물로 간다는 방향성이 있습니다.이를 통해 다음 경로를 정하기 전..

상황펀딩 생성 테스트 코드 작성 중 메서드별 데이터의 독립적인 환경을 보장하기 위해 삭제 로직을 추가했습니다.삭제 방식은 @Sql을 통해 쿼리문을 직접 실행시키는 방법을 선택했습니다.삭제 해야할 데이터는 funding, anniversary_category, consumer, product_option, product 테이블에 있는 정보들 입니다.테이블별 1~2개 정도의 레코드를 삭제해야하고, 현재 외래키 제약 조건이 테이블간 걸려 있습니다. 고민쿼리문 작성 과정에서 delete를 사용할지 truncate를 사용할지 고민했습니다.delete 장점1. 외래키 제약 조건을 풀고, 다시 잠그는 과정이 필요하지 않음.delete 단점1. 삭제시 로그를 남기고, 하나의 데이터씩 삭제하기 때문에 한번에 전체를 삭제..

https://www.acmicpc.net/problem/1027골드4구현 방법1. 서 있을 건물을 정한다.2. 볼 건물을 정한다.3. 사이 건물들이 시야를 가리는지 확인한다.  a. 사다리꼴 면접 공식으로 최대 건물 높이를 구합니다.  b. 큰 사다리꼴 = 사이 건물 높이로 나눠진 사다리꼴 + 사이 건물 높이로 나눠진 사다리꼴4. 사이 건물들이 시야를 안 가릴 경우, 볼 수 있는 건물수를 하나 늘린다. 주의 사항범위를 주의해야합니다.최대 높이가 1,000,000,000이기 때문에 계산 과정에서 오버플로우를 조심해야합니다. 개선 방법사다리꼴 면접으로 중간 높이를 구하지 않고, 기울기 차이로 판단 가능합니다. 코드import java.util.*;import java.io.*;/** * 백준 1027 * ..

헥사고날 아키텍처 도입데이터베이스 변경 리펙토링 과정에서 두가지 문제점을 발견했습니다.DB 엔티티와 도메인 로직의 결합서비스 로직과 데이터베이스 강결합두 문제점을 통해 DDD와 Clean Architecture의 필요성을 느꼈습니다.이를 구현하기 위해 헥사고날 아키텍처를 도입하기로 결정했습니다.레이어드 아키텍처 → 헥사고날 아키텍처기존 패키지 구조- controller- service- entity- repository- dto  헥사고날 아키텍처 적용 범위헥사고날 아키텍처의 핵심은 포트와 어댑터를 통해 각 계층별 의존성을 줄여 변경이나 확장에 유리하도록 하는 것 입니다.따라서 아래와 같은 구조로 설계할 계획을 세웠습니다.패키지 구조- controller - controller.java - dto ..

문제 상황 친구 목록 동기화 과정에서, 이미 존재하는 친구 데이터를 업데이트하고 새 데이터는 추가로 저장해야 한다. 하지만 기존 친구 데이터가 업데이트되지 않고, 새로운 데이터로 중복 저장되는 문제가 발생. 원인 분석 JPA에서 엔티티를 업데이트하려면, 해당 엔티티가 영속성 컨텍스트에서 관리되어야 한다. 문제 지점: FriendEntity로 변환하는 과정에서 id가 누락되어, JPA는 이를 새로운 엔티티로 간주하고 저장. 결론: id 필드가 없는 경우, JPA는 해당 엔티티를 식별할 수 없어 영속성을 판단하지 못하고, 기존 데이터를 업데이트하지 못함. 문제 코드  동기화 로직 // 친구 목록 동기화 로직중 일부friendRepository .findByConsumerIdAndToConsume..

https://www.acmicpc.net/problem/1939골드3구현 방법1. 문제 조건N: 섬의 수 (2 ≤ N ≤ 10,000)M: 다리의 수 (1 ≤ M ≤ 100,000)C: 다리의 최대 중량 (1 ≤ C ≤ 1,000,000,000)두 섬 사이의 여러 경로 중, 한 번의 이동에서 옮길 수 있는 물품들의 최대 중량을 구해야 한다.다리마다 중량 제한이 존재하며, 이를 초과하면 경로로 사용할 수 없다.2. 완전탐색의 비효율성만약 BFS를 통해 모든 가능한 경로를 탐색하는 방식으로 접근하면:시간 복잡도는 최악의 경우 O(2^M)에 도달할 수 있다.이유: 각 다리를 선택하거나 선택하지 않는 경우의 수를 모두 고려해야 하기 때문이는 M=100,000일 경우 비현실적으로 많은 계산을 요구하기 때문에 적..

이번에 데이터베이스를 변경하면서 DDD와 Clean Architecture의 필요성을 느꼈습니다. 참고: 데이터베이스를 변경한 이유는 아래 포스팅에 있습니다. https://kdozlo.tistory.com/74  친구 정보, Redis에서 MySQL로 옮긴 이유상황현재 사용자의 친구 정보들을 "카카오톡 친구 API"를 통해 받은 뒤, redis에 저장해 놓고 있었다.하지만 "자신의 친구들 중 친한 친구를 표시할 수 있다."라는 기능을 제공하고 있고, 이 정보 또kdozlo.tistory.com 기존 방식의 문제점 1. DB 엔티티와 도메인 로직의 결합 기존 방식에서는 DB 엔티티(Friend)에 도메인 로직(예: toggleFavorite)을 포함하여 구현했습니다. 이로 인해 데이터베이스와 도메인 로직..