Algorithm
줄 세우기
문제
N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.
일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.
학생들의 번호는 1번부터 N번이다.
출력
첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.
예제 입력 1
3 2
1 3
2 3
예제 입력 2
4 2
4 2
3 1
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
// https://www.acmicpc.net/problem/2252
public class three2252 {
public void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer infoToken = new StringTokenizer(reader.readLine());
int students = Integer.parseInt(infoToken.nextToken());
int compares = Integer.parseInt(infoToken.nextToken());
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < students + 1; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i <compares; i++) {
StringTokenizer edgeToken = new StringTokenizer(reader.readLine());
int start = Integer.parseInt(edgeToken.nextToken());
int end = Integer.parseInt(edgeToken.nextToken());
adjList.get(start).add(end);
}
// 1. 진입 차수 정리
int[] inDegrees = new int[students + 1];
for (List<Integer> neighbors: adjList) {
for (int neighbor: neighbors) {
inDegrees[neighbor]++;
}
}
// 2. 진입 차수에 따른 첫 정점 정하기
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i < students + 1; i++) {
if (inDegrees[i] == 0) queue.offer(i);
}
// 3. Queue 를 이용 위상정렬 진행
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
result.add(node);
for (int neighbor: adjList.get(node)) {
inDegrees[neighbor]--;
if (inDegrees[neighbor] == 0) queue.offer(neighbor);
}
}
// 정답 출력
StringBuilder answer = new StringBuilder();
for (int node: result) answer.append(node).append(' ');
System.out.println(answer);
}
public static void main(String[] args) throws IOException {
new three2252().solution();
}
}선수 과목
문제
올해 Z대학 컴퓨터공학부에 새로 입학한 민욱이는 학부에 개설된 모든 전공과목을 듣고 졸업하려는 원대한 목표를 세웠다. 어떤 과목들은 선수과목이 있어 해당되는 모든 과목을 먼저 이수해야만 해당 과목을 이수할 수 있게 되어 있다. 공학인증을 포기할 수 없는 불쌍한 민욱이는 선수과목 조건을 반드시 지켜야만 한다. 민욱이는 선수과목 조건을 지킬 경우 각각의 전공과목을 언제 이수할 수 있는지 궁금해졌다. 계산을 편리하게 하기 위해 아래와 같이 조건을 간소화하여 계산하기로 하였다.
- 한 학기에 들을 수 있는 과목 수에는 제한이 없다.
- 모든 과목은 매 학기 항상 개설된다.
모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하는 프로그램을 작성하여라.
입력
첫 번째 줄에 과목의 수 N(1 ≤ N ≤ 1000)과 선수 조건의 수 M(0 ≤ M ≤ 500000)이 주어진다. 선수과목 조건은 M개의 줄에 걸쳐 한 줄에 정수 A B 형태로 주어진다. A번 과목이 B번 과목의 선수과목이다. A < B인 입력만 주어진다. (1 ≤ A < B ≤ N)
출력
1번 과목부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지를 한 줄에 공백으로 구분하여 출력한다.
예제 입력 1
3 2
2 3
1 2
예제 입력 2
6 4
1 2
1 3
2 5
4 5
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
//https://www.acmicpc.net/problem/14567
public class five14567 {
public void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer infoToken = new StringTokenizer(reader.readLine());
int lectures = Integer.parseInt(infoToken.nextToken());
int preReqs = Integer.parseInt(infoToken.nextToken());
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < lectures + 1; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < preReqs; i++) {
StringTokenizer reqToken = new StringTokenizer(reader.readLine());
int start = Integer.parseInt(reqToken.nextToken());
int end = Integer.parseInt(reqToken.nextToken());
adjList.get(start).add(end);
}
// 진입 차수 정리
int[] inDegrees = new int[lectures + 1];
for(List<Integer> neighbors: adjList) {
for(int neighbor: neighbors) {
inDegrees[neighbor]++;
}
}
// 진입 차수에 따른 시작 정점 결정
Queue<int[]> queue = new LinkedList<>();
for(int i = 1; i < lectures + 1; i++) {
if(inDegrees[i] == 0) queue.add(new int[] {i, 1});
}
// Queue를 가지고 순회
// Queue에 담기는 시점에 방문하고 있던 정점의 소요 시간 정보 기록
int[] firstSam = new int[lectures + 1];
while(!queue.isEmpty()) {
int[] lecture = queue.poll();
int node = lecture[0];
int semester = lecture[1];
firstSam[node] = semester;
for(int nextLec:adjList.get(node)) {
inDegrees[nextLec]--;
if(inDegrees[nextLec] == 0) {
queue.offer(new int[] {nextLec, semester + 1});
}
}
}
StringBuilder answer = new StringBuilder();
for (int i = 1; i < lectures + 1; i++) {
answer.append(firstSam[i]).append(' ');
}
System.out.println(answer);
}
public static void main(String[] args) throws IOException {
new five14567().solution();
}
}Backtracking
N-Queen
체스는 88개의 정사각형으로 이루어진 판에 놓여진 말을 다뤄 상대방의 왕을 잡는 게임이다. Queen은 가장 가치가 높은 말로 상하좌우 대각선 방향으로 칸의 제약 없이 이동할 수 있다. 88 크기의 체스판에 8개의 Queen을 배치한다고 할 때 서로를 위협하지 못하도록 배치하는 문제이다. 총 Queen을 놓을 수 있는 위치는 64개고 선택해야 하는 위치는 8개이다. 따라서 총 경우의 수는 약 4억 개이다. 그러나 실제 해의 개수는 92개밖에 없다. 백트래킹은 문제를 풀다가 종료 조건을 확인하고 더는 살피지 않는 방식을 통해 실제로 봐야 하는 경우의 수를 단축시키는 방법론이다. DFS에서 조건을 거는 것이다.
Backtracking
상태 공간 트리를 DFS로 탐색하는 중에 어느 노드에 도달했을 때, 해당 노드의 유망성을 검사하는 것이다. 해당 노드를 거쳐 가는 결과가 해가 된 가능성을 검사한다. 유망하지 않은 노드의 경우 최대 깊이까지 진행하지 않고 바로 부모 노드로 복귀한다.
문제
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.
N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N < 15)
출력
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
예제 입력 1
8
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//https://www.acmicpc.net/problem/9663
public class four9664 {
// 판을 int[][]로 다 구현하는 방법
// 아니면 각 줄에 어느 위치에 queeen이 존재하는지 기록하는 방법
private int[] queenPos;
// n
private int size;
// 몇 개의 queen을 뒀는지
private int count;
public int solution() throws IOException {
size = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
queenPos = new int[size];
count = 0;
setQueenPos(0);
return count;
}
private void setQueenPos(int row) {
// 전부 배치 완료된 경우
if(row == size) {
count++;
}
else for (int i = 0; i < size; i++) {
// row 번째 queen 위치는 순회 중인 i
queenPos[row] = i;
// 이번 줄에 배치한 결과가 조건에 부합하면 다음으로
if(checkQueen(row)) setQueenPos(row + 1);
}
}
// 유망성 조사
// 현재 배치가 요구사항을 만족하는지
private boolean checkQueen(int row) {
// 세로줄에 겹치는지
for (int i = 0; i < row; i++) {
if(queenPos[i] == queenPos[row]) return false;
else if(Math.abs(queenPos[i] - queenPos[row]) == row - i) return false;
}
// 가로선은 겹치지 않음
return true;
}
public static void main(String[] args) throws IOException {
System.out.println(new four9664().solution());
}
}Database
Entity 관계 설정
일반적으로 데이터베이스 테이블에서는 관계를 외래키를 이용해 표현한다. 아래 그림의 왼쪽 테이블의 제조사 ID는 오른쪽 테이블의 ID를 의미한다. 즉 자신의 테이블이 아닌 테이블의 Key를 외부의 키, 외래키라고 한다.
1:1 One to One 관계
한 테이블에 레코드 하나가 다른 테이블의 레코드 하나와 연관된 관계이다. 특정 데이터를 성능 또는 보안적 측면에서 나눌 때 사용한다.
N:1 Many to One 관계
한 테이블의 레코드 0개 이상이 다른 테이블의 레코드 하나와 연관된 관계이다. 일반적인 데이터베이스의 가장 흔한 관계이다. (게시글-댓글)
M:N Many to Many 관계
한 테이블의 레코드 0개 이상이 다른 테이블의 레코드 0개 이상과 연관된 관계이다. 양쪽 테이블의 PK를 Foreign Key로 가진 Join Table, Associative Table을 활용한다.
JPA
하나의 테이블에는 다른 테이블에 레코드를 넣지 못한다. 따라서 Foriegn Key 설정이 어려워진다. 따라서 테이블 데이터를 표현하기 위해 ORM이 등장했다. ORM을 사용하면 테이블간 관계를 Entity의 필드로 표현이 가능해진다. 내가 연관 관계를 맺고 싶은 객체를 언급하고 Annotation을 통해 관계를 설정해 주는 것이 ORM이다.
@Entity
public class Article {
private String title;
@Lob
private String content;
// 아래 User와 Comment는 다른 Entity 클래스 입니다.
private User writer;
private List<Comment> comments;
}Many to One & One to Many
이 관계를 JPA로 표현해 보자. 먼저 관계 설정이 되지 않은 각각의 Entity부터 만들어 준다.
@Entity
public class InstructorEntity {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;
private String firstName;
private String lastName;
}@Entity
public class LectureEntity {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;
private String course_name;
private Integer startTime;
private Integer endTime;
}이후 관계 설정을 해 주기 위해 N에 위치하는 Lecture에 Instructor를 넣고 @ManyToOne Annotation을 붙여 준다. 만약 FK 칼럼의 이름을 바꾸고 싶다면 @JoinColumn(name = "instructor") 등으로 설정할 수 있다.
@Entity
@Table(name = "lecture")
public class LectureEntity {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;
private String course_name;
private Integer startTime;
private Integer endTime;
@ManyToOne
private InstructorEntity instructor;
}이후 레포지토리와 컨트롤러를 만들어 주고 강의에 강사를 배정하는 기능으로 @PutMapping을 진행해 본다.
// 강의에 강사를 배정한다
@PutMapping("{id}/instructor/{instructorId}")
// 응답 바디가 없을 것이다
@ResponseStatus(HttpStatus.NO_CONTENT)
public void updateLectureInstructor(
@PathVariable("id") Long id,
@PathVariable("instructorId") Long instructorId
) {
Optional<LectureEntity> optionalLectureEntity
= lectureRepository.findById(id);
if(optionalLectureEntity.isEmpty()) {
throw new ResponseStatusException(HttpStatus.NOT_FOUND);
}
Optional<InstructorEntity> optionalInstructorEntity
= instructorRepository.findById(instructorId);
if(optionalInstructorEntity.isEmpty()) {
throw new ResponseStatusException(HttpStatus.NOT_FOUND);
}
LectureEntity lecture = optionalLectureEntity.get();
InstructorEntity instructor = optionalInstructorEntity.get();
lecture.setInstructor(instructor);
lectureRepository.save(lecture);
}이번에는 id 강의에 강사를 반환하는 엔드포인트를 만들어 보자.
// id 강의의 강사를 반환하는 엔드포인트
@GetMapping("{id}/instructor")
public void readLectureInstructor(
@PathVariable("id") Long id
) {
Optional<LectureEntity> optionalLectureEntity
= lectureRepository.findById(id);
if(optionalLectureEntity.isEmpty()){
throw new ResponseStatusException(HttpStatus.NOT_FOUND);
}
log.info(optionalLectureEntity.get().getInstructor().toString());
}이때 @OneToMany와 @ManyToOne이 모두 붙어 있으면 각각 다른 관계로 인식할 수 있다. 따라서 하나의 관계임을 알려 주기 위해 둘 중 하나에 mapped by를 붙여 주면 된다. 양방향 연결에서 중요하게 생각해야 하는 부분이다.
@Entity
@Table(name = "lecture")
public class LectureEntity {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;
private String course_name;
private Integer startTime;
private Integer endTime;
@ManyToOne
private InstructorEntity instructor;
}
@Entity
public class LectureEntity {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;
private String course_name;
private Integer startTime;
private Integer endTime;
@OneToMany(mappedBy = "instructor")
private List<LectureEntity> lectures;
}이제 Instructor에서도 Lecture에 접근이 가능해졌으니 Controller를 만들어 보자.
@Slf4j
@RestController
@RequestMapping("instructor")
@RequiredArgsConstructor
public class InstructorController {
private final InstructorRepository instructorRepository;
private final LectureRepository lectureRepository;
@GetMapping("{id}/lectures")
public void readInstructorLectures(@PathVariable("id") Long id) {
Optional<InstructorEntity> optionalInstructorEntity
= instructorRepository.findById(id);
if(optionalInstructorEntity.isEmpty()) {
throw new ResponseStatusException(HttpStatus.NOT_FOUND);
}
for(LectureEntity lecture:optionalInstructorEntity.get().getLectures()) {
log.info(lecture.getName());
}
}
}
위와 같이 잘 접근이 가능하다.
주의할 점이 있다면 양방향으로 접근이 가능할 때 오른쪽에서 왼쪽 객체의 toString을 호출하면 왼쪽 객체에서는 다시 오른쪽 toString을 호출하는 식으로 쌓이고 쌓여서 Stack Overflow가 발생할 수도 있다.
Many To Many
테이블의 레코드들이 양방향으로 복수의 연관 관계를 가지는 것이다. 대표적으로 좋아요나 학생과 강의의 관계를 예시로 들 수 있다. 이를 테스트해 보기 위해 먼저 StudentEntity를 만들어 준다.
import jakarta.persistence.*;
import lombok.Data;
@Data
@Entity
@Table(name = "student")
public class StudentEntity {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;
private String firstName;
private String lastName;
}이후 서로에게 관계를 설정해 준다.
@Data
@Entity
@Table(name = "student")
public class StudentEntity {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;
private String firstName;
private String lastName;
**@ManyToMany
private List<LectureEntity> attending;**
}
@Data
@Entity
@Table(name = "lecture")
public class LectureEntity {
@Id
@GeneratedValue(strategy = GenerationType.IDENTITY)
private Long id;
private String name;
private String day;
private Integer startTime;
private Integer endTime;
@ManyToOne
private InstructorEntity instructor;
**@ManyToMany(mappedBy = "attending")
private List<StudentEntity> stuents;**
}Join table이 만들어진 것을 확인할 수 있다.
이후 Controller를 만들어서 실행해 본다. 학생을 강의에 등록시키는 기능이다.
@PutMapping("{id}/lectures/{lectureId}")
public void updateStudentLectures(
@PathVariable("id") Long id,
@PathVariable("lectureId") Long lectureId
) {
Optional<StudentEntity> optionalStudentEntity
= studentRepository.findById(id);
if(optionalStudentEntity.isEmpty()){
throw new ResponseStatusException(HttpStatus.NOT_FOUND);
}
Optional<LectureEntity> optionalLectureEntity =
lectureRepository.findById(lectureId);
if(optionalLectureEntity.isEmpty()){
throw new ResponseStatusException(HttpStatus.NOT_FOUND);
}
StudentEntity student = optionalStudentEntity.get();
LectureEntity lecture = optionalLectureEntity.get();
student.getAttending().add(lecture);
studentRepository.save(student);
lecture.getStudents().add(student);
lectureRepository.save(lecture);
}
잘 읽었습니다. 좋은 정보 감사드립니다.