1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/1934(2) 해설🕵최대공약수와 최소 공배수의 관계를 알고 있는지 묻는 문제2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: 유클리드 호제법유클리드 호제법의 개념만 알면 문제가 쉬워서 바로 SUDO CODE로 넘어가겠다. 혹시 개념에 대해 모르시는 분들은 다음 두 개의 포스팅을 한번 읽고 오시길 바란다.https://dalcheonroadhead.tistory.com/485https://dalcheonroadhead.tistory.com/486(2) SUDO CODE 📜1️⃣ 입력으로 받은 A, B의 최대공약수 G를 구한다.2️⃣ G 로 A,B를 나눠서 몫인 a, b를 얻는다...

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/11689(2) 해설🕵오일러의 피를 알고 있는지 묻는 문제이다. 오일러의 피 함수 $φ(n)$ 이란, n 이하 자연수 중 n과 서로소인 숫자의 개수를 반환하는 함수이다.저번 오일러의 피 이론 정리 포스팅에서는 N개의 영역 내의 모든 수에 대한 오일러의 피 함수를 구했는데, 이번 문제는 N의 최대값이 $10^{12}$ 여서 그러한 배열을 만들 수도 없고, 문제에서도 N 하나에 대한 오일러 피 함수를 구하라 했으므로, N에 대해서만 오일러 피 함수를 구하면 된다.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: 에라토스테네스의 체, 오일러 피 함수에라토스테네스의 체를 따로 구할 메모..

0. 무엇을 정리하나요필자는 문자열을 뒤집는 기술이 필요할 때, StringBuilder클래스의 reverse()를 자주 활용한다. 근데, 펠린드롬 수를 빠르게 구하기 위해, 다음과 같이 문제를 푸니 틀리는 것 아닌가! StringBuilder straight = new StringBuilder(num);StringBuilder reverse = new StringBuilder(num).reverse();콘솔에 찍어보니 두 객체 모두에 어떠한 입력값도 들어가지 않았다! 코테에서 이러한 에러를 겪었으면 적잖이 당황했을 것 같다. 오늘은 필자와 같이 당황할 사람들을 위해, StringBuilder의 생성자에 int i를 넣는 것과 String str을 넣는 것의 차이를 알아보려 한다.1. ne..

1. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: 에라토스테네스의 체, 문자열1️⃣ N의 최대값의 2배에 해당하는 부분에 대하여 소수 전부 찾아놓기 (N의 최대값: 1,000,000이라 가능)2️⃣ 입력 받기3️⃣ 입력보다 크거나 같은 값 중 펠린드롬 (뒤집어도 같은 수)인지 확인하기.(1) 시간복잡도 분석 🕓임의의 수: $N$ (최대값: 1,000,000) 에라토스테네의 체 만들기: $O(2N \log (\log 2N))$펠린드롬 수 찾기: input에서 제일 가까운 소수 이자 펠린드롬 수를 찾는 것이므로, 시간 복잡도 따로 계산하지 않아도 될 만큼 작은 반복안에 찾음.3. 코드 소개 🔎(1) SUDO CODE0️⃣ 1에서 2,000,000까지의 영역에서 소수 전부 찾아놓기1️⃣ ..

1. 문제 설명 📌문제 링크일반적인 매개변수 탐색이나 이분 탐색 문제보다 까다로웠던 점은,1️⃣ 통나무의 자를 수 있는 위치가 정해져 있다.2️⃣ 통나무의 가장 긴 조각을 작게 만들었을 때, 제일 처음 자른 위치도 같이 출력 해라.였다. 이걸 유념하며 문제를 풀어야 한다.2. 구현 방법 🗃️KEY WORD: Parametric Search, Binary Search, Greedy Algorithm0️⃣ 통나무를 자를 수 있는 위치를 받아서 오름차순으로 정렬한다.1️⃣ 이분탐색으로 통나무의 가장 긴 조각의 최소값을 구한다. 구하는 방법은 다음과 같다.1️⃣-1) f(w) = 모든 조각난 통나무의 길이가 w 이하인가? 라는 결정문제 함수를 만든다. 이를 만족하는 f(w) 중 가장 오른쪽에 있는 f(w)의..

1. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: 에라토스테네스의 체문제에서 주어진 영역의 최소값 A, 최대값 B, 임의의 소수 K에 대하여, $A 0️⃣ $A 가능한 K를 모두 구하기 위해, n을 2라고 치고, 양변을 모두 2의 제곱근으로 나눈다. $√A 1️⃣ 1 에라토스테네스의 체), √√B까지의 숫자를 살펴보면 될 것이다.2️⃣ 구해진 소수들을 계속 제곱하며, B보다 작을 때까지 가능한 수의 개수를 센다. 이때 우리는 Long이 아닌 Double 자료형을 사용한다. double 자료형은 지수표기법으로 값을 나타내기 때문에 정밀도는 조금 떨어질 수 있으나, Long보다 큰 값도 overflow 없이 표현 가능하다. 이번 문제가 정확한 값을 구하는 것이 아닌 대소 비교임으로 충분히 ..

1. 슬라이딩 단조 큐란 무엇인가요?슬라이딩 단조 큐란, DECK을 활용해 구현한 슬라이딩 윈도우로, 슬라이딩 윈도우 구간 내의 최소값, 최대값을 O(1)에 찾기 위해 고안한 구현체이다. 단조라는 이름이 붙은 이유는, 구간 내 최소값을 찾고 싶을 경우, Deck 내부 원소들이 오름차순으로 유지되고, 구간 내 최대값이 찾고 싶은 경우 내림차순으로 유지되기 때문이다.사실 내가 만든 이름이다...😂슬라이딩 윈도우 심화 문제를 풀면서, 슬라이딩 윈도우를 Deck으로 구현한 형태가 꾸준히 나오는데, 인터넷 여기 저기 찾아봐도, 형태만 있을 뿐 이것의 제대로 된 이름이 없었다.따라서 정식 명칭은 아니지만! 설명의 편의를 위해 앞으로 현 구간 내의 최소값과 최대값을 찾기 위해 Deck으로 구현한 슬라이딩 윈도우를 ..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: GREEDY ALGORITHM(1) 목적지의 x축 혹은 y축에 일치할 때까지 대각선 가로지르기로 이동한다. 비용 = Math.min(2*S, W)(2) 목적지와 x축 혹은 y축이 일치한 이후에는 한칸 이동과 대각선 가로지르기 중 최소 비용을 택해서 이동한다.a. S > W인 경우 (목적지 - 현 위치) == 짝수일 경우 W로만 이동, 홀수 일 경우, 목적지-1까지 W로 이동 후 마지막 한 번을 S로 이동b. S 인 경우, S로 쭉 이동 3. 코드 소개 🔎import java.io.*;import java.util.Arrays;import java.util.StringTokenizer;public class Main { /* ..

1. 문제 설명 📌✨ 문제 링크 ✨문제 설명이 꽤 직관적이다. 다만 내가 한 번에 이해하지 못한 부분이 있어, 그에 대한 부연 설명을 하고 다음 장으로 넘어가겠다.교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).문제의 입력으로 일련의 데이터가 공백으로 구분되어 주어지는데, 해당 데이터의 index = 공장, value = 해당 공장에서 사야할 라면의 개수 라는 뜻이다.2. 접근 방식 🗃️KEY WORD: DP(가) 문제에서 주어진 3가지 방법을 숙지한다.i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다.i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다.i번 공장과 ..

1. 문제 설명 📌문제 링크한 개 이상의 일이 존재하고, 일마다 시작시간, 끝시간, 완료했을 때 이익 이 주어질 때, 주어진 일련의 일들에서 나올 수 있는 최대 이익을 반환하라.조건선택한 일들은 서로 일의 진행 시간이 겹치면 안된다.A라는 일의 endTime = X 이고, B라는 일의 startTime = X이면 A와 B를 연달아 일할 수 있다. 이는 겹치는 것으로 간주하지 않는다.2. 접근 방식 🗃️KEY WORD: DP(1) 초기화(가) 각각 산재되어 있는 startTime, endTime, profit을 같은 일 단위로 묶어서 나열 ➜ class Job + ArrayList(나) ArrayList를 시작 시간이 이른 순으로 정렬(다) DP용 배열 maxProfit[] 만들기 (maxProfit[..

1. 문제 설명 📌문제 링크해당 문제는 자신이 사용하는 언어의 내부 라이브러리 정렬을 사용하지 않고 O(nlog(n))에 문제를 푸는 것이 관건이다.(문제에서도 진짜 라이브러리 정렬을 썼는지 안 썼는지는 양심에 맡겼다...)2. 접근 방식 🗃️Key word: Merge sort병합 정렬의 최악의 시간 복잡도가 O(nlog(n))이기 때문에 쓰면 풀린다. 하지만 한 가지 백준과 다른 점이 있어 1시간 동안 헤멘 부분이 있다. 리트코드는 알고리즘 자체의 시간 뿐만 아니라, 자료구조를 사용하며 생기는 메모리 오버 헤드, 가비지 컬랙션 부담에 따른 실행 시간 증가 또한 실행시간에 포함시키는 듯 하다.그렇게 느낀 이유는 내가 Merge_sort를 하면서 부분 정렬된 값들을 넣을 tmp 임시 배열을 매 재귀..

1. 문제 설명 📌문제 링크2. 접근 방식 🗃️KEY WORD: QUICK SORTING사실 JAVA 내부 라이브러리에 있는 Sorting을 쓰면 간단히 해결되는 문제이지만, Qucik Sorting 연습을 위해 Quick Sorting을 사용해 보았다. quick sorting의 경우, 최악의 시간 복잡도가 O( $N^2$ )이라서 문제에 제시된 최대 데이터 량을 보면, 시간초과가 나야 하는 것이 맞다. (아마 Quick Sorting을 쓰면 시간 초과가 나는 테스트 케이스를 안 넣어놓은 것 같다.)(1) 큰 흐름(1) 현재 정렬해야 하는 영역의 중앙값을 PIVOT으로 선정(2) PIVOT을 영역 최좌단 값과 자리 교체. (pivot은 비교 대상에 속하지 않도록 하기 위함.)(3) PIVOT을 제외..

1. 문제 설명 📌문제링크문제 설명이 직관적이라 설명 생략2. 접근 방식 🗃️KEY WORD: custom Sorting정렬 문제 였지만, 직접 정렬 알고리즘을 구현하는 문제는 아니었고, 정렬의 기준을 직접 제작하는 것이 중요한 문제였다. 필자는 문제를 처음부터 정렬 알고리즘 직접 구현으로 가닥을 잘못 잡고 들어가서 엄청 헤멨다. 해당 내용은 배운 것들에 더 자세히 기술 하고 여기서는 어떻게 접근해야 하는지에 초점을 맞추겠다.(1) 정렬 기준Numbers 배열의 원소 중 임의의 하나를 A, A의 다음 원소를 B라고 하자. 이 숫자들을 문자열이라 가정했을 때, 다음과 같이 이어 붙일 수 있을 것이다. AB 형태BA 형태이 두 형태 중 무엇이 큰지를 대소 관계 비교하면 된다.AB > BA , A가 앞에 ..

1. Quick 정렬은 무엇인가?Pivot(중추)가 되는 값을 하나 선정해서 그 값보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 모은다. 이제 나눠진 두 그룹 내에서 다시 Pivot을 선정하고 이 과정을 반복한다. 값을 더 이상 쪼갤 수 없을 때까지 반복하면 모든 값이 정렬되어 있다.2. 원리병합정렬과 마찬가지로 분할 정복을 활용하는 또 다른 예시이다. 병합 정렬에서는 선 분할 후 정복 이었다면, quick 정렬은 선 정복, 후 분할 형식이라 생각하면 되겠다.정복에는 마주보는 투 포인터가 활용된다. 어떻게 쓰이는지는 밑의 예시에서 자세히 설명하겠다. (1) Pivot 정하기 (정하는 방식은 때에 맞게 자유)(2) Pivot보다 큰 값은 오른쪽으로 몰기, 작거나 같은 값은 왼쪽으로 몰기 (정복 by 투 포..

1. 문제 설명 📌문제 링크일련의 수가 1차원 배열 형식으로 주어진다. 이때 수들 중 임의의 수 하나를 다른 수 두개의 합으로 나타낼 있을 때, 이 임의의 수를 좋은 수라고 한다. 이러한 좋은 수가 배열 내에 몇 개인지 구하라2. 접근 방식 🗃️Key Word: Two-way Two Pointer두 포인터의 합 > target: R 포인터를 한 칸 내려 합을 하향 조정두 포인터의 합 : L 포인터를 한 칸 올려 합을 상향 조정두 포인터의 합 == target: 답을 +1 올리고 반복문 종료(1) 시간 복잡도는? N = 2000 으로 이중 반복문까지 허용 범위이다. 따라서N개 중에 하나 Target 값으로 찾기 (O(N))두 포인터 움직이며 Target 값 만들 수 있는지 찾기 (O(N))두 움직임은 ..

1. 문제 설명문제 링크서로 연결되어 있는 그래프를 하나의 군집체로 볼 때, 주어진 전체 노드에서 군집체가 총 몇 개 있는지 구하는 문제이다. 2. 접근 방식인접 리스트 형태로, 노드와 연결 정보를 저장한다. 방문 배열을 만들고 방문하지 않은 배열을 기점으로 BFS를 실행한다.한 번 BFS를 돌면, 시작 정점과 연결된 모든 정점은 방문 처리가 될 것이다. 이는 하나의 군집체를 조회한 걸로 볼 수 있다. 따라서 BFS를 돈 횟수만큼 군집체가 존재하는 것이므로, BFS를 실행한 횟수를 반환하면 된다.3. 코드 분석import java.io.*;import java.util.*;class Solution { public int solution(int n, int[][] computers) { ..

1. 문제 설명문제 링크(1) 일거리의 시작 시간, 끝 시간, 일을 끝냈을 때의 이익 이 주어진다.(2) 시작 시간과 끝 시간의 범위가 겹치는 일은 같이 하지 못한다. 반면 어떤 일이 끝나자마자 다른 일은 시작할 수 있다.예를 들어, job A의 끝 시간이 3시 이고 job B의 시작시간이 3시이면 두 일 거리는 연달아 할 수 있다. 반면 job C가 3~5시이고 job D가 4~6시이면 두 일은 일의 시간 범위가 겹치므로 같이하지 못한다.(3) 이때, 겹치지 않게 일을 해서, 최대 이익을 얻으려고 한다. 주어진 일거리들 중에서 가질 수 있는 최대 이익은 몇인가?2. 접근 방식KEY WORD: DP(1) 주어진 문제가 시작시간, 끝시간, 이익을 따로 따로 주기에 이를 하나의 일(job) 단위로 하나로 묶..

1. 문제 설명문제 링크2. 접근 방식KEY WORD: DATA STRUCTURE(0) 현재 조회 중인 수를 value, 출력해야 하는 수를 now라고 해보자.(1) value (2) stack의 top과 now를 비교한다.(3) top이 크면 어떤 방법을 써도 수열을 만들 수 없다. NO를 출력하자.(왜냐하면, 수열은 무조건 stack에서 pop되는 값으로 만들어야 하기 때문이다. stack에는 오름차순으로 값이 저장되기에, 현 stack의 top 값이 크다고 새로 push를 받으면 더 큰 값밖에 들어오지 않는다. stack의 top이 now보다 작을 때는 같은 값이 들어올 때까지 기다리면 되는 것과 상반된다.)(4) top == now 이면 stack에서 pop해서 값을 뺀다.Stack은 진짜 sta..

1. 문제 설명문제 링크(1) 오늘이 몇년, 몇월, 며칠인지 알려주고, 개인정보의 유형별로 정보 보관 기간을 알려준다. (2) String 배열 형태로, 정보가 수집된 날짜, 개인정보의 유형이 주어질 때, 주어진 배열에서 오늘 파기될 정보가 무엇인지, 번호를 배열 형태로 반환하라. 2. 접근 방식KEY WORD: 문자열 자르기해당 문제의 입력은 다음과 같이 주어진다. todaytermsprivaciesresult"2022.05.19"["A 6", "B 12", "C 3"]["2021.05.02 A", "2021.07.01 B", "2022.02.19 C", "2022.02.20 C"][1, 3]"2020.01.01"["Z 3", "D 5"]["2019.01.01 D", "2019.11.15 Z", "2..

1. 문제 설명문제 링크 2. 접근 방식KEY WORD: BFS생각 해야할 점: 하나의 정점이 자신의 위치를 안다는 것은 단방향 그래프에서 해당 정짐이 다른 모든 정점들과 서열를 가진다는 것이다. 이 때, 해당 서열은 간접적으로 파악이 되도 된다.간접적으로 파악된다는 것은 무슨 뜻인가?해당 그림은, 문제에서 예시로 주어진, 정점들간의 관계이다. 문제에서는 2번이 1,4,3번에게 패하고, 5번에게 이겼음으로 4등이라고 했다. 5번은 그 2번에게 졌음으로, 1,3,4번에게도 간접적으로 진 것이다. 따라서 2, 5번은 모든 정점에 대해서 서열을 가진다.(1) 단 방향 그래프를 두 개 만들기첫 번째 방법은 단 방향 그래프 2개 만들기 이다.우리의 핵심은, 현재 조회 중인 정점이 간접적으로라도, 모든 정점과 서열..

1. 문제 설명2. 접근 방식KEY WORD: BFS, IDEA해당 문제는 문제를 풀기 위한 IDEA만 생각해낸다면 간단한 BFS 문제이다. 문제에 대한 접근 방식은 다음과 같다.(1) 입력받은 좌표의 변두리 부분도 페인트를 칠할 수 있다. 가령파란색으로 칠한 부분을 봐라. 만약 입력 좌표 그대로 2차원 배열을 만든다면, 해당 변두리 부분은 배열을 벗어나게 되어, 페인트를 칠할 때 골치가 아파진다. (자칫 잘못하면 OutOfArrayIndex 에러가 나기 때문이다!!)따라서 우리는 해당 좌표도 배열 내에서 받을 수 있도록 2차원 배열을 테두리까지 넉넉하게 만들고, 여기에 입력받은 좌표값들을 집어넣는다.int [][] map = new int [row+2][col+2]그러면 이렇게 받을 수 있다. 파란색으..