처음엔 dfs를 이용해 풀어보려고 했으나 실패했다. bfs를 이용해 익은 토마토가 들어있는(1) 좌표를 q에 넣어주고, 상하좌우에 있는 토마토 중 안익은(0) 토마토가 들어있는 좌표가 있으면 익은 토마토 일수에서 1을 더해준다 즉 depth가 1 깊어질 때마다 1을 추가해 주는 것이다. 이렇게 하면 일수를 계산 가능하다. 그 후 countDay메서드를 통해 가장 깊은 depth를 cnt에 담아주고 depth는 1에서 시작했는데 일수는 0에서부터 시작했으니 날짜를 계산할 때는 1을 빼준다. 최종적으로 checkTomato메서드를 통해 안익은 토마토가 있으면 -1을 출력하고 그렇지 않으면 모든 토마토가 있은것이므로 cnt를 출력한다. import java.io.BufferedReader; import jav..

문제 풀 때마다 까먹어서 이항계수를 정리해보려 한다. 이항계수 nCr 은 n개중 r개를 선택하는 경우의 수를 의미하며 n!/r!(n-r!)로 나타낼 수 있다 알고리즘에서 이항계수를 구할 때 팩토리얼로 일일히 이항계수를 구하면 int범위를 벗어나 오버플로우가 발생하는 경우가 많다. 따라서 BigInteger를 이용해줄 수 있지만 보통은 재귀를 이용한다. 재귀를 이용할 때에도 시간초과가 날 수 있기 때문에 dp로 풀어주는 것이 일반적이다. 이항계수에는 중요한 규칙 두 가지가 있다. 1.nCr = n-1Cr + n-1Cr-1 2.nC0 = nCn = 1 이를 증명해보자 {a1,a2,a3....an}의 부분집합 중 원소의 개수가 r인 것의 개수는 nCr이다 여기서 원소의 개수가 r인 경우는 두가지로 나뉠 수 있..

피보나치 수열 중 n번째 항의 수를 리턴하는 간단한 문제였다. 입력 : int n 출력 : int타입 💡주의사항 재귀함수로 풀어야 한다 반복문의 사용이 금지된다. 아 별거아니네~ 하고 처음에는 재귀를 사용해서 룰루랄라 풀어서 제출하려고 했다. 근데 자꾸 시간초과가 뜨는 것이다.. 알고보니 재귀를 이용한 문제는 메모리를 상당히 잡아먹는 비효율적인 방법이고 위 방법대로 푼다면 함수들의 총 호출횟수가 대략 2^n 근처라서 n이 25~30 넘어가면 힘들어진다고 한다. 따라서 메모이제이션을 쓰면 효율적인 알고리즘(O(N))으로 연산을 줄일 수 있다! 🔎메모이제이션이란 이미 계산된 값을 배열에 저장하고 필요시마다 값을 불러와 쓴다. 이렇게 하여 불필요하게 중복되는 계산을 줄이는 것이다! public class fi..

문제 입출력 예시 처음 풀이 처음에는 정말 최대공약수와 최소공배수 구하는 공식 그대로 생각해서 구현해서 풀었다. import java.util.Scanner; //최대공약수와 최소공배수 public class Baek_2609 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int num1 = in.nextInt(); int num2 = in.nextInt(); int commonDivisor = 1; //최초 최대공약수 1로 설정 //두 수중 작은 수에서부터 돌면서 공약수를 확인 for (int i = Math.min(num1, num2); i > 1; i--) { /*만약 i가 num1과 num2의 공약수이..

처음 백준 문제를 풀때 가장 많이 헷갈리는 부분이 입출력을 어떻게 받는가이다. 아직 StringTokenizer의 사용법이 헷갈려서 오류가 뜰 때가 많다. 처음에 가장 많이 떳던 오류는 NoSuchElementException였다. 아직 정확한 원인은 모르지만 nextToken으로 받은 후 값을 사용하지 않고 바로 nextToken을 사용하여 다른 값을 받으려고 하면 뜬다. 또 StringTokenizer는 무조건 '공백'으로만 입력받는다! 줄 단위로 입력받고 싶으면 그냥 readLine()을 바로 쓰면 된다. 추후에 다른 오류들을 만나며 더 알아봐야겠다. 이번에는 백준 2675번 문제를 풀던 중 다음과 같이 ArrayIndexOutOfBoundsException이 발생하였고 해석해보면 인덱스 1은 배열..

3일에 걸쳐 전반적인 Java의 개념을 배우고 연습문제를 풀어보았다. 최종 과제로 intellij를 이용하여 계산기까지 만들어 보았다. 주요 학습내용 변수와 타입 문자열(String) String 클래스의 메서드 연산자와 연산자 우선 순위 콘솔 입출력 제어문(조건문,반복문) 배열(1차원 배열, 2차원 배열,가변 배열) 계산기 만들기 과제 반복문 문제 아래는 코플릿 문제 답이 있으니 혹시 코드스테이츠 수업을 들으실 분들은 보지 않으시는게 좋을 것 같다 ㅎㅎ 반복문 문제 17 1 이상의 자연수를 입력받아 소수(prime number)인지 여부를 리턴해야 합니다. 입력 - int 타입의 수 출력 - boolean 타입을 return해야 합니다. 나의 답안 reference 여기서는 Math.sqrt 를 활용했..