분류 전체보기

[백준, Java] 1707번 : 이분 그래프

🔗 문제 링크 https://www.acmicpc.net/problem/1707 🤔 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 😮 문제 해결 방법 이분 그래프는 문제에 나와 있는 것 처럼 정점끼리 이어진 그래프를 하나의 집합으로 보고 서로 연결된 정점끼리는 다른 두 그룹으로 속하게 하는 그래프를 말한다. 따라서, 이분 그래프를 판별하는 방법은 다음과 같다. 색칠되지 않은 모든 정점에 대해 BFS를 진행한다. BFS의 시작 정점을 임의의 색상으로 색칠한다. ..

[백준, Java] 1806번 : 부분합

🔗 문제 링크 https://www.acmicpc.net/problem/1806 🤔 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 😮 문제 해결 방법 아래의 그림과 같이 num 배열이 주어지고 다음 인덱스로 갈 때 마다 이전 값을 누적해서 더해주는 sum배열을 생성한다. 각 인덱스의 누적합을 더해준 sum배열의 동작에 대해 알아야한다. 예를 들어, sum 배열에서 인덱스 2에서 인덱스 6까지의 부분합을 구하고 싶다면, sum[6] - sum[2] = 25를 구할 수 있다. 이 결과가 성립할 수 있는 이유는 sum[2] = num[1] ~ num[2]까지..

[ 백준, Java] 1339번 : 단어 수학

🔗 문제 링크 https://www.acmicpc.net/problem/1339 🤔 문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그..

[백준, Java] 16120번 : PPAP

🔗 문제 링크 https://www.acmicpc.net/problem/16120 😮 문제 해결 방법 스택을 이용해서 문제를 해결했다. ‘P’가 들어오는 경우 스택에 저장하고, ‘A’가 들어오는 경우는 PPAP 문자열인지 판단해주었다. ‘A’가 들어오는 경우 PPAP 문자열인지 판단하기 위해 바로 다음 인덱스 문자가 ‘P’인지 판단하고 스택 사이즈가 2 이상 (스택에는 ‘P’만 들어감)인지 확인 후 스택을 두번 pop해 주었다. 결론적으로, 스택에서 pop된 문자 2개 PP와 현재 인덱스 A, 다음 인덱스 P가 되어 문자열 PPAP가 만들어지므로 다음 인덱스 ‘P’로 대체가 가능하다. 이외의 경우는 PPAP문자열을 P로 대체할 수 없으므로 “NP”를 리턴한다. 모든 PPAP 문자열이 P로 대체된다면, 마..

단방향, 양방향 매핑

엔티티들은 다른 엔티티들과 연관관계를 맺고 조회한다. 테이블에서는 외래 키를 사용하여 서로의 테이블을 조회하는 것이 가능하고, 객체는 다른 객체와의 참조를 통해 조회하는 것이 가능하다. 객체의 경우 서로 다른 객체 중 참조가 있는 객체 쪽에서만 조회가 가능하다. 방향 : 단방향과 양방향 매핑이 있으며, 서로 다른 두 개의 엔티티 중 한 개의 엔티티 쪽에서만 참조하는 경우를 단방향, 모두 서로의 객체를 참조하는 경우를 양방향 관계라고 한다. 테이블의 경우 외래키를 이용해 서로의 테이블 데이터를 조회할 수 있기 때문에 사실상 양방향 관계라고 볼 수 있다. 다중성 : 테이블의 관계와 동일하다. 1:N , N:1, 1:1, N:M 관계를 의미한다. 연관관계의 주인(owner) : 객체를 양방향 관계로 맺어 서로..