https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1715, 카드 정렬하기 이번 문제는 우선순위 큐를 사용해서 풀어보겠다. N의 범위가 1 - 100,000 이고, 카드의 최대 값은 1,000이지만 카드를 합쳐가는 과정에서 모든 카드의 수를 계산한다면 int 의 범위를 넘을 수 있기 때문에 Long 을 사용해주겠다. # Process main : 입력받은 값들을 큐에 넣어주고 가장 작은 2장의 카드를 뽑아 더한 후에 다시 큐에 넣어..

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 12904, A와 B 이번 문제는 역으로 해결해 나가면 쉽게 풀 수 있다. # Process main : 조건이 2개가 있다. 1. 문자열의 뒤에 A를 추가한다. 2. 문자열을 뒤집고 뒤에 B를 추가한다. 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지를 판단하는 문제이다. 이 조건을 반대로 생각해보자. 주어진 B의 텍스트에1. 문자열의 뒤에 A가 있..

https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net 1342, 폴리오미노 이번 문제는 String 과 replace 를 사용하면 너무나도 쉽게 풀 수 있다. # Process main : "XXXX" 는 "AAAA"로, "XX"는 "BB" 로 바꿔주되 사전순으로, 전환이 불가능하다면 -1을 출력해주면 된다. 즉, 차례대로 전환해주고 X가 남아있다면 -1 을 출력해준다. str = str.replaceAll("XXXX", "AAAA"); str = str..

https://www.acmicpc.net/problem/11000 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 11000, 강의실 배정 이번 문제는 최소 우선순위 큐와 시작 시간과 종료 시간을 저장하는 class 를 생성하여 해결하였다. # Process Class, Lecture : 시작시간과 종료시간을 저장하는 Lecture Class 를 생성하였다. 생성자로 두 시간을 저장해주는 간단한 설계이다. static class Lecture { public int sdate; public int edate; Lecture(int startDate, int endDate)..

https://www.acmicpc.net/problem/15903 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 15903번, 카드 합체 놀이 이번 문제는 최소 우선순위 큐를 사용하고 범위를 주의해야 하는 문제이다. int 가 아닌 Long 을 사용하였는데 이유는 아래에서 설명하겠다. # Process main : x번 카드와 y번 카드 두장을 골라 x+y 의 값으로 x 와 y 번 카드를 덮어쓰는 문제이다. 카드의 수의 최대 값은 1,000,000이다. 모든 최대 경우를 계산했을 때, 1000장의 카드 모두 1,000,000 이고 합체를 15,000번을 진행하게 된다면 ..

https://www.acmicpc.net/problem/2847 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 2847, 게임을 만든 동준이 이번 문제는 뒤에서 부터 계산해 나가면 어렵지 않게 풀 수 있는 문제이다. N의 범위가 1 - 100 이고, 점수는 최대 20,000 점이기 때문에 모든 점수를 합해도 int 범위이기 때문에 int 를 사용해 주었다. # Process main : 차례대로 모든 수를 계산하려면 복잡하기 때문에 뒤에서 부터 계산을 진행했다. N 번째 요소와 N-1 번째 요소를 비교하여 N-1 번째 요소가 더 크다면 N에서 -1 만큼 해준 수로 값을 ..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 11725, 트리의 부모 찾기 이번 문제는 트리 구조와 BFS(너비우선탐색) 을 사용하면 풀 수 있는 문제이다. 그다지 어렵지 않다. N의 범위가 2 이상, 100,000 이하 이기 때문에 int 형을 사용해 주겠다. # Process main : 트리상에서 연결된 두 정점을 제공하기 때문에 양방향으로 연결해주면 된다. ArrayList 를 사용한 인접 리스트 방식으로 코드를 구현하겠다. ( adj의 i 번째의 공간에 ArrayList 생성 ) static v..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 9663번, N-Queen 이번 문제는 백트래킹의 대표문제라고 많이 알려져 있는 N-Queen 문제이다. 문제에 대한 설명보다는 풀이 과정에 집중에서 포스팅을 진행해 보겠다. [공간 복잡도] 공간 복잡도를 고려했을 때, 1