Alogorithm
백준 JAVA 19532번 수학은 비대면 강의입니다.
백준 JAVA 19532번 수학은 비대면 강의입니다.
2021.12.10문제 링크: https://www.acmicpc.net/problem/19532 19532번: 수학은 비대면강의입니다 정수 $a$, $b$, $c$, $d$, $e$, $f$가 공백으로 구분되어 차례대로 주어진다. ($-999 \leq a,b,c,d,e,f \leq 999$) 문제에서 언급한 방정식을 만족하는 $\left(x,y\right)$가 유일하게 존재하고, 이 때 $x$와 $y$가 각각 $- www.acmicpc.net 단순한 브루트 포스 문제이다. ax+by=c 와 dx+ey=f를 만족하는 x,y를 반복문을 통해서 모든 경우의 수를 탐색해주면 된다. import java.util.*; import java.io.*; public class Main { public static void main(..
백준 JAVA 17626번 Four Squares
백준 JAVA 17626번 Four Squares
2021.12.09문제 링크: https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 그리디 알고리즘으로 가장 큰 제곱수를 빼고 나머지에서 가장 큰 수로 계속해서 나가는 형식으로 문제를 접근했지만, 당연히 틀렸다. DP로 풀어야 하는 문제였다. 밑에와 같이 개수=1일 때 가장 작고 그 후에 증가하고 줄어드는 추세를 볼 수 있다. dp[1] = 1^2 = 1개 dp[2] = 1^2 + 1^2 = 2개 dp[3] = 1^2 + 1^2 +..
백준 JAVA 9655번 돌게임
백준 JAVA 9655번 돌게임
2021.12.07문제 링크: https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 상근이와 창영이가 가져갈 수 있는 돌의 갯수가 1 or 3개로 고정되어 있다. 돌갯수/승리자 상근 창영 1 o x 2 x o 3 o x 4 x o 5 o x 돌의 갯수가 주여졌을 때 다음과 같은 모습을 볼 수 있다. 따라서 2로 나눈 나머지의 여부로 승리자가 결정된다. import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { BufferedReader b..
백준 JAVA 14891번 톱니바퀴
백준 JAVA 14891번 톱니바퀴
2021.12.04문제 링크: https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 시뮬레이션 문제로서 하나의 톱니바퀴를 돌렸을 때 옆에 있는 톱니바퀴들이 돌아간다면 상태 배열을 변경시키고 상태 배열에 따라서 시계방향, 반시계방향으로 돌려주면된다. 시작 지점에서의 시계, 반시계 방향으로 퍼져나가는 것을 생각해주면 어려운 문제는 아니다. import java.util.*; import java.io.*; class info{ int num; int dir; publ..
백준 JAVA 1343번 폴리오미노
백준 JAVA 1343번 폴리오미노
2021.12.02문제 링크: https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net '.'을 기준으로 X의 문자 개수 % 2 == 0을 만족한다면 4와2의 몫을 이용하여 A와B로 치환해주고, 만족하지 않는다면 -1을 출력해주는 간단한 문제이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static StringBuilder sb = new StringBuilder(); stati..
백준 JAVA 1991번 트리 순회
백준 JAVA 1991번 트리 순회
2021.12.01문제 링크: https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 트리의 전위, 중위, 후위 탐사를 진행하는 기초 문제다. List[] 의 배열 형태로 받아 저장한 후 루트부터 탐색을 진행하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Node{ char left;..