본문 바로가기

Algorithm/Baekjoon65

[백준][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.
[백준 알고리즘][자바] 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.
[백준 알고리즘][자바] 2480번 : 주사위 세개 https://www.acmicpc.net/problem/2480 2480번: 주사위 세개 1에서부터 6까지의 눈을 가진 3개의 주사위를 던져서 다음과 같은 규칙에 따라 상금을 받는 게임이 있다. 같은 눈이 3개가 나오면 10,000원+(같은 눈)×1,000원의 상금을 받게 된다. 같은 눈이 2개 www.acmicpc.net 백준 알고리즘 구현 파트를 브론즈 4 정도부터 풀고 있는데, 부족함을 많이 느끼네요. 코드를 구현할 때 for문에 너무 집착하는 경향이 있는 것 같습니다... 이 문제의 포인트는 같은 눈이 몇 개인지를 구해야 하는 것입니다. 아래는 제가짠 코드 for문을 통해 같은 수가 존재 하는지 flag를 통해 저장하고 다시 전체 for문을 통해 같은 눈이 몇개인지와 max값을 구했습니다. 그리.. 2023. 4. 20.
[백준 알고리즘][JAVA] 2439번 : 별 찍기 - 2 https://www.acmicpc.net/problem/2439 2439번: 별 찍기 - 2 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제 하지만, 오른쪽을 기준으로 정렬한 별(예제 참고)을 출력하시오. www.acmicpc.net 이번 문제는 일반적인 별 찍기 문제와 다른 점은 오른쪽 정렬입니다. 풀이법은 먼저 (N - i) 만큼 공백 출력 후 i만큼 별을 찍습니다. for문을 돌려 갯수만큼 공백과 별을 찍으면 해결 되겠지만, 문자열 곱셈을 활용하여 문제를 해결하였습니다. \0은 문자열의 끝을 찾아주는데, 그것을 공백과 별로 replace 시켜 문자열을 완성합니다. import java.io.BufferedReader; import java.io.BufferedWr.. 2023. 4. 19.
[백준 알고리즘][자바] 10814번 : 나이순 정렬 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 이번 문제는 안정 정렬(Stable Sort)에 관한 문제입니다. 입력으로 사람들의 나이와 이름이 가입한 순서대로 주어집니다. 이때 회원들을 나이순으로 정렬하고, 나이가 같으면 먼저 가입한 사람이 앞에 오도록 정렬해야 합니다. 안정 정렬(Stable Sort)이란 정렬을 마쳤을 때 동일한 키값을 가진 요소의 순서가 유지되는 것을 의미합니다. 예를들어, 1, 3, 5, 7, 3 를 정렬한다면 정렬 후에 .. 2022. 7. 14.
반응형

티스토리툴바