2번째 부트 캠프 합격 소식설을 쇠기 전, 합격 소식을 담은 메일이 왔다. 구름이란 회사에서 하는 2달짜리 단기 KDT 캠프였다. 해당 부트캠프를 선택했던 이유는 다음과 같다.1️⃣ KDT 수료자를 대상으로 하는 부트 캠프이다. 따라서 입문 과정을 반복하는 낭비 없이 원하는 것을 할 수 있으리라 생각했다.2️⃣ 한달은 개발, 한달은 TDD 기반 단위 테스트로 성능을 향상시키는 것에 집중한다. 이것이 주효하게 선택한 원인이었다. SSAFY에서 개발을 처음 배운 나는, SSAFY가 나의 기초와 프로젝트 구현 실력을 키워준 것에 정말 감사하고 있다. 하지만 하나 갈증을 느꼈던 부분은 완성한 프로젝트를 뜯어보며 성능을 측정하고 향상시키는 과정을 하지 못한 것 이었다. 이를 할 수 있어서 좋았다.3️⃣ 두 달 동..

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}$: 여러 값의 합..

0. 들어가며...해당 글은 ArrayList에서 원하는 숫자를 지우는 방법에 대한 글이다. ArrayList.remove() 함수로 지우면 되지 않겠냐 생각할 수 있지만 .remove(int i)를 넣으면, remove의 오버로딩된 함수 중 ArrayList.remove(int index)가 호출되어, i를 index로 가지는 Value를 ArrayList에서 삭제한다. 따라서 원래 의도한 'i라는 Value 지우기'는 실패한다.1. ArrayList.remove(int index)위에서 설명했듯이 remove에 원시 자료형 int를 넣으면 해당 인수를 index로 가지는 Value를 ArrayList에서 삭제한다.2. ArrayList.remove(Object o)우리가 실제 i라는 Value를 삭..

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. 푸는 방향삼국지에서 조조는 숲에서 게릴라 항전을 하는 황건적 잔당을 잡기 위해 숲에 직접 들어가기 보다 숲에 불을 질러서 살려고 나오는 잔당을 죽였다. 그처럼 모든 제곱 수로 나눠지지 않는 수(제곱 ㄴㄴ 수)를 일일히 구하는 것보다, 제곱 수로 나눠지는 수를 제거해서 결국엔 제곱 ㄴㄴ 수만 배열에 남기는 것이 간편할 것이다. 그렇다면 이제 구해야할 것은 제곱수와 그..

0. 들어가며개발을 하거나, 코딩테스트에서 정수론 관련 문제를 만나면 한 번씩 주어지는 입력의 크기가 Long형을 초월할 수 있을 때가 간혹 있다. 먼저 코테에서 자주 쓰이는 자료형인 int와 Long형의 최대, 최소값을 알아보자.정수형 타입데이터 표현 범위int-2,147,483,648 ~ 2,147,483,647 ($10^{10}$)long-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 ($10^{18}$)long이 정말 많은 수의 범위를 커버할 수 있음에도 불구하고 백준의 거의 소수같은 문제는 이러한 자료형을 뛰어넘는다. 이때의 대처법 2가지를 설명하겠다.1. 실수 자료형인 Double 사용 Double은 64bit 부동 소수점으로 표현된 자료형으로..

0. 정리하는 이유코테 문제를 풀다가 갑자기 순서가 헷갈렸다. 그래서 정리해놔야 겠다1. For 문 작동 순서1️⃣: 지역 변수 선언 및 초기화 (해당 부분이 For문 밖에 있어도 된다. 다만 그렇게 하면, for 문이 끝난 뒤에도 i 값이 유지된다.)2️⃣: 중앙의 조건 체크 (여기서 걸리면 for문 내용물에 들어가지 않고 바로 for 문이 끝난다.)3️⃣: 내용물 처리4️⃣: i 크기 올리기5️⃣: 다시 한 번 더 조건 체크

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

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로 가는 부분적인 최단 경로에서 벗어나는 정점을 방문하는 것 자체가 비용을 늘릴 뿐 도움되지 않는다. 따라서 각각 부분적인 최단 경로의 합이 곧 전체 최단 경로가 될..