본문 바로가기

분류 전체보기130

에라토스테네스의 체(백준 1713번 : 골드바흐 파티션) 오늘은 소수 판별법 중 하나인 에라토스테네스의 체에 대한 리뷰 오늘도 당연히 그림 같은 건 생략한다. 왜냐하면 귀찮기 때문 에라토스테네스의 체는 소수 판별법 중에 하나인데, 특정 숫자 범위 이내의 숫자들 중 소수들을 찾을 때 사용 가능하다. 찾는 법은 아주 간단한데, 예를 들어 100 이하의 소수를 찾으려고 할 때 2의 배수, 3의 배수, 5의 배수, 7의 배수를 제외하면 남은 숫자가 소수이다. 이렇게 걸러내는 방식이 마치 체로 걸러내는 것과 비슷하여 이름이 붙여졌다. (코드는 아래 주석과 함께) 아래는 에라토스테네스의 체를 사용하는 문제이다. 나는 에라토스테네스의 체를 모르는 채로 아래 문제를 풀었는데, 2의 배수 3의 배수까지 걸러내는 것에는 다가갔는데 그 이후로는 실패하여 검색해서 해결했다. 원래 .. 2023. 12. 9.
[백준][JAVA] 1003번 : 피보나치 함수(동적계획법과 메모이제이션을 활용한 풀이) 오늘은 백준 1003번 피보나치 함수에 대한 리뷰 유튜브로 동적계획법(Dynamic Programming)과 이를 위한 메모이제이션, 테뷸레이션 등등을 배웠는데 마침 느낌상 정석 같은 풀이라서 기록을 남긴다. 문제가 길지만, 요약하자면 함수를 통해 피보나치 수를 구할 때, 0과 1이 몇번 호출되는지 구하는 문제 기본 재귀함수 등 여러시도를 해봤지만 시간 초과 때문에 동적계획법을 활용해야함. 그 외의 신박한 풀이들은 구글에 검색하면 고수님들이 많이 올려주셨음. 나는 초보라서 동적계획법을 떠올리기 힘들었고, 처음에는 그저 카운트 할려했는데 포기하고 검색해 보니 DP문제라고 해서 다시 혼자서 연구해서 풀어냈다.(시간 초과 때문이지 절대 구현을 못한 건 아님!!) 구현한 코드는 사실 간단하다. import ja.. 2023. 12. 8.
자바 배열로 스택 구현해보기(백준 28278번 : 스택 2) 오늘은 백준 28278번 : 스택 2 리뷰입니다(매우 간단한 문제) 그냥 남들은 어떻게 구현했나 보려고 검색을 했는데 다들 컬렉션 프레임워크를 사용했더라고요.. 그래서 글을 남깁니다. 요즘 문제를 풀면서 느끼는 건데, 구현 그 자체보다 시간, 메모리 제한이 빡빡하게 걸려있는 것들이 어려움.. 보통 그런 문제들은 정해진 알고리즘이 있긴 하던데, 예를 들어 어제는 에라토스테네스의 체 때문에 시간 엄청 잡아먹었음 모르는 채로 얼추 근접했긴 했었는데 아무튼 이번 문제는 구현만 하면 돼서 간단했다. 구현 방법은 명령의 수가 1,000,000으로 정해져 있기 때문에 배열을 크기를 고정시킬 수 있고, 배열을 만든 후 스택에 push(insert) 할 때마다 front라는 상수를 조절하는 방식으로 구현했다. impor.. 2023. 12. 7.
간단하지만 재미있는 약수의 성질(백준 13909번 : 창문닫기) 오늘은 실버 5단계인 백준 13909번 창문닫기 리뷰입니다.(문제 해결법을 깨닫고 재밌어서 바로 글남김) 문제를 요약하자면, N번째 사람은 N의 배수인 창문을 닫거나 열어서 마지막에 몇 개의 창문이 열려있는지 맞히는 문제 문제 해결을 위해 7번째 사람까지 메모장에 작성해 보며 찾은 규칙성은 N의 약수의 개수가 짝수면 창문이 열리고 홀수면 닫히는 것이다. 그래서 작성한 코드는 아래와 같다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Number_.. 2023. 12. 5.
유클리드 호제법 오늘은 백준 알고리즘 1735번을 풀면서 접하게 된 유클리드 호제법에 대하여 정리해보겠습니다. 유클리드 호제법(Euclidean Algorithm)은 두 개의 자연수의 최대공약수를 구하는 알고리즘이다. 유클리드 호제법의 핵심은 두개의 자연수 a, b에 대하여 a를 b로 나눈 나머지를 r이라고 한다면, a와 b의 최대공약수와 b와 r의 최대공약수는 같다는 것이다. 이 핵심에 따라 b를 r로 나눈 나머지를 r`라고 한다면 다시 r를 r`로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나눈 수가 최대공약수가 되는 것이다. 유클리드 호제법을 사용하여 최대공약수를 구하는 과정을 설명하면 좋겠으나 귀찮기도 하고 핵심만 안다면 코드로 구현하는 것은 어렵지 않다고 생각한다. 반복문으로 a, b 자리에.. 2023. 12. 3.
자바 Map관련 알고리즘 문제 리팩토링 과정 기록 정말 오랜만에 글을 쓴다. 이제부턴 조금 편하게 글을 써 내려가도록 마음을 먹었다. 그리고 말투도 편하게 독백체로... 독백체가 좀 더 감정이 잘 실리고 글도 술술 잘 적힌다. 오늘 포스팅은 백준 알고리즘 10816번을 풀다가 초기 코드에서 리팩토링을 해간 과정이 재밌어서 기록해 둔다. 먼저 백준 알고리즘 10816번에 대해 단계별로 풀어가고 있는데 현재는 집합과 Map 단계인데 이 문제가 실버 4 수준인지는 잘 모르겠다. Map이라는 자료구조가 들어가서 그런가... 문제 자체는 굉장히 직관적이게 숫자 카드의 개수를 Map에다가 저장하면 된다. 아래는 초기 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOE.. 2023. 12. 1.
[백준 알고리즘][자바] 1475번 : 방 번호 https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 특별한 알고리즘은 없지만, 반례에 대해 다시 생각해 보게 돼서 작성하게 되었습니다. 방 번호의 숫자를 카운팅하여 max값을 출력하면 되는 간단한 문제입니다. 다만, 처음 코드를 작성할 때, 6와 9를 묶어서 6으로 카운팅 한 후에 홀수냐 짝수냐를 판별해서 다시 계산해 주는 부분을 max값 뒤에다가 작성하다보니 더 높은 카운트 숫자가 앞에 있음에도 불구하고 max가 6으로 잡히는 경우가 생겼습니다. 알고리즘 문제를 풀면서 반례를 찾아야 할 때, 아래를 중점적으로 보면 좋을 거 같습니다.. 2023. 5. 5.
[백준 알고리즘][자바] 1158번 : 요세푸스 문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제에 분명 "1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고" 라고 순환되는 LinkedList 계열이라고 힌트를 줬는데 배열 형식으로 문제를 해결하려다 보니 시간을 많이 잡아먹게 되었습니다... 처음에는 아래의 코드를 ArrayList로 제출을 했더니 시간초과가 나서 혹시나 싶어서 LinkedList로 변경하여 제출했는데 아슬아슬하게 통과했습니다. 아마도 데이터 추가와 삭제가 일어날때, ArrayList는 데이터가 Shift 되면서 더 시간을 잡아먹어서 그런게 아닐까라고 생각해.. 2023. 4. 26.
[백준 알고리즘][자바] 4673번 : 셀프넘버, 자릿수 판별하는 방법 https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 생성자는 자기 자신 + 각각의 자릿수이다. 예를 들어 101은 101 + 1 + 0 + 1 = 104로 101은 104의 생성자입니다. 이때, 생성자가 없는 숫자를 셀프 넘버라고 하는데, 10000보다 작거나 같은 셀프 넘버를 출력합니다. 이 문제에서 각각의 자릿수를 판별하여 더해야 하는데, 그 알고리즘 기록을 위해 포스팅을 작성합니다. impor.. 2023. 4. 24.
[백준 알고리즘][자바] 2577번 : 숫자의 개수 https://www.acmicpc.net/problem/2577 2577번: 숫자의 개수 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다. www.acmicpc.net 문제 자체는 간단한 문제입니다. 세 개의 자연수 A, B, C의 곱의 값이 0부터 9까지의 숫자가 각각 몇번 쓰였는지 출력하면 되는 문제입니다. 이 문제를 포스팅하는 이유는 숫자로 이루어져있는 String 타입의 문자열을 char로 나누고 다시 int형으로 변환시키는 코드를 기록하기 위함입니다. int뿐만 아니라 다시 각각 String으로도 변환 가능하겠네요. import java.io.BufferedReader; import java.io.Buffe.. 2023. 4. 24.
반응형

티스토리툴바