Algorithm, Problem Solving62

• 

  [백준][Java] 2230 - 수 고르기 목차 문제 정보 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 난이도 : G5 유형 : 투포인터, 이분탐색 시간 : O(NlogN) 문제 풀이 투포인터와 이분탐색을 같이 사용하여 풀이를 했다. 투포인터는 왼쪽, 오른쪽 포인터를 이용하는 개념이다. 왼쪽 포인터는 순차적으로 수열의 인덱스로 사용하였고 오른쪽 포인터는 이분탐색으로 얻은 인덱스로 사용하였다. 주의할 점은 이분탐색을 하기 전에는 미리 정렬을 해주어야 한다. 코드 i.. Algorithm, Problem Solving/백준(boj) 2023. 3. 30.

• [codeforces][Kotlin] 1475A - Odd Divisor 목차 문제 정보 https://codeforces.com/problemset/problem/1475/A Problem - 1475A - Codeforces codeforces.com 난이도 : A 유형 : Math 문제 풀이 주어진 숫자가 짝수일 경우 2로 계속 나누어서 홀수로 만든 다음 결괏값이 3 이상인 홀수이면 정답이다. 코드 import java.io.BufferedReader import java.io.InputStreamReader fun solution() = with(BufferedReader(InputStreamReader(System.`in`))) { var sb = StringBuilder() var t = readLine().toInt() while (t-- > 0) { var in.. Algorithm, Problem Solving/codeforces 2023. 3. 29.

• 

  [백준][Java] 12904 - A와 B 목차 문제 정보 https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 난이도 : G5 유형 : 그리디, 문자열 문제 풀이 문자열을 변환하는 방법은 2가지밖에 없다 1. 마지막에 A를 추가 2. 거꾸로 만든 후 B를 추가 S문자열에 1, 2번 연산을 어떻게 처리해도 결국 마지막에 A 혹은 B만 올 수 있다. 그럼 T 문자열을 기준으로 보자 1. T의 문자열 마지막이 A이면 1번 연산이 진행된 것이고 2. T의 문.. Algorithm, Problem Solving/백준(boj) 2023. 3. 29.

• [codeforces][Kotlin] 703A - Mishka and Game 목차 문제 정보 https://codeforces.com/problemset/problem/703/A Problem - 703A - Codeforces codeforces.com 난이도 : A 유형 : implementation 시간 : O(n) 문제 풀이 승리가 많은 사람을 출력 코드 import java.io.BufferedReader import java.io.InputStreamReader import java.util.StringTokenizer fun solution() = with(BufferedReader(InputStreamReader(System.`in`))) { var mCnt = 0 var cCnt = 0 var n = readLine().toInt() for (i in 0 unti.. Algorithm, Problem Solving/codeforces 2023. 3. 28.

• 

  [백준][Java] 2212 - 센서 목차 문제 정보 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 난이도 : G5 유형 : 정렬, 그리디 시간 : O(N + NlogN) 문제 풀이 거리를 최소로 만들려면 직관적으로 K만큼 기지국을 설치하면 된다는 것을 알 수 있다. 또한 이문제를 쉽게 이해하기 위해 센서를 K개의 집합으로 나눠서 생각해 보자. 빨간 세모 : 센서 빨간색 숫자 : 센서 위치 파란색 숫자 : 바로 옆에 있는 센서와의 거리 위 그림에서 기지국.. Algorithm, Problem Solving/백준(boj) 2023. 3. 28.

• 

  [백준][Java] 15486 - 퇴사 2 목차 문제 정보 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 난이도 : G5 유형 : DP 시간 : O(N) 문제 풀이 n이 1,500,000 이여서 시간초과를 피하기 위해 O(N) 이하로 풀어내야 한다. 따라서 일차원 배열을 이용한 DP로 해결을 했다. 1일부터 시작하여 N일까지 순차적으로 DP테이블을 갱신해줬다 dp배열은 N+1만큼 선언해 주고 dp[0] = 0으로 초기화 점화식) dp[i + T[i] -1.. Algorithm, Problem Solving/백준(boj) 2023. 3. 28.

• [codeforces][Kotlin] 313A - Ilya and Bank Account 목차 문제 정보 https://codeforces.com/problemset/problem/313/A Problem - 313A - Codeforces codeforces.com 난이도 : A 유형 : Math 문제 풀이 입력값이 양수) 입력값 자체가 정답 입력값이 음수) 자릿수가 1개라면 정답은 0 그 외인 경우 첫 번째 자리를 뺀 수 vs 두 번째 자리를 뺀 수 중 더 큰 값이 정답 코드 import java.io.BufferedReader import java.io.InputStreamReader fun solution() = with(BufferedReader(InputStreamReader(System.`in`))) { var input = readLine().toInt() if (input <.. Algorithm, Problem Solving/codeforces 2023. 3. 27.

• [백준][Java] 6593 - 상범 빌딩 목차 [프로그래머스][Kotlin] - [codeforces][Kotlin] - 문제 정보 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 난이도 : G5 유형 : BFS 문제 풀이 상 하 동 서 남 북 6가지 방향으로 이동할 수 있는 3차원 BFS 문제 스탠다드한 BFS풀이에서 z축으로 확장만 시켜주면 쉽게 풀 수 있는 문제이다. 아래 코드를 최적화한다면 출구를 만났을 때 다시 큐에 넣지 말고 바로 탐색을 종료하면 된다. 코드 import jav.. Algorithm, Problem Solving/백준(boj) 2023. 3. 27.

• [백준][Java] 2668 - 숫자고르기 목차 문제 정보 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 난이도 : G5 유형 : 그래프탐색, DFS 문제 풀이 싸이클을 구하는 문제이다. 필자는 재귀가 아닌 while반복문으로 풀었다. 이문제에는 재귀보단 반목문이 더 최적화인 풀이일 것이다. ( 메모리, 시간이 더 적게 소모된걸 확인) 윗줄에서 숫자 1개를 선택했을 때 결국 다시 뽑은 숫자로 돌아오는지 확인해 주면 된다 ex) 1 2 3 4 5 6 2 4 1 3 6 5 1.. Algorithm, Problem Solving/백준(boj) 2023. 3. 27.

• [백준][Java] 2023 - 신기한 소수 문제 정보 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 난이도 : G5 유형 : 재귀, 정수론, 소수판정, 백트래킹 문제 풀이 문제 메모리 조건을 때문에 미리 소수배열을 만들어 놓으면 메모리 초과가 뜰 것이다. 그래서 어떤 수가 소수인지 동적으로 판별하여야 한다. 풀이 방법 - 예시 - 5939) 첫번째 수가 소수이다. (5) -> 첫째둘째 수가 소수이다. (59) -> 첫째둘째셋째 수가 소수이다. (593) -> ... N자리까.. Algorithm, Problem Solving/백준(boj) 2023. 3. 26.

• [백준][Java] 20055 - 컨베이어 벨트 위의 로봇 목차 문제 정보 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 난이도 : G5 유형 : 구현, 시뮬레이션 문제 풀이 개인적으로 문제의 내용 설명이 불친절하다고 느꼈다. 문제에 주어진 1 ~ 4 수행과정을 1 세트로 묶어서 카운팅 하여야 한다. 문제 말대로하면 1 ~ 4 과정을 모두 세서 카운팅하여야 하는데, 그러면 오답이 나올 것이다. 코드 import java.io.BufferedReader; import java.io.. Algorithm, Problem Solving/백준(boj) 2023. 3. 26.

• [codeforces][Kotlin] 466A - Cheap Travel 목차 [백준][Java] - [프로그래머스][Kotlin] - 문제 정보 https://codeforces.com/problemset/problem/466/A Problem - 466A - Codeforces codeforces.com 난이도 : A 유형 : 그리디, Math 문제 풀이 세트의 표의 1장당 가격 vs 일반 1장당 가격 둘이 비교해서 그리디 하게 선택하면 된다. 코드 import java.io.BufferedReader import java.io.InputStreamReader import java.util.StringTokenizer fun solution() = with(BufferedReader(InputStreamReader(System.`in`))) { var st = Strin.. Algorithm, Problem Solving/codeforces 2023. 3. 25.