전공공부

설명 입력이 들어오면 그 숫자를 소인수 분해하면 된다. 출력 형태를 보니 재귀로 처리하면 쉽게 처리 할 수 있을 것으로 판단하여 재귀 형태로 짰고 모든 수를 탐색하여 소수를 찾아서 나눠도 되지만 제곱근 내에서만 탐색하면 해당 숫자 내부의 소수를 모두 찾아서 판단할 수 있어서 아래와 같이 코드를 짰다. 그리고, 마지막에 출력 추가 부분은 다 나누고 마지막에 남는 소수를 찾기 위해서 추가하였다. 마지막에 남은 수가 소수일 경우 제곱근으로 반복문 돌리는 방식은 자기 자신이 소수일때는 자기 자신의 수 내부에 존재하는 소수를 찾지 못하고 (소수는 1 아니면 자기 자신으로만 나누어진다.) 마지막에 남은 소수 바로 자신을 출력하면 된다. 코드 import java.io.BufferedReader; import jav..

설명 자연수 n개가 주어진다. 이 자연수의 공약수를 모두 구하는 프로그램을 작성하시오. 들어온 수를 나눴을때 공통으로 0이 되는 수를 찾아서 출력하는 형식으로 만들었고 이를 최적화 하기 위해서 들어오는 수 중 가장 작은 수 기준으로 해당 값 보다 작거나 같은 자연수들만 공약수가 될 수 있음을 유의해서 풀었다. 코드 package Math; import java.util.*; import java.io.*; public class BOJ_5618 { public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr[] = new int[n]; for(i..

단순히 소수를 구하고 이에 따라서 해당 범위의 최솟값과 소수들의 합을 구하는 문제이다. 소수 판별법이 잘 기억이 나지 않아 제곱근까지의 숫자들을 모두 검증하는식으로 풀었다. package Math; import java.util.*; import java.io.*; public class BOJ_2581 { static int min = Integer.MAX_VALUE; static int ans = 0; public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tk = new StringTokeniz..

설명 왼쪽으로 모으는 경우 오른쪽으로 모두 모으는 경우를 카운트 한다. 이것이 가능한 이유는 카운트 해야 할 예시가 R,B 2가지로 2가지를 서로 다른 위치로 배정해서 모두 같은 곳으로 옮기면 되므로 한 쪽으로 몰아준다는 아이디어로 구현을 하면된다. 예시로, RBBBRRB의 경우 R을 오른쪽으로 모두 옮긴 경우 BBB B RRR 와 R을 왼쪽으로 모두 옮기는 경우인 R RR BBB B 가 존재한다. 이것을 B의 경우에도 적용하여 최저로 옮긴 경우를 반환하면 된다. 이것을 구현하기 쉽게 이해하기 위해서는 최초의 가장자리 위치의 값들만 제외하고 떨어진 것들만 옮기면 된다는 생각을 가지고 코드를 구현하면 바로 구현 가능하다. 코드 package Greedy; import java.io.*; import jav..

설명 재귀함수를 사용하는 문제였으며 처음에는 일일이 S -> T로 만드는 방법을 썼지만 12%에서 시간 초과가 났고 생각을 비틀어서 T -> S로 변경하여 소거법으로 진행하였다. 그러면, 문제 조건중 '문자열 뒤에 B를 추가하고 뒤집는다.' 가 있으니 B가 맨 앞에 있는 경우는 B의 경우로 들어온 것임을 유추 할 수 있어서 오히려 조건의 반대로 맨 앞의 B를 빼고 다시 뒤집는 것을 B의 조건으로 만들고 재귀함수 돌리고 A의 경우에는 '문자열 뒤에 A를 추가한다' 가 있으니 맨 뒤에 A를 빼고 재귀를 돌리는 형식으로 S를 만들어 나갔다. 그런데, 이 소거법을 진행하면서 간과한 것이... T = T.subString(1); 이런식으로 재귀를 돌아가는 T의 조건을 바꾸어 버렸다. 이런식으로 진행해버리면 다음 ..

BFS 문제는 너무 많이 풀어서 유형을 외워 버린 탓에 쉽게 풀 수 있었다. Queue에 넣고 방문 여부 체크하고 문제에서 제시한 조건을 따라서 조건을 생성 한 후 반복문을 돌면서 큐의 값을 소진 시키면서 탐색을 진행 너무나 많이들 쓰는 풀이이기 때문에 따로 설명은 필요 없을 듯하다. 만일, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다. 이 조건을 간과하고 풀었다면 arr이 0로 초기화 되었을테니 잘못된 부분을 찾지 못해서 어려움을 느꼈을 수도 있을 것 같다. package BFS; import java.util.*; import java.io.*; public class BOJ_14940 { static int dx[] = {-1,0,1,0}; static int dy[]..

단순 구현 문제 - list 객체에 등수 구하기 위한 값들을 넣은 후 내림차순 sort 한 후 같은 값일 때는 가장 작은 등수로 인식이 되어야 하므로 조건문 통과를 위한 값은 lastIndex의 값으로 사용함 - 등수 출력시에는 index 처음 나온 위치 값을 사용함 아래는 코드이다. package Simulation; import java.util.*; import java.io.*; public class BOJ_1205_등수_구하기 { public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tk..

슬라이딩 윈도우(Sliding Window)는 배열 또는 문자열에서 연속적인 요소의 부분집합을 찾는 데 사용되는 알고리즘 기술 알고리즘은 주어진 문제의 해결을 위해 윈도우을 움직이면서 데이터를 처리하고 일부 조건을 충족하는 부분집합을 찾습니다. 이는 주로 부분집합의 합, 최대 길이 부분집합, 연속된 부분집합 등을 찾는 데 사용합니다. 1. 처음 시작과 끝으로 지정할 부분 집합의 길이 만큼 탐색한 후 데이터를 초기화 합니다. 2. 끝과 초기 인덱스를 이동하면서 윈도우 내부 데이터를 업데이트를 진행합니다. 아래는 부분 집합의 최대 합을 구하는 문제이다. public class SlidingWindow { public static int findMaxSubarraySum(int[] nums, int k) { ..