이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.
문제 설명
코드
첫 번째 코드(정렬 알고리즘을 이용한 방법)
package inflearn_algorithm.chapter3;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class sec03_01 {
public static int[] solution(int [] arr1, int [] arr2) {
int[] mergeArr = new int[arr1.length + arr2.length];
for (int i = 0; i < mergeArr.length; i++) {
if(i < arr1.length) mergeArr[i] = arr1[i];
else mergeArr[i] = arr2[i - arr1.length];
}
Arrays.sort(mergeArr);
return mergeArr;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr1 = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) arr1[i] = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(br.readLine());
int[] arr2 = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; ++i) arr2[i] = Integer.parseInt(st.nextToken());
for (int i : solution(arr1, arr2)) System.out.print(i + " ");
}
}
두 번째 코드(투 포인터를 이용한 방법)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class sec03_01 {
public static int[] solution(int[] arr1, int[] arr2) {
int[] mergeArr = new int[arr1.length + arr2.length];
int ptr1 = 0, ptr2 = 0, i = 0;
while (ptr1 < arr1.length && ptr2 < arr2.length) {
if (arr1[ptr1] <= arr2[ptr2]) mergeArr[i++] = arr1[ptr1++];
else mergeArr[i++] = arr2[ptr2++];
}
while (ptr1 < arr1.length) mergeArr[i++] = arr1[ptr1++];
while (ptr2 < arr2.length) mergeArr[i++] = arr2[ptr2++];
return mergeArr;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr1 = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) arr1[i] = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(br.readLine());
int[] arr2 = new int[M];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; ++i) arr2[i] = Integer.parseInt(st.nextToken());
for (int i : solution(arr1, arr2)) System.out.print(i + " ");
}
}
설명
두 번째 코드에 대한 설명
ptr1과 ptr2는 각각 arr1과 arr2의 현재 위치를 가리키며, 두 배열의 끝에 도달할 때까지 반복된다.
결과 배열인 mergeArr는 arr1과 arr2의 길이를 합친 크기로 초기화된다.
두 배열의 요소를 비교하며 작은 값을 결과 배열에 추가하고, 포인터를 증가시킨다.
한 배열의 모든 요소를 처리한 후 다른 배열의 나머지 요소들을 모두 결과 배열에 추가한다.
이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.
문제 설명
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class sec02_12 {
public static int solution(int N, int M, int[][] arr){
int count = 0;
// 순위를 저장할 배열
int[][] rank = new int[M][N + 1];
// 각 테스트에서 학생들의 순위를 미리 계산
for (int k = 0; k < M; ++k)
{
for (int s = 0; s < N; ++s) rank[k][arr[k][s]] = s;
}
// 학생 쌍 (i, j) 에 대해 비교
for (int i = 1; i <= N; ++i) {
for (int j = 1; j <= N; ++j)
{
int temp = 0;
for (int k = 0; k < M; ++k) if (rank[k][i] < rank[k][j]) ++temp;
if (temp == M) ++count;
}
}
return count;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[][] arr = new int[M][N];
for(int i = 0; i < M; ++i)
{
st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; ++j) arr[i][j] = Integer.parseInt(st.nextToken());
}
System.out.println(solution(N, M, arr));
}
}
설명
rank 배열은 각 테스트(M)에서 각 학생(N)의 순위를 저장한다.
rank[k][x]는 k번째 테스트에서 x 학생의 순위를 의미한다.
for (int k = 0; k < M; ++k) {
for (int s = 0; s < N; ++s) rank[k][arr[k][s]] = s;
}
각 테스트에 대해, 학생들의 순위를 계산하고 rank 배열에 저장한다.
arr[k][s]는 k번째 테스트에서 s번째 순위인 학생의 번호이다.
예를 들어, rank[0][3] = 2라면, 첫 번째 테스트에서 3번 학생은 세 번째 순위라는 뜻이다.
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= N; ++j)
{
int temp = 0;
for (int k = 0; k < M; ++k) if (rank[k][i] < rank[k][j]) ++temp;
if (temp == M) ++count;
}
}
모든 학생 쌍 (i, j)에 대해 i가 모든 테스트에서 j보다 높은 순위에 있는지를 확인한다.
이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.
문제 설명
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int solution(int n, int[][] arr)
{
int answer = 0, max = 0;
// 각 학생 i에 대해 반복
for(int i = 1; i <= n; ++i)
{
int count = 0;
// 다른 모든 학생 j와 비교
for(int j = 1; j <= n; ++j)
{
// 5년 동안 같은 반이었던 적이 있는지 확인
for(int k = 1; k <= 5; ++k)
{
if(arr[i][k] == arr[j][k])
{ // 같은 반이었던 경우
count++;
break; // 더 이상 확인할 필요 없이 다음 학생으로 넘어감
}
}
}
// 최대값 갱신
if(count > max)
{
max = count;
answer = i;
}
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N + 1][6]; // 1-based 인덱스 사용을 위해 배열 크기 설정
for(int i = 1; i <= N; ++i)
{
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 1; j < 6; j++) arr[i][j] = Integer.parseInt(st.nextToken());
}
System.out.println(solution(N, arr));
}
}
이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.
문제 설명
코드
처음 작성한 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class sec02_09 {
public static int solution(int N, int[][] numArr) {
int rightUp = 0;
for(int i = 0; i < N; ++i)
{
int colSum = 0;
for(int j = 0; j < N; ++j)
{
colSum += numArr[j][i];
if(i + j == N - 1) rightUp += numArr[i][j];
}
numArr[N][i] = colSum;
}
int max = 0;
for(int i = 0; i < N; ++i) if(max < numArr[i][N]) max = numArr[i][N];
for(int i = 0; i < N; ++i) if(max < numArr[N][i]) max = numArr[N][i];
if(max < rightUp) max = rightUp;
return max;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N + 1][N + 1];
int rightDown = 0;
for(int i = 0; i < N; ++i) {
StringTokenizer st = new StringTokenizer(br.readLine());
int rowSum = 0;
for(int j = 0; j < N; ++j)
{
arr[i][j] = Integer.parseInt(st.nextToken());
rowSum += arr[i][j];
if(i == j) rightDown += arr[i][j];
}
arr[i][N] = rowSum;
}
arr[N][N] = rightDown;
System.out.println(solution(N, arr));
}
}
개선한 코드
package inflearn_algorithm.chapter2;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class sec02_09 {
public static int solution(int N, int[][] numArr) {
int max = 0;
int rightUp = 0;
int rightDown = 0;
for (int i = 0; i < N; ++i)
{
int rowSum = 0;
int colSum = 0;
for (int j = 0; j < N; ++j)
{
rowSum += numArr[i][j];
colSum += numArr[j][i];
if (i == j) rightDown += numArr[i][j];
if (i + j == N - 1) rightUp += numArr[i][j];
}
max = Math.max(max, rowSum);
max = Math.max(max, colSum);
}
max = Math.max(max, rightDown);
max = Math.max(max, rightUp);
return max;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N][N];
for (int i = 0; i < N; ++i)
{
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; ++j) arr[i][j] = Integer.parseInt(st.nextToken());
}
System.out.println(solution(N, arr));
}
}
개선된 코드에 대한 설명
초기 변수 설정 max 변수는 최댓값을 저장하기 위해 사용된다. rightUp 변수는 오른쪽 위 대각선의 합을 저장한다. rightDown 변수는 오른쪽 아래 대각선의 합을 저장한다.
이중 반복문을 통한 합 계산 외부 반복문 for (int i = 0; i < N; ++i)는 행을 기준으로 반복한다. 내부 반복문 for (int j = 0; j < N; ++j)는 열을 기준으로 반복한다. rowSum 변수는 현재 행의 합을 계산한다. colSum 변수는 현재 열의 합을 계산한다. if (i == j) 조건문을 통해 오른쪽 아래 대각선(rightDown)의 합을 계산한다. if (i + j == N - 1) 조건문을 통해 오른쪽 위 대각선(rightUp)의 합을 계산한다.
최대값 갱신 각 행의 합(rowSum)과 각 열의 합(colSum)을 계산한 후, 현재의 max 값과 비교하여 최대값을 갱신한다.
대각선의 합과 비교 오른쪽 아래 대각선의 합(rightDown)과 오른쪽 위 대각선의 합(rightUp)을 계산한 후, 현재의 max 값과 비교하여 최대값을 갱신한다.
이 글은 인프런 김영한님의 Spring 강의를 바탕으로 개인적인 정리를 위해 작성한 글입니다.
객체 지향 프로그래밍(OOP) 패러다임과 관계형 데이터베이스(RDB) 패러다임 간의 불일치는 종종 객체-관계 불일치(O/R Impedance Mismatch)라고 불린다.
이는 객체 모델과 관계형 데이터 모델 간의 구조적 차이에서 비롯된다. 이러한 불일치로 인해 양방향 매핑을 구현할 때 다양한 문제와 고려사항이 발생한다.
객체 모델은 상속을 자연스럽게 지원하지만, 관계형 데이터베이스에서는 이를 직접적으로 지원하지 않는다.
객체 모델에서는 객체 간의 연관관계를 직접 참조로 표현할 수 있지만, 관계형 데이터베이스에서는 외래 키(Foreign Key)를 사용해 연관관계를 표현해야 한다.
객체는 참조 동등성을 사용하지만, 데이터베이스에서는 기본 키를 사용하여 행의 동등성을 판단한다.
객체 모델에서는 필요한 데이터를 즉시 로딩할 수 있지만, 데이터베이스에서는 조인을 통해 데이터를 가져와야 한다.
이러한 이유때문에 객체지향 프로그래밍에서 객체 그래프 탐색을 할 수 없다.
즉, 객체지향다운 프로그래밍을 할 수 없다.
JPA 는 이를 해결해주는 매커니즘을 제공한다.
연관관계의 주인
객체의 두 관계 중 하나를 연관관계의 주인으로 지정
연관관계의 주인만이 외래 키를 관리(등록, 수정)
주인이 아닌 쪽은 읽기만 가능
주인은 MappedBy 속성 사용 불가능
주인이 아니면 MappedBy 속성으로 주인 지정
MappedBy 속성은 양방향 연관관계일때만 사용한다.
MEMBER 테이블과 TEAM 테이블의 관계를 살펴보면, MEMBER 테이블은 N, TEAM 테이블은 1의 관계이다.
즉 Member 테이블과 TEAM 테이블은 1:N 관계이다.
멤버 한명은 하나의 팀에 소속될 수 있지만, 하나의 팀은 여러 멤버가 소속될 수 있다.
여기서 연관관계의 주인은 Member 테이블로 정해야 한다.
외래 키가 있는 곳으로 주인으로 정해야 함.
즉, N의 관계가 있는 곳을 주인으로 정해야 한다.
이와 같은 기준으로 연관관계의 주인을 정해야한다.
단방향 연관관계
JPA에서 단방향 연관관계 매핑은 엔티티 간의 관계를 설정하는 방식 중 하나로, 한쪽 엔티티만 다른 엔티티를 참조하는 구조이다.
@Entity
public class Member {
@Id
private Long id;
@Column(name = "USERNAME")
private String name; private int age;
@Column(name = "TEAM_ID")
private Long teamId;
@ManyToOne //Member 입장에서 Team과의 관계는 ManyToOne
@JoinColumn(name = "TEAM_ID", nullable = false)
private Team team;
//getter and setter...
}
@ManyToOne 관계는 여러 개의 엔티티가 하나의 엔티티와 관계를 맺는 경우에 사용된다.
MEMBER 테이블이 연관관계의 주인이므로 Member 클래스에 @ManyToOne 애노테이션을 추가했다.
연관관계 주인이 아닌 Team 클래스에는 단방향 연관관계에서는 @ManyToOne 애노테이션을 추가하지 않는다.
이렇게 설정하면 member 객체에서 team 객체로 단방향 객체 그래프 탐색을 할 수 있다.
//팀 저장
Team team = new Team();
team.setName("TeamA");
em.persist(team);
//회원 저장
Member member = new Member();
member.setName("member1");
member.setTeam(team); //단방향 연관관계 설정, 참조 저장
em.persist(member);
//조회
Member findMember = em.find(Member.class, member.getId());
//참조를 사용해서 연관관계 조회
Team findTeam = findMember.getTeam();
// 새로운 팀B
Team teamB = new Team();
teamB.setName("TeamB");
em.persist(teamB);
// 회원1에 새로운 팀B 설정
member.setTeam(teamB); //단방향 연관관계 설정, 참조 저장
양방향 연관관계
양방향 매핑은 두 개의 엔티티가 서로를 참조하는 관계를 말한다.
객체 모델에서는 서로를 참조하는 두 객체가 있을 수 있지만, 데이터베이스에서는 이러한 관계를 설정하기 위해 외래 키를 사용해야 한다.
양방향 매핑을 통해 두 엔티티 간의 탐색이 양방향으로 가능하게 된다.
양방향 매핑을 통한 객체의 양방향 관계는 사실 양방향 관계가 아니라 서로 다른 단방향 관계 2개이다.
객체를 양방향으로 참조하려면 단방향 연관 관계를 2개 만들어야 하기 때문이다.
객체 연관관계 = 2개
회원 -> 팀 연관관계 1개(단방향)
팀 -> 회원 연관관계 1개(단방향)
테이블 연관관계 = 1개
회원 <-> 팀의 연관관계 1개(양방향)
양방향 매핑 규칙
객체의 두 관계 중 하나를 연관관계의 주인으로 지정
연관관계의 주인만이 외래 키를 관리(등록, 수정)
주인이 아닌 쪽은 읽기만 가능
주인은 MappedBy 속성 사용 불가능
주인이 아니면 MappedBy 속성으로 주인 지정
MappedBy 속성은 양방향 연관관계일때만 사용한다.
@Entity
public class Member {
@Id
private Long id;
@Column(name = "USERNAME")
private String name; private int age;
@Column(name = "TEAM_ID")
private Long teamId;
@ManyToOne //Member 입장에서 Team과의 관계는 ManyToOne
@JoinColumn(name = "TEAM_ID") //외래키 지정
private Team team;
//getter and setter...
}
@Entity
public class Team {
private String name;
@Id @GeneratedValue
private Long id;
@OneToMany(mappedBy = "team") //Team 입장에서는 Member와 OneToMany
List<Member> members = new ArrayList<Member>();
//getter and setter...
}
Member 테이블은 연관관계의 주인이므로 아무 속성 없이 @ManyToOne 애노테이션을 사용한다.
또한, 외래키를 통해 JPA가 JOIN을 하기 때문에 @JoinColumn를 통해 외래키를 지정해주어야 한다.
연관관계 주인이 아닌 Team 테이블은 MappedBy 속성을 사용한다.(@OneToMany(mappedBy = "team"))
양방향 매핑시 많이 하는 실수
연관관계의 주인에 값을 입력하지 않음.
Team team = new Team();
team.setName("TeamA");
em.persist(team);
Member member = new Member();
member.setName("member1");
//역방향(주인이 아닌 방향)만 연관관계 설정
team.getMembers().add(member);
em.persist(member);
TEAM 클래스는 연관관계의 주인이 아니다.
따라서 주인이 아닌 쪽은 읽기만 가능하기 때문에 제대로 입력이 되지 않는다.
따라서 양방향 매핑시 아래의 코드와 같이 연관관계의 주인에 값을 입력해야 한다.
Team team = new Team();
team.setName("TeamA");
em.persist(team);
Member member = new Member();
member.setName("member1");
member.setTeam(team); //연관관계의 주인에 값 설정
em.persist(member);
주의 사항
양쪽 모두 값 설정
순수 객체 상태를 고려해서 양방향 매핑시 주인인 쪽과 주인이 아닌 쪽 모두 값을 설정해주는 것이 좋다.
Team team = new Team();
team.setName("TeamA");
em.persist(team);
Member member = new Member();
member.setName("member1");
team.getMembers().add(member); //역방향(주인이 아닌 방향)만 연관관계 설정
member.setTeam(team); //연관관계의 주인에 값 설정
em.persist(member);
양쪽 모두 값을 설정해주는 것을 편하게 해주는 연관 관계 편의 메서드를 이용하면 좋다.
편의 메서드는 두 방향 어느곳에 만들어도 상관없지만, 한 방향에만 만들어야 한다.
즉, 두 클래스 모두 편의 메서드를 만들면 안되고, 둘 중 하나의 클래스에만 있어야 한다.
Member 클래스에 편의 메서드를 만들 시
@Entity
public class Member {
@Id
private Long id;
@Column(name = "USERNAME")
private String name;
private int age;
@Column(name = "TEAM_ID")
private Long teamId;
@ManyToOne //Member 입장에서 Team과의 관계는 ManyToOne
@JoinColumn(name = "TEAM_ID")
private Team team;
//편의 메서드 정의
public void addTeam(Team team){
this.team = team;
team.getMembers().add(this);
}
//getter and setter...
}
Team 클래스에 편의 메서드를 만들 시
@Entity
public class Team {
private String name;
@Id @GeneratedValue
private Long id;
@OneToMany(mappedBy = "team")
List<Member> members = new ArrayList<Member>();
//편의 메서드 정의
public void addMember(Member member){
member.setTeam = this;
this.members.add(member);
}
//getter and setter...
}
무한루프 조심
양방향 매핑시에 무한 루프를 조심해야 한다.
양방향 매핑을 사용할 때 무한 루프가 발생할 수 있는 이유는, 두 엔티티가 서로를 참조할 때 객체를 직렬화하거나 문자열로 변환하는 과정에서 무한 재귀 호출이 발생할 수 있기 때문이다. 이 문제는 특히 toString() 메서드, Lombok, JSON 생성 라이브러리에서 자주 발생한다.
양방향 매핑을 사용하는 엔티티 클래스에서 toString() 메서드를 오버라이드할 때, 양쪽 엔티티가 서로를 참조하는 필드를 포함하면 무한 루프가 발생할 수 있다.
Lombok을 사용하여 @ToString 어노테이션을 적용하면, 자동으로 toString() 메서드를 생성한다. 양방향 관계 필드를 포함한 toString() 메서드가 생성되면 동일한 문제가 발생할 수 있다.
Jackson과 같은 JSON 생성 라이브러리는 객체를 JSON으로 직렬화할 때 양방향 관계를 처리할 수 없다. 양쪽 엔티티가 서로를 참조하고 있으면 무한 루프가 발생할 수 있다.
일반적으로 스프링 애플리케이션에서 엔티티(Entity)를 JSON으로 변환할 때 DTO(Data Transfer Object)를 사용하는 것이 좋은 방법이다. 이는 여러 가지 이유로 권장되며, 특히 양방향 연관 관계와 같은 문제를 해결하고, 보안 및 성능 측면에서도 많은 이점을 제공한다.
양방향 매핑 정리
단방향 매핑만으로도 이미 연관관계 매핑은 완료되었다.
양방향 매핑은 반대 방향으로 조회(객체 그래프 탐색) 기능이 추가된 것 뿐이다.
JPQL에서 역방향으로 탐색할 일이 많다.
그렇기 때문에 최대한 단방향 매핑을 이용하고, 양방향은 필요할 때 추가하면 된다.
연관 관계의 주인은 비즈니스 로직을 기준으로 연관관계의 주인을 선택하면 안되고, 외래 키의 위치를 기준으로 정해야 한다.
