본문 바로가기

CS ﹒ Algorithm/Baekjoon

JAVA 백준 문제풀이 (15) 2798: 블랙잭
CS ﹒ Algorithm/Baekjoon 2022. 7. 11. JAVA 백준 문제풀이 (15) 2798: 블랙잭 해당 문제는 브루트포스 카테고리에 속해있다. 브루트 포스란 무엇인가? 암호학에서, 무차별 대입 공격(영어: brute-force attack)은 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 것을 의미한다. 대부분의 암호화 방식은 이론적으로 무차별 대입 공격에 대해 안전하지 못하며, 충분한 시간이 존재한다면 암호화된 정보를 해독할 수 있다. 하지만 대부분의 경우 모든 계산을 마치려면 실용적이지 못한 비용이나 시간을 소요하게 되어, 공격을 방지하게 한다. 암호의 '취약점'이라는 의미에는 무차별 대입 공격보다 더 빠른 공격 방법이 존재한다는 것을 의미한다. 이것은 암호학의 얘기이지만 알고리즘도 별 다를 거 없다. 원하는 값이 도출될 때까지 모든 경우의 수를 대입하는 것을 브루트포스라고 한다. 브루트는 ..
JAVA 백준 문제풀이 (14) 10872: 팩토리얼
CS ﹒ Algorithm/Baekjoon 2022. 7. 10. JAVA 백준 문제풀이 (14) 10872: 팩토리얼 가장 기초적인 팩토리얼 문제이다. 사실 팩토리얼은 for문으로 풀어도 아무런 문제가 없으나, 백준에서 해당 문제가 재귀 카테고리에 올라가 있었기 때문에 재귀를 활용해서 풀었다. 재귀란 무엇인가? 재귀 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 자기언급과도 관련된 재귀는 언어학에서 논리학에 이르기까지 다양한 분야에서 연구되는 주제로, 특히 컴퓨터 과학과 수학에서, 재귀는 함수가 자신의 정의에 의해 정의될 때의 개념을 가리킨다. 쩝.. 처음 접하면 어렵게 느껴질 수도 있다. 하지만 사칙연산만 할 수 있다면 누구나 이해할 수 있는 것이니 밑을 보자. 팩토리얼 N! = n-2 * n이라는 공식을 갖는다. 그러니까, 팩토리얼(3) = 팩토리얼(2)의 결과 * 3이란 말이다. 엥? 이거 완전 메서드..
JAVA백준 문제풀이 (13) 9020: 골드바흐의 추측
CS ﹒ Algorithm/Baekjoon 2022. 7. 9. JAVA백준 문제풀이 (13) 9020: 골드바흐의 추측 백준 단계별 학습의 마지막 소수 문제이다. 늘 그랬듯이 에라토스테네스의 체로 해결한다. https://7357.tistory.com/104?category=1065986 0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체 고대 그리스 수학자 에라토스테네스가 발견한 소수를 구하는 간편한 방법이다. 알고리즘 중에 그나마 쉬운 편에 속한다. (1) 우선 0과 1은 소수가 아니기때문에 제외한다. (2) 소수인 2를 제외한 2 7357.tistory.com 평소보다 머리를 조금 더 써야하는데, 단순히 더해서 해당 값이 나오게 합만 구하면 되는 것이 아니라 여러 경우의 수가 있을 경우 최대한 소수의 차가 덜한 것을 구하라고 한다. 그렇다. 입력된 값을 반으로 갈라 중간부터 반복문을 돌리면 된다. 어차피 입력..
JAVA백준 문제풀이 (12) 4948:베르트랑 공준
CS ﹒ Algorithm/Baekjoon 2022. 7. 8. JAVA백준 문제풀이 (12) 4948:베르트랑 공준 단계별로 문제를 풀다보니 한 번 특정 형태의 문제를 만나면 해당 문제만 연달아 일주일가량 만나게 된다. 그래서 오늘도 어김없이 에라토스테네스의 체와 관련된 소수를 구하는 문제다. 매번 똑같은 내용으로 글을 늘어지게 작성할 수는 있지만.. 의미가 없다. 에라토스테네스의 체는 굉장히 쉽기 때문에 꼭 직접 풀어보길 바란다. https://7357.tistory.com/104?category=1065986 0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체 고대 그리스 수학자 에라토스테네스가 발견한 소수를 구하는 간편한 방법이다. 알고리즘 중에 그나마 쉬운 편에 속한다. (1) 우선 0과 1은 소수가 아니기때문에 제외한다. (2) 소수인 2를 제외한 2 7357.tistory.com import java..
JAVA백준 문제풀이 (11) 1929: 소수 구하기
CS ﹒ Algorithm/Baekjoon 2022. 7. 6. JAVA백준 문제풀이 (11) 1929: 소수 구하기 백준 문제 밑에 항상 짧게 설명이 있다. 헉 더 빠르게 소수를 판별하는 문제?????? 정답률 26.666%?????? 주어진 시간이 2초나 되길래 혹시나 싶어 그냥 풀어보니 다른 문제랑 똑같았다. 혹시 BufferdReader를 쓰지 않으면 시간 초과하나? 아니면 문제 번호가 1929번인 걸 보니 아직 코테가 당연하지 않던 시절에 사람들이 너무 틀려서 정답률을 낮춰놨나 싶기도 하다. 아무튼 그냥 에라토스테네스의 체로 풀 수 있는 문제였음. 모른다면 아래 링크에서 이전 포스트를 읽어봅시다. 제목은 백준 풀이인데 며칠째 소수 구하는 문제만 풀고 있어서 풀이를 적을 게 없다.. https://7357.tistory.com/104?category=1065986 0부터 n까지의 수 중 소수 구하기 : 에라토스테..
JAVA백준 문제풀이 (10) 11653: 소인수분해
CS ﹒ Algorithm/Baekjoon 2022. 7. 5. JAVA백준 문제풀이 (10) 11653: 소인수분해 이 문제를 보고 내가 생각한 풀이 방식은 에라토스테네스의 체를 이용해 소수의 배열을 먼저 구한 뒤 그것으로 나누는 것이였는데.. 그러면 바로 시간 제한에 걸려서 탈락한다. 생각해보면 애초에 그런 식으로 풀어야 할 이유가 없다. 그냥 소수인 2부터 나누기 시작해서 2로 나눈 나머지가 0이 아니라면 나누는 수를 1씩 더하면 된다. " 엥?? 소인수 분해는 소수로만 나눠야 하는데요?? " 생각해보자. 어차피 2로 나눌 수 없는 수는 4로 나눌 수 없고 3으로 나눌 수 없는 수는 6으로 나눌 수 없다. 띠용~ 작은 수부터 점점 키워나가면 무조건 소수로 나눠지게 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt..
JAVA백준 문제풀이 (9) 2581:소수
CS ﹒ Algorithm/Baekjoon 2022. 7. 4. JAVA백준 문제풀이 (9) 2581:소수 포스팅한 1978: 소수 찾기와 똑같다고 봐도 무방한 문제. 에라토스테네스의 체를 코드로 구현할 수 있는 사람이 결과물을 다른 곳에 담아 출력하는 걸 할 줄 모를리가 없기 때문이다. 혹시라도 에라토스테네스의 체를 모른다면 예전에 작성한 포스팅을 읽어보자. 단순해서 한 번 보면 이해할 수 있다. https://7357.tistory.com/104?category=1065986 0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체 고대 그리스 수학자 에라토스테네스가 발견한 소수를 구하는 간편한 방법이다. 알고리즘 중에 그나마 쉬운 편에 속한다. (1) 우선 0과 1은 소수가 아니기때문에 제외한다. (2) 소수인 2를 제외한 2 7357.tistory.com import java.util.ArrayLis..
JAVA백준 문제풀이 (8) 1978:소수 찾기
CS ﹒ Algorithm/Baekjoon 2022. 7. 3. JAVA백준 문제풀이 (8) 1978:소수 찾기 에라토스테네스의 체를 활용하면 쉽게 풀 수 있는 문제이다. 예전에 포스팅한 적이 있으니 잘 모르면 읽어보도록 하자. https://7357.tistory.com/104 0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체 고대 그리스 수학자 에라토스테네스가 발견한 소수를 구하는 간편한 방법이다. 알고리즘 중에 그나마 쉬운 편에 속한다. (1) 우선 0과 1은 소수가 아니기때문에 제외한다. (2) 소수인 2를 제외한 2 7357.tistory.com 에라토스테네스의 체는 굉장히 심플해서 한 번 보면 바로 이해가 되는데, 문제는 이걸 어떻게 코드로 작성하지? 라고 생각하면 또 벙찌게 될 수도 있다. 그러면 그냥 여러번 풀어보면 된다.. 그것이 수학이니까.. ㅋㅋㅋ ㅜ import java.util.Sc..

티스토리툴바