Algorithm
-
백준 14467 - 소가 길을 건너간 이유(JAVA)Algorithm 2022. 9. 25. 14:01
14467번: 소가 길을 건너간 이유 1 (acmicpc.net) 14467번: 소가 길을 건너간 이유 1 3번 소는 위치 1, 0, 1에서 관찰되었으므로 길을 최소 두 번 건넜음을 확인할 수 있다. 4번 소도 길을 한 번 건넜으며, 나머지 소는 길을 건넌 기록이 확인되지 않는다. www.acmicpc.net 오늘 풀어본 문제는 소가 길을 건너간 이유이다. 이 문제는 두 번째 열에서 1과 0의 position이 바뀌는 시점을 잘 파악하여 그때 마다 count를 올려주면 해결될 수 있을 것이라고 생각했다. ※ 알고리즘 1. 숫자를 입력받고 소가 총 10마리 있으므로 2차원 배열로 행렬을 표현해 준다. 2. 두 번째 열에 0을 입력해 두고 행이 10번 바뀔 수 있으므로 반복문을 이용해 arr[i][0]을 고..
-
백준 2902 - KMP는 왜 KMP일까? (JAVA)Algorithm 2022. 9. 20. 10:23
이번 주 코테 study의 마지막 문제이다. 2902번: KMP는 왜 KMP일까? (acmicpc.net) 2902번: KMP는 왜 KMP일까? 입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 ('-', 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드 www.acmicpc.net KMP와 같은 약자를 만드는 문제인데 나는 단어를 쪼개는 StringTokenizer를 잘 쓰면 해결 될 수 있는 문제라고 생각했다. ※ 알고리즘 1. StringTokenizer를 사용하여 "-" 단위로 단어를 쪼개준다. 2. 단어 마다의 맨 앞 글자를 StringBuilder에 append 시키고 더 이상 단어가 없으면 Stri..
-
백준 1225 - 이상한 곱셈(JAVA)Algorithm 2022. 9. 20. 09:48
오늘 풀어볼 문제는 백준 1225번 이상한 곱셈이다. 1225번: 이상한 곱셈 (acmicpc.net) 1225번: 이상한 곱셈 첫째 줄에 A와 B가 주어진다. 주어지는 두 수는 모두 10,000자리를 넘지 않는 음이 아닌 정수이다. 수가 0인 경우에는 0만 주어지며, 그 외의 경우 수는 0으로 시작하지 않는다. www.acmicpc.net 문제는 위 링크를 참조하자. ※ 알고리즘 1. 숫자 두개를 입력받는다. 2. 두개의 숫자를 이중 for문으로 순회하며 각 숫자를 뽑아내면 된다. 3. 숫자를 string형으로 뽑아내어야 charAt()을 사용하여 쉽게 한자리씩 뽑아낼 수 있다. 4. 결과 변수에 더하고 출력 알고리즘을 그대로 구현하면 위와 같다. String 형태의 A와 B 숫자를 length()로 ..
-
백준 2798 - 블랙잭(JAVA)Algorithm 2022. 9. 18. 14:39
오늘은 백준 2798 블랙잭 문제를 가져와 보았다. 2798번: 블랙잭 (acmicpc.net) 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제는 위 사이트를 참고하기 바란다. 처음에 입력해야 할 사항들이 많아서 조금 당황했는데 크기 N의 배열을 만들면 모든 입력을 쉽게 받을 수 있었다. ※ 알고리즘 딱히 큰 알고리즘이 필요가 없는 문제였다. 결국 순회를 하면서 세 개의 숫자를 선택하는 방식을 택하면 되기 때문에 전형적인 전체 순회 "브루트 포스" 문제임을 알 수 있었다...
-
백준 2231 - 분해합(JAVA)Algorithm 2022. 9. 16. 10:49
9/15일에 study원들과 코테 스터디를 진행하고 뽑아 본 5개의 문제 중 하나를 풀어 보았다. 2231번: 분해합 (acmicpc.net) 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 ..
-
백준 1173 - 운동(JAVA)Algorithm 2022. 9. 16. 09:43
예전에 풀어둔 문제 였는데 최근 수 많은 일들로 인해 오늘에서야 포스팅을 한다. 1173번: 운동 (acmicpc.net) 1173번: 운동 첫째 줄에 다섯 정수 N, m, M, T, R이 주어진다. www.acmicpc.net 문제 영식이가 운동을 하는 과정은 1분 단위로 나누어져 있다. 매 분마다 영식이는 운동과 휴식 중 하나를 선택해야 한다. 운동을 선택한 경우, 영식이의 맥박이 T만큼 증가한다. 즉, 영식이의 맥박이 X였다면, 1분 동안 운동을 한 후 맥박이 X+T가 되는 것이다. 영식이는 맥박이 M을 넘는 것을 원하지 않기 때문에, X+T가 M보다 작거나 같을 때만 운동을 할 수 있다. 휴식을 선택하는 경우 맥박이 R만큼 감소한다. 즉, 영식이의 맥박이 X였다면, 1분 동안 휴식을 한 후 맥박은..
-
백준 2292 - 벌집(JAVA)Algorithm 2022. 9. 13. 09:58
코테의 중요성이 슬슬 느껴지다보니 다시 코딩테스트 공부를 시작해 보려 한다. 오늘은 가볍게 브론즈 2의 백준 2292번 벌집 문제를 풀어보았다. 2292번: 벌집 (acmicpc.net) 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 벌집 문제를 잘 살펴 보면 처음에 빙빙 도는 것에 집중하여 "??? 어쩌라는거지?" 라는 생각이 들 수 있다. 그러다가 결국 우리가 주목할 지점은 몇 개의 방을 지나가는지를 count하는것에 초점이 맞추어 졌다. 처음 1은 count : 1 두번째 2~7은 count : 2 세번째 8~..
-
3/2기록 - 백준 2635Algorithm 2022. 3. 2. 15:38
이전 문제가 너무 간단하게 해결이 되어서 양심상 한 문제를 더 풀어보았다. 백준 2635번 수 이어가기 문제이다. 이 문제는 첫번째 수로 주어진 수에서 최대로 만들 수 있는 빼기 수를 찾아내는 것이다. 앞 수 - 뒷 수 = 그 다음 세번째 수 이런식으로 나열이 되고 몇개까지 수가 만들어질 수 있는지와 앞 수 - 뒷 수 = 음수가 나오게 되면 종료가 된다. 알고리즘 생각 1. max 숫자를 출력할 list와 실제로 처리를 담당할 list를 만든다. 2. 실제 처리 리스트를 1~N까지의 반복문 안에서 형성한다. 3. N과 그 다음 수 i를 담는다. 4. 계산을 위한 first와 second 변수를 N과 i로 각각 선언한다. 5. while(true) 반복문 안에서 result 변수를 first - secon..