HELLOnayeon

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net [실패한 코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class B_1676 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Intege..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제를 딱 보고나서 점화식이라는 방법이 떠오르지 않아 그냥 구현했더니 틀렸다. 찾아보니까 점화식을 사용해서 푸는 문제라고 나와있었다. 잊어버릴 수 있으니 정리를 해보려고 한다. - 1을 뺄 때는 d[i] = d[i-1] + 1 - 2로 나눌 수 있을 때는 d[i] = d[i/2] + 1 - 3으로 나눌 수 있을 때는 d[i] = d[i/3] + 1 초기값은 dp[1] = 0 으로 설정한다. * 점화식 i 를 계산하는 방법에는 총 3가지가 있다. 2로 나눈 나머지가 0일 경우, 2로 나눈다. 3으로 나눈 나머지가..

HashMap 을 사용하여 알고리즘 문제를 푸는데 모르는 부분이 있어 정리하고자 한다. https://www.acmicpc.net/problem/1302 [문제] 김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다. [입력] 첫쨰 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000 보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다. [출력] 첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 ..

주어진 자료에서 중복되지 않은 값이 주어질 때 그 데이터 내에 특정 값이 존재하는 지 검색하는 방법 중 이분탐색(Binary Search)은 자료를 정렬한 후 분할정복방식으로 데이터를 1/2씩 나누면서 값이 존재하는 지 확인하는 알고리즘을 사용했다. 이분탐색이 데이터 내 특정 값을 정확히 찾는 것이라면 lower_bound 와 upper_bound 는 이분탐색 알고리즘에서 약간 변형된 것으로 중복된 자료가 있을 때 유용하게 탐색할 수 있는 알고리즘이다. lower_bound 는 데이터 내 특정 K 값보다 같거나 큰 값이 처음 나오는 위치를 리턴해주고 upper_bound 는 K 값보다 처음으로 큰 값이 나오는 위치를 리턴해주는 알고리즘이다. 이분탐색 코드 구현 int binarySearch(int A[]..

풀이 과정 흰색 또는 검은색으로 칠해진 N × M 칸을 이룬 판에서 정해지지 않은 위치에서 8 × 8 의 사각형으로 잘라서 체스판을 만든다. 그 후 공유하는 변이 겹치지 않게 색을 칠하는데 가장 적은 칸을 칠해야하는 최솟값을 구하는 문제이다. 사각형을 한 칸씩 움직이면서 하나하나 칸을 비교하면서 문제를 풀어야 한다. 2가지 방법 : 보드판을 char 와 boolean 으로 받는 방법을 이용했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class B_1018_2 { private static final cha..

이 문제는 완전 탐색, 브루트 포스에 관한 문제이다. 완전 탐색, 브루트 포스란 무엇인가? 브루트 포스를 사전적 의미로 찾아본다면 다음과 같다. 브루트(Brute) : 무식한 + 포스(Force) : 힘 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다. * 장점 - 알고리즘을 설계하고 구현하기 매우 쉽다. - 복잡한 알고리즘 없이 빠르게 구현할 수 있다. * 단점 - 알고리즘의 실행 시간이 매우 오래 걸린다. - 메모리 효율면에서 매우 비효율적이다. # 브루트 포스의 종류 브루트 포스는 크게 선..

구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있다. 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미한다. 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다. 대표 예제 2.시각 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다. ..

구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있다. 완전탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미한다. 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다. 대표 예제 1. 상하좌우 여행가 A는 N×N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 ..

그리디 알고리즘 = 탐욕법이라고 말한다. 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 대표 예제 3. 숫자 카드 게임 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 1. 숫자가 쓰인 카드들이 N × M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다, 3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮을 카드를 뽑을 것을 고려하여 최종적으로 가장 높..

그리디 알고리즘 = 탐욕법이라고 말한다. 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 대표예제 2. 큰수의 법칙 '큰 수의 법칙' 은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로 2, 4, 5, 4, 6 으로 이루어진 배열이 있을 때, M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 ..