백준

https://www.acmicpc.net/problem/9935 접근방법스택 문제이기 때문에 Stack클래스를 사용하는 방향으로 문제에 접근했다.스택에 입력된 문자열의 문자를 하나씩 넣기넣을 때마다 조건 확인조건 : 폭발 문자열의 마지막 글자와 같은지, 스택이 폭발 문자열의 길이보다 긴지 조건에 맞는다면 폭발 문자열인지 확인맞다면 폭발 문자열을 스택에서 제거아니라면 제거하지 않고 1번으로 돌아가기 참고사항 N : 입력 문자열의 길이M : 폭발 문자열의 길이1차 시도 : Stack 사용 - O(N*M)결과 : 시간초과import java.util.Scanner;import java.util.Stack;public class Main { public static void main(String[] ar..

N과 M을 둘다 int로 선언하면 안되는 이유문제에서 설정한 N과 M의 범위는 [-2,000,000,000 ≤ N, M ≤ 2,000,000,000]즉, int의 범위에 속한다. 하지만 주의해야 할 점은, N과 M이 사칙연산을 한다는 점이다.+,- 연산으로 인해 -40억,+40억과 같은 int의 범위를 초과한 연산결과가 나올 수 있다는 소리다. 하지만, 문뜩 나는 이런 궁금증이 생겼다.어차피 변수 N, M에 저장된 값은 변하지 않을텐데 왜 int로 하면 안되지? 결과값만 long으로 저장하면 안되나?Math.abs에서 N-M을 알아서 long으로 봐줄 수는 없나?Math.abs함수의 동작 방식 뭐지?그래서 구글링한 결과 N과 M을 둘다 int로 선언하면 안되는 2가지의 구체적인 이유를 찾았다.첫째, N과..

문제 핵심 포인트 1. 문제 단계 제목인 브루트 포스 알고리즘 2. 브루트 포스 알고리즘에 따라 모든 경우의 수를 다 확인하면 그중에 하나는 문제의 조건을 만족하는 결과라고 가정 코드 설명 1. 3kg , 5kg 봉투의 모든 조합을 확인하기 위해 2중 반복문 2. bag3를 외부,bag5를 내부 반복자로 연결 -> 3kg보다 5kg봉투를 더 많이 사용하는 경우부터 확인하기 위해(5kg를 더 많이 사용해야 최소봉투의 개수가 되기 때문에) 3. 가장 먼저 찾은 경우가 최소봉투의 개수이기 때문에 찾은 즉시 바로 2중 반복문을 탈출 4. 만약 존재하지 않을 경우 -1을 출력하는 조건문 사용 import java.io.*; import java.util.StringTokenizer; public class Mai..

문제 핵심 포인트 1. 문제 단계 제목인 브루트 포스 알고리즘 순서 1. 전체 보드 입력 2. 전체 보드에서 부분보드(8x8)를 전체 탐색 3. check함수 = 부분보드를 인자로 받아서 일반체스판과 일치하는 사각형이 얼마나 있는지 확인하는 함수 4. 모든 부분보드를 반복문을 돌면서 check함수에 인자로 전달 5. 반환값들 중에 가장 큰 반환값을 이용해서 정답 출력 import java.io.*; import java.util.StringTokenizer; public class Main { static int check(char[][] subBoard){ int countW=0; int countB=0; String[] W = new String[8]; String[] B = new String[8]..

문제 핵심 포인트 1. 문제를 이해하는 것 부터 힘들다. 2. 숨은 조건을 찾아내기 일단 아래에 중요한 부분을 표시해봤다. 여기서 O(n)정의를 만족하는지를 물었으니 O(g(n))의 g(n)은 n이 된다. + 문제조건 1. a1,a0 = 양수,음수 가능 2. c,n0 = 양수 이 정보들을 바탕으로 부등식을 써보자 a1*n0 + a0 ≤ c*n0 이 부등식을 조건문으로 사용해서 문제를 제출해보자. 정답인 것 같다. import java.io.*; public class Main { public static void main(String[] length) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syst..

문제 핵심 포인트 1. BigO 표기법으로 봤을때 몇차수인가 2. 표시된 코드가 얼마나 반복되는가 3. 자료형 범위가 맞나 MenOfPassion(A[], n) { sum

문제 핵심 포인트 굉장히 큰 크기(long보다 큰)의 int를 어떻게 계산할 것인가? 방법1. BigInteger 클래스 사용 import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); BigInteger big1 = scan.nextBigInteger(); BigInteger big2 = scan.nextBigInteger(); System.out.println(big1.add(big2)); } } 방법2. 배열을 이용해서 계산 (아래 코드에서 BufferWriter를 사용할 때 주의할 ..

아무 생각없이 int를 사용했다가 런타임 에러가 떠서 당황했다. 문제를 잘 보면 [입력 : 첫 번째 줄에 A, B, C (1 ≤ A, B, C ≤ 10¹²)이 공백을 사이에 두고 주어진다.] 에서 범위가 1 ~ 10의 12승이다. 하지만 int의 4바이트로 양의 범위는 최대 2,147,483,647(2의 31승 ) < 10의 10승 이기 때문에 런타임 에러가 뜬다. 따라서 8바이트 자료형(double,long long등)을 써줘야 런타임 에러가 발생하지 않는다. import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); long a,b,c; a ..