🤔 상속관계 매핑? 관계형 데이터베이스는 상속관계라는 개념이 없다. 하지만 슈퍼타입과 서브타입 관계라는 모델링 기법이 객체의 상속과 유사하기 때문에 이점을 이용하여 상속관계 매핑을 하고있다. (객체의 상속 구조와 DB의 슈퍼타입 서브타입 관계를 매핑) DB에서 슈퍼타입과 서브타입의 논리모델을 디자인 했을때 실제 물리 모델로 구현하는 전략은 3가지가 있다. ✔ 조인전략(JOINED) 가장 정규화된 방법으로 각테이블을 join하는 방식으로 데이터 를 저장하게되며 데이터가 정규화 되어 저장되기 때문에 중복되는 데이터(name, price)를 줄일 수 있고, 객체의 관계와 가장 유사하다. @Inheritance(strategy = InheritanceType.JOINED)과 객체의 상속(extends)을 사용하..
🤔 Brute force 브루트포스 알고리즘? '무식한 힘' 으로 해석할 수 있겠습니다, 이 뜻 처럼 주어진 문제를 무식하게 하나하나 탐색하는 알고리즘 입니다. 모든 경우의 수를 전부 탐색하여 조건에 맞는 답을 찾기 때문에 정확한 답을 보장합니다. 하지만 모든 경우의 수를 탐색하기 때문에 시간복잡도가 높다는 단점이 있습니다. 그렇기 때문에 브루트포스 알고리즘은 시간복잡도를 고려하여 사용해야합니다. 또한 브루트포스 알고리즘은 정형화된 틀이 없기때문에 주어진 문제 유형에 따라 다양한 방법으로 풀이합니다. 단순 Brute force ( for문 ) 재귀호출 비트마스크 순열 DFS / BFS 💡 하지만 비효율적으로 보이는 브루트포스 알고리즘을 왜 사용할까요? 입력되는 범위가 작고, 탐색해야할 경우의 수가 적은 ..
✔ 문제 난이도 : 골드5 🥇 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net ✔ 문제 풀이 주어진 예제 처럼 첫째 줄에 NxN의 배열에 해당하는 N이 주어지고 각 칸에 R,G,B중 하나를 색칠한 그림이 둘째 줄부터 주어집니다. 이때 각 색들이 차지하는 구역과, 적록색약인 사람이 봤을 때의 구역을 구하는 문제입니다. 적록색약은 R(빨강)과 G(초록)이 잘 구분되지 않기 때문에 같은 구역으로 생각하여 카운트하도록 코드를 짠다면 쉽게 풀 수 있습니다. 💡 단순하게 R과 G일 경우 조건을 주어 탐색을 진행하려..
✔ 연관관계 매핑시 고려사항 3가지 다중성 : @ManyToOne, @OneToMany, @OneToOne, @ManyToMany 단방향, 양방향 연관계의 주인 어노테이션을 사용하여 관계를 정확히 매핑해주고, 객체(Entity)를 단방향 또는 양방향으로 사용할지 충분히 고려한 후 양방향으로 설정 했다면 연관관계 주인을 설정함으로써 한쪽에서만 등록,수정이 일어날 수 있도록 한다. 🔎 @ManyToOne 다대일 [N:1] 💡 단방향 가장 많이 사용되는 연관관계로 한쪽(Member)에서만 조회, 등록, 수정 하도록 매핑 💡 양방향 양방향으로 설정하게 되면 Member와 Team객체에 서로 참조할 수 있는 필드를 생성하여 각각의 관계를 설정해준다. 이렇게되면 양쪽에서 등록, 수정이 일어날 수 있기 때문에 연관관..
🤔 Floyd-Warshall 플로이드-와샬 알고리즘? 그래프에 있는 모든 정점에 대해 각 정점들이 다른 정점들까지 도달하기 위해 필요한 모든 최단 거리를 구할때 사용합니다. 플로이드-와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행하는 특징이 있습니다. 즉, 정점 A, 정점B 까지의 최단 거리를 구하기 위해 중간에서 거쳐갈 수 있는 모든 정점들을 확인해보고 그 중 최단 거리의 경로를 찾습니다. (플로이드 와샬은 다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬로 표현하여 최단 거리를 계산합니다.) ✔ 시간복잡도 3중 for문을 통해 거쳐가는 정점을 이용하여 그래프를 탐색하기 때문에 O(n^3)의 시간복잡도를 갖습니다. ✔ 탐색 방법 문제와 함께 플로이드-와샬 알고리즘의 탐색방법을 살펴보..
✔ 문제 난이도 : 실버 🥈 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net ✔ 문제 풀이 임의의 두 사람이 최소 몇 단계만에 이어질 수 있는지 계산하는 문제입니다. 즉, 정점에서 다른 정점까지의 최단거리들을 계산하여 최단거리들의 합이 가장 낮은 사람을 출력 해야합니다. BFS와 DFS 모두 이용 가능하지만 DFS로 풀 경우 시간 초과가 났습니다.😭 하지만 풀이는 가능함으로 BFS와 DFS모두 풀어보겠습니다. 📌 설명은 코드 주석에 있습니다! 🔎 BFS 풀이 i..
