✔ 문제 난이도 : 실버2 🥈 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net ✔ 문제 풀이 입력값의 범위가 n(1 ≤ n ≤ 100,000)이기 때문에 단순히 이중 for문을 통해 계산하게 되면 시간초과가 됩니다. 동적 계획법(DP)을 적용하여 시간복잡도를 낮추어 풀어야합니다. 위 문제에서는 '연속되는 몇 개의 수'라는 조건이 주어졌기 때문에 연속되는 수의 누적합을 배열에 저장하여 비교하면서 중복되는 연산을 줄일 수 있습니다. Bottom-Up과 Top..
✔ 문제 난이도 : 골드4 🥇 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net ✔ 문제 풀이 실제 스도쿠 규칙과 같이 가로줄, 세로줄, 작은 정사격형 안의 수들이 1부터 9까지 하나씩 있어야합니다. 숫자가 입력 되었을 때 가로줄, 세로줄, 작은 정사각형을 탐색하여 중복된 숫자가 있는지 체크하는 로직은 쉽게 머리속에 떠올릴 수 있었지만, 어떤 흐름으로 어떤 조건을 사용하여 재귀호출하며 백트래킹 과정을 거칠지는 많이 고민이 필요한 문제였습니다. 🔎 isChecked 가로와 세로체크는 모든 9개의 범위를 탐색하여 ..
✔ 프록시(Proxy) 만약 비즈니스 로직에서 Member에 대한 정보를 가지고올 때 .find()를 통해 Member Entity와 연관관계 매핑된 Entity를 join하여 한번에 다 가지고온다. 하지만 Member에 대한 정보만 쓰려는 케이스는 불필요한 다른관계의 Entity정보까지 join을 통해 가지고오게 되는데 둘 다 쓰는 케이스에서는 편리하겠지만 Member에대한 정보만 사용하는 케이스에서는 낭비가 될 수 있다. 이러한 불필요한 낭비를 JPA는 프록시와 지연로딩을 사용하여 해결하고 있다. 실제클래스를 상속 받아서 만들어지고 겉 모양이 같다. EntityManager.find() - 데이터베이스를 통해 실제 엔티티 객체 조회 EntityManager.getReference() - 데이터베이스 ..
🤔 시작하기 전에 개발 과정에서 만난 고민 builder?, Spring Data JPA?, DTO? [SpringBoot + JPA 게시판 만들기] 개발 과정에서 만난 고민 builder?, Spring Data JPA?, DTO? 🤔 고민 강의, GPT, 구글링을 하며 혼자서 개발하다보니 계속해서 새로운 문제에 직면하게 되었다. 객체를 생성할때에는 어떤 방법이 더 좋지? 인터페이스를 만들고 구현체를 만들어 역할과 구 average1.tistory.com 1. 객체 생성시 Builder 패턴을 사용하여 가독성을 높이고 일관성과 불변성을 해칠 위험을 제거했습니다. 2. Entity와 DTO의 범위를 Service계층 까지로 설정하였습니다, 즉 변환( Entity -> DTO, DTO -> Entity )..
🤔 상속관계 매핑? 관계형 데이터베이스는 상속관계라는 개념이 없다. 하지만 슈퍼타입과 서브타입 관계라는 모델링 기법이 객체의 상속과 유사하기 때문에 이점을 이용하여 상속관계 매핑을 하고있다. (객체의 상속 구조와 DB의 슈퍼타입 서브타입 관계를 매핑) DB에서 슈퍼타입과 서브타입의 논리모델을 디자인 했을때 실제 물리 모델로 구현하는 전략은 3가지가 있다. ✔ 조인전략(JOINED) 가장 정규화된 방법으로 각테이블을 join하는 방식으로 데이터 를 저장하게되며 데이터가 정규화 되어 저장되기 때문에 중복되는 데이터(name, price)를 줄일 수 있고, 객체의 관계와 가장 유사하다. @Inheritance(strategy = InheritanceType.JOINED)과 객체의 상속(extends)을 사용하..
🤔 Brute force 브루트포스 알고리즘? '무식한 힘' 으로 해석할 수 있겠습니다, 이 뜻 처럼 주어진 문제를 무식하게 하나하나 탐색하는 알고리즘 입니다. 모든 경우의 수를 전부 탐색하여 조건에 맞는 답을 찾기 때문에 정확한 답을 보장합니다. 하지만 모든 경우의 수를 탐색하기 때문에 시간복잡도가 높다는 단점이 있습니다. 그렇기 때문에 브루트포스 알고리즘은 시간복잡도를 고려하여 사용해야합니다. 또한 브루트포스 알고리즘은 정형화된 틀이 없기때문에 주어진 문제 유형에 따라 다양한 방법으로 풀이합니다. 단순 Brute force ( for문 ) 재귀호출 비트마스크 순열 DFS / BFS 💡 하지만 비효율적으로 보이는 브루트포스 알고리즘을 왜 사용할까요? 입력되는 범위가 작고, 탐색해야할 경우의 수가 적은 ..
