1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/1738(2) 해설🕵경로에 깡패가 있어서 가중치가 마이너스인 경우가 있다. 따라서 최적 경로는 벨만 포드로 구해야 하는데, 여기에 제약 조건이 있다.1️⃣ 이번 문제는 최소 가중치 합이 최적 경로인 일반적인 벨만 포드 문제와는 달리 최대 가중치 합이 최적 경로 이다.2️⃣ 따라서 최적 경로를 구할 수 없는 경우는 N 번째 완화과정을 거쳐도 가중치의 합이 커지는 경로가 있는 경우이다.3️⃣하지만 양의 사이클이 1에서 N까지의 경로에 영향을 주지 않는다면, 최적 경로는 그대로 존재하는 것임으로 상관 없다.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: Bellman-ford, BF..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/9663(2) 해설🕵체스에서 Queen은 8방향을 갈 수 있는 말이다. (사방 탐색 + 사방의 대각)체스는 자신이 한 번의 움직임으로 갈 수 있는 경로에 있는 말을 죽일 수 있다.이 Queen을 모든 행에 하나씩 둘 때, 서로가 서로를 죽일 수 없게 두는 경우의 수를 구하는 것이다. 2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: BACK TRACKINGN의 최대값이 15라서, 1515 체스판에서 백트래킹을 해도 시간 초과가 나지 않는다. 따라서 *백 트래킹**을 활용한다. 경로가 겹치는지 확인하기 위해서는 다음 4가지를 확인해야 한다.1️⃣ 현재 Queen을 놓으려는 행에 이..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/1850(2) 해설🕵입력으로 주어지는 A와 B는 1로 이루어진 숫자의 길이인데, 그 길이가 $2^{63}$으로 너무 길다. 분명 이 A와 B까지는 Long 자료형으로 표현할 수 있겠으나, 그것이 실제 가리키는 1로 이루어진 숫자는 표현하기가 어렵다. (숫자의 길이가 2^{63}이라 BigInteger로도 힘들 듯 하다.) 여기서 주목해야할 점은1️⃣ 1로만 이루어져 있다.2️⃣ 문제 제목이 최대공약수 이다.정도 일 것이다.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: 문자열 GCD임의의 문자열 A,B가 특정 문자열 패턴 P의 반복으로 이루어져 있을 경우, 둘의 최대 공약수 문..

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: 에라토스테네스의 체, 오일러 피 함수에라토스테네스의 체를 따로 구할 메모..

1. 오일러 피 함수란?$$φ(n) = n이하\;자연수\;중\;n과\;서로소인\;수의\;개수$$$φ(12) \; = \; 4$이다.2. 사전 학습오일러 피 함수의 증명을 위해서 다음 챕터에서 오일러의 곱 공식을 살펴볼 것인데, 사전에 학습해야할 내용이 있어서 미리 소개하겠다.1️⃣ 소인수: 임의의 수 K의 소수이면서 인수인 수이다. 예를 들면 12의 소인수는 2와 3 이 있다.2️⃣ 소인수 분해: 임의의 수 K를 소수로만 인수 분해하는 것이다. 예를 들어 12를 소인수 분해하면, $12\,=\,2^{2}\,*\,3$이다.3️⃣ 서로소: A와 B가 서로소라는 뜻은, A와 B의 공약수가 1말고는 없다는 뜻이다.4️⃣ $φ()$: 오일러 파이라고 읽는다.5️⃣ $\prod_{p \mid N}$: 여러 값의 합..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/2615(2) 해설🕵주의해야할 점1️⃣ 바둑알이 가로 세로 혹은 대각선으로 동시에 6개 이상 9개 이하로 놔두는 곳도 있다.(이 경우, 문제의 승리 조건인 '5개가 연속되어서 놓아졌다.' 를 위배하기에 답이 아니다.)2️⃣ 재귀가 바둑판을 벗어나는 순간을 감지해서 오류를 방지해야 한다.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: 재귀, SIMULATION해당 문제는 진짜 오목을 두듯이, 흰색 혹은 검은색 바둑알이 나온 시점부터, 가로, 세로, 대각선으로 5개가 연속되는지 확인해주면 되는 문제이다. ⓐ 구해야할 방면 정하기그럼 8방면을 다 구해야 할까? 아니다. 그 절반만 구..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/1016(2) 해설🕵제곱 ㄴㄴ 수 : 1보다 큰 제곱 수로 나누어 떨어지지 않는 수. 따라서 4이상 모든 제곱 수로 나누어 떨어지지 않아야 함 2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: 에라토스테네스의 체a. 푸는 방향삼국지에서 조조는 숲에서 게릴라 항전을 하는 황건적 잔당을 잡기 위해 숲에 직접 들어가기 보다 숲에 불을 질러서 살려고 나오는 잔당을 죽였다. 그처럼 모든 제곱 수로 나눠지지 않는 수(제곱 ㄴㄴ 수)를 일일히 구하는 것보다, 제곱 수로 나눠지는 수를 제거해서 결국엔 제곱 ㄴㄴ 수만 배열에 남기는 것이 간편할 것이다. 그렇다면 이제 구해야할 것은 제곱수와 그..

1. 문제 설명 📌(1) 링크🔗https://www.acmicpc.net/problem/13317(2) 해설🕵지구이의 코드는 벨만포드를 잘못 구현한 코드로서, 정점이 N 개일 떄, N-2번만 완화과정을 거치고, N-1번에서는 음수 사이클 확인을 한다고 한다. 원래라면 N-1번까지 완화 과정을 거치고, N번째에 음수 사이클을 확인한다.해당 문제의 요구사항은 지구이의 코드가 "틀렸습니다."가 나올 반례 입력을 만드는 것이다.지구이의 CPP 코드에 대한 분석✨해당 코드에는 지구이가 만든 틀린 코드와 제대로 돌아가는 벨만포드 코드 2가지로 나뉘고 있다. 여기서 주의해야할 점은 다음과 같다.1️⃣ 시작점에서 정점까지의 최단거리를 나타내는 dis[] 배열이 0으로 초기화 되고 있다.2️⃣ 입력을 받은 순서대로..

1. 문제 설명 📌(1) 링크🔗문제 링크(2) 해설🕵문제 설명이 꼬임 없이 직관적이라 따로 설명할 것이 없다.2. 생각의 흐름: 코드가 나오기까지 🗃️(0) 완전 탐색은 제대로 된 풀이가 아니다.만약 문자열 중 2개를 골라, 앞에서부터 단어가 몇 개나 같은지를 전부 확인 으로 문제를 풀었다면, SOLVED는 되겠지만 답이 아니다. 왜냐하면, 단어의 개수는 최대 20,000 이고, 단어의 길이는 최대 100 이다. 따라서 조합으로 2개 골라서 대조로 풀었다면, 시간 복잡도는 O($ n\choose 2 $* 100) 즉 200억이 나온다.이러한 완탐도 정답이 되는 이유는 아직 대량의 데이터를 입력으로 넣는 TC가 없는 모양이다.https://www.acmicpc.net/board/view/94785여..

1. 문제 설명📌(1) 링크🔗  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr (2) 주목 포인트 🕵1️⃣ 늑대 >= 양 이면 모았던 양의 개수가 0이 된다!2️⃣ 현재 특정한 서브 트리를 방문 중이라 가정할 때, 해당 트리에서 최대 이익을 이미 냈다고 확신한다면, 조상 노드를 거슬러 올라가 다른 서브 트리를 파고 드는 것이 가능하다.2. 생각의 흐름: 코드가 나오기까지 🗃️(1) IDEA 도출💡KEY WORD: BACK-TRACKING, DFS해설에서 설명한 2️⃣번째 포인트 때문에, 이번 문제는 BACK-TRACKING에 가깝게 변형된 DFS를 사용해야 한다. 깊이 우선 탐색을 하는 성질은..

1. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: 재귀, DFS해당 문제에서 실행해야 하는 작업에는 3가지로 왼쪽 자식 방문, 현 노드에 대한 처리, 오른쪽 자식 방문가 있다. 해당 문제는 '이 순서를 어떻게 할 것인가?'에 대한 기준을 세우면 쉽게 풀린다. 왜냐하면, 전위, 중위, 후위 순회는 미리 정해진 순서를 재귀적으로 반복하기 때문이다. 각 순회 별 3가지 작업에 대한 순서는 다음과 같다.1️⃣ 전위 순회: 현 노드에 대한 처리➜ 왼쪽 자식 방문 ➜ 오른쪽 자식 방문2️⃣ 중위 순회: 왼쪽 자식 방문 ➜ 현 노드에 대한 처리 ➜ 오른쪽 자식 방문3️⃣ 후위 순회: 왼쪽 자식 방문 ➜ 오른쪽 자식 방문 ➜ 현 노드에 대한 처리예를 들어 보면, 후위 순회를 진행한다고 해보자. 먼저 ..

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. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: SIMUlATION, BRUTE FORCE0️⃣ 윷놀이판 구현, 말의 위치 나타낼 배열 구현1️⃣ 10번의 주사위 각각으로 움직일 말을 중복순열로 구한다. ($4^{10}$)2️⃣ 이제 주사위 하나당 움직일 말이 무엇인지 순서도 정했음으로, 그대로 말을 움직여 본다.2️⃣-1) 현재 움직일 말의 시작 노드에 파란색 화살표가 있을 경우, 그것이 가리키는 곳으로 이동2️⃣-2) 윷놀이 판의 최종 위치가 아닌데도, 말이 도착한 위치에 다른 말이 이미 존재한다면 이번 순서는 의미가 없으므로, 1️⃣로 회귀2️⃣-3) 1️⃣번에서 구한 모든 말의 순서에 대하여 2️⃣을 진행한다.3️⃣ 지금까지 진행한 순서 중 누적 점수 값의 최대값을 구한다.(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. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: 에라토스테네스의 체에라토스테네스의 체를 구현해보라고 준 연습용 문제이다. 자세한 설명은 이론을 정리한 링크를 남기겠다.  하나 또는 다수의 소수 판별법, 그림으로 쉽게 이해하기1. 하나의 숫자에 대한 소수 판별(1) 방법만약 소수인지 판별해야할 숫자를 N이라고 한다면, 다음과 같은 방법으로 N이 소수인지 여부를 판별할 수 있다.int N = Integer.parseInt(br.readLine());for(int i = 2; idalcheonroadhead.tistory.com (1) 시간복잡도 분석 🕓범위의 끝을 N이라고 할 때,$O(N \log(\log N))$3. 코드 소개 🔎import java.io.BufferedReader;..

1. 문제 설명 📌문제 링크정점 1 ➜ 정점 N으로 갈 건데, 이 둘 사이에 특정한 정점 A, B를 꼭 거쳐야 한다. 이 특정한 정점 2개를 꼭 거치면서 갈 수 있는 최단 경로의 비용을 구하여라2. 구현 방법 🗃️KEY WORD: DIJKSTRA특정 정점 A,B를 꼭 거치면서, 1 ➜ N 까지 가는 최단 경로는 다음 2가지 중 하나 일 것이다.1 ➜ A, A ➜ B, B ➜ N 각각의 최단 경로를 구해서 합한다.1 ➜ B, B ➜ A, A ➜ N 각각의 최단 경로를 구해서 합한다.이게 가능한 이유는 모든 가중치가 양수이기 때문이다. A,B로 가는 부분적인 최단 경로에서 벗어나는 정점을 방문하는 것 자체가 비용을 늘릴 뿐 도움되지 않는다. 따라서 각각 부분적인 최단 경로의 합이 곧 전체 최단 경로가 될..

1. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: BINARY_SEARCH, PARAMETRIC_SEARCHN: 놀이기구 타는 아이 수, M: 놀이기구 수, rids[] = 놀이기구 별 걸리는 시간,minimum_time: 애들 전부 놀이기구에 태우는 최소 시간,remained_kid: (minimum_time -1 ) 시간에 아직 놀이기구 못 타고 남아있는 아이들의 수0️⃣ 사람 수 놀이기구 수 이면, 마지막 사람의 번호가 곧 놀이기구의 수 이므로 N 출력 후 프로그램 종료1️⃣ 아이들을 다 태울 수 있는 최소 시간 찾기 (minimum_time)2️⃣minimum_time 1분 전 시점까지 아직 놀이기구 못 탄 아이들이 몇 명인지 찾기 (remained_kid)3️⃣ rids[]를 ..

1. Parametric Search 란?최적화 문제를 여러 개의 결정 문제 + 이분 탐색으로 변환시키는 문제 접근 방법이다. 여기서 3가지 키워드가 나왔는데, 이분탐색이 뭔지는 많은 사람들이 알테니, 최적화 문제와 결정 문제에 대해 먼저 설명하고 가겠다.(1) 최적화 문제문제의 조건을 만족하는 해의 범주가 존재하고, 그 중에서 최적의 답(최소값, 최대값 등)을 구하는 문제를 말한다.Thread Knots라는 문제를 예시로 들어보면, 해당 문제는 'n개의 매듭을 성공적으로 놓았을 때, 가장 가까운 두 개의 매듭 사이의 최대 거리를 출력하라'고 요구한다.그렇다면, 여기서 가능한 해의 범주는 n 개의 매듭을 각 Thread에 성공적으로 놓는 모든 경우이고,최적의 해는 가장 가까운 두 매듭 사이의 최대 거리일..

1. 벨만포드 알고리즘이란?음수인 가중치가 존재하는 그래프에서도 최단 경로를 구할 수 있게 해주는 알고리즘.1️⃣ ONE TO ALL 알고리즘: 시작점을 고르면, 해당 정점에서 모든 정점까지의 최단 경로를 구할 수 있다.2️⃣ 음수 가중치가 있어도 괜찮아: 다익스트라는 안되지?3️⃣ 음수 사이클이 존재하는지도 확인 가능: 음수 사이클이 존재한다면, 사실 하나 이상의 정점으로의 최단 경로가 $- \infty $가 되기 때문에, 최단경로를 구하는 게 무의미해짐. 따라서 최단 경로를 구하는 게 무의미한지 여부도 파악 가능!음수 사이클가중치 그래프에서 정점 A에서 시작해서 A로 돌아왔는데 가중치의 합이 음수인 경우, 해당 사이클을 음수 사이클이라고 한다.해당 예시에서는 사이클을 돌수록 출발지에서 A,B,C까지의..