Algorithm/BOJ
-
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..
(JAVA) [BOJ]백준 1342번, 폴리오미노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..
2023.04.19 -
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)..
(JAVA) [BOJ]백준 11000번 : 강의실 배정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)..
2023.04.19 -
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번을 진행하게 된다면 ..
(JAVA) 백준 15903번 : 카드 합체 놀이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번을 진행하게 된다면 ..
2023.04.18 -
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..
(JAVA) 백준 11725번 : 트리의 부모 찾기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..
2023.03.09 -
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 9663번, N-Queen 이번 문제는 백트래킹의 대표문제라고 많이 알려져 있는 N-Queen 문제이다. 문제에 대한 설명보다는 풀이 과정에 집중에서 포스팅을 진행해 보겠다. [공간 복잡도] 공간 복잡도를 고려했을 때, 1
(JAVA) 백준 9663번 : N-Queenhttps://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 9663번, N-Queen 이번 문제는 백트래킹의 대표문제라고 많이 알려져 있는 N-Queen 문제이다. 문제에 대한 설명보다는 풀이 과정에 집중에서 포스팅을 진행해 보겠다. [공간 복잡도] 공간 복잡도를 고려했을 때, 1
2023.02.13 -
https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이번 문제를 읽는데 무슨 내용인지 이해가 되지 않아 애를 먹었었다. 정리하자면 첫번째에서 RED 에서 골랐으면 두번째에선 RED를 제외한 BLUE OR GREEN 을 선택하고 세번째에선 나머지를 고르고, 이러한 경우 중 최소값을 고르면 되는 문제이다. 풀이는 아래와 같다. # Process import java.io.BufferedReader; import java.io.In..
(JAVA) 백준 1149번 : RGB거리https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이번 문제를 읽는데 무슨 내용인지 이해가 되지 않아 애를 먹었었다. 정리하자면 첫번째에서 RED 에서 골랐으면 두번째에선 RED를 제외한 BLUE OR GREEN 을 선택하고 세번째에선 나머지를 고르고, 이러한 경우 중 최소값을 고르면 되는 문제이다. 풀이는 아래와 같다. # Process import java.io.BufferedReader; import java.io.In..
2022.12.01 -
https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 이번 문제는 동적 계획법과 피보나치 수열의 응용 버전이라고 생각하면 편하다. 이번 문제는 4번째 값부터 한칸 뒤의 두 수의 합과 같다. 즉, dp[i] = dp[i-2] + dp[i-3] 으로 표현할 수 있다. 풀이는 아래와 같다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException..
(JAVA) 백준 9461번 : 파도반 수열https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 이번 문제는 동적 계획법과 피보나치 수열의 응용 버전이라고 생각하면 편하다. 이번 문제는 4번째 값부터 한칸 뒤의 두 수의 합과 같다. 즉, dp[i] = dp[i-2] + dp[i-3] 으로 표현할 수 있다. 풀이는 아래와 같다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException..
2022.11.28 -
https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 이 문제는 dp (동적계획법) 을 사용하고 함수는 기존의 함수를 그대로 사용하면 된다. 규칙이 있나 찾아보다가 재밌는 규칙을 찾아내서 그것도 사용해 보았다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; publi..
(JAVA) 백준 9148번 : 신나는 함수 실행https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 이 문제는 dp (동적계획법) 을 사용하고 함수는 기존의 함수를 그대로 사용하면 된다. 규칙이 있나 찾아보다가 재밌는 규칙을 찾아내서 그것도 사용해 보았다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; publi..
2022.11.25