https://www.acmicpc.net/problem/1259문제 간단 요약입력된 정수가 팰린드롬이면 "yes", 아니면 "no" 출력 문제 해석간단한 구현문제로, 결국 좌/우를 확인하는 문제 문제풀이투 포인터, StringBuilder의 reverse() 내장함수 같은 다른 방법도 있지만좌/우가 한 쌍을 이루는지 확인하는 점에서 스택을 이용해서 풀기로 결정스택에 입력받은 문자열의 절반을 push한다.절반 이후부터는 스택의 top과 비교하며 같으면 pop, 아니면 반복문 탈출을 한다.위 과정이 진행된 후 스택이 비어있으면 입력된 수는 팰린드롬이다.막힌 부분가운데 수 처리홀수인 경우, 가운데 수는 짝을 이루지 않아도 팰린드롬이다.해결방법홀수인 경우, 한 칸 더 움직인 후 top과의 비교를 시작하는 것으..
백준 15829 문제 간단 요약영어 소문자로 된 문자열이 주어졌을 때,해당 문자열을 해시함수에 넣어서 생성된 해시값을 출력하라.문제 해석문제를 잘 이해했는지 확인하는 구현 문제해사함수에 대해 공부해봤으면 하는 출제자의 의도와 노력이 보인다.문제 풀이각 자리의 소문자를 정수(1~26)으로 치환한다.각 자리에 해당하는 만큼 r(31)을 거듭제곱한 후 치환한 값에 곱한다.M(1234567891)으로 나머지 연산을 한다.막힌 부분 : 50점r^i(31^i)는 거듭제곱이기 때문에, L이 클 때 굉장히 커진다.이거 어떻게 처리할지?해결방법내가 해결한 방법r에 31을 곱할 때마다 M을 사용한 나머지 연산을 통해 범위를 줄인다.추가 문제 : 나머지 연산을 통해 범위를 줄여도 M은 약 12억 ➡ a의 값이 2이상이..
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
