1. CPU 스케줄링이란?복수의 프로세스 중 어떤 프로세스가 CPU를 가장 먼저 사용하고 얼마나 오래 사용할지를 결정하는 방식을 의미한다.이를 위해서 스케줄링 기법마다 다르게 프로세스들의 우선순위를 측정하고, CPU 사용시간을 산정한다.(1) 좋은 CPU 스케줄링이란?CPU란 단일 자원을 프로세스들에게 최대한 공평하게 배분하여 프로세스 처리율과 CPU 이용률을 높이고, 응답시간, CPU 과부화(오버 헤드), 프로세스들의 처리 대기시간을 줄이는 것이 좋은 스케줄링이다.공평성🆙 ➜ ( 프로세스 처리율⬆️, CPU 이용률⬆️ ) | (응답 시간 ⬇️, CPU 과부하 ⬇️, 프로세스 처리 대리시간 ⬇️)2. 선점형 스케줄링에 대하여현재 CPU를 활용하고 있는 프로세스를 A라고 하자. 이때 준비큐에서 A보다 처..

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을 놓으려는 행에 이..

0. 개요오늘은 1️⃣ PRD(요구사항 정의서)와 2️⃣ API 명세서를 팀 노션에 부착하여 노션을 업그레이드 했다. 그간 팀 프로젝트를 하면서 느꼈던 불편했던 점들을 생각해보고, 그것들을 개선하는 형식으로 PRD와 API 명세서를 구현했다. 내가 불편함을 느꼈던 사항은 다음과 같다.1. 불편 했던 점1️⃣ 요구사항 정의서 DB와 API 명세서 DB가 따로 논다.둘이 연관관계가 없으니, API 명세서가 요구사항 정의서의 요구사항을 잘 이행하고 있는지 확인이 어려웠다. 따라서 요구사항 준수 여부를 확인하기 위해 (1) 두개의 표를 띄우고, (2) 연관 있는 것을 사람이 직접 찾고, (3) API가 요구사항을 벗어났는지 아닌지 확인하는 식으로 진행 했다. 이러니 초반에는 구현 속도가 더뎠고, 후반에는 요구사..

0. 들어가며...이번에 새로 팀 프로젝트를 하면서, 노션을 통해 프로젝트 관리를 하게 되었다. JIRA나 MATTERMOST 같은 협업툴을 지원해주던 SSAFY와 달리, 구름 부트 캠프는 그런 것이 없어, NOTION을 통해 직접 만들어야 했다. 그간 노션 활용력이 많이 높아졌으니, 좋은 기회라 여겼다. 오늘은 1️⃣ 노션의 관계형 데이터 베이스를 활용한 스프린트 관리와 2️⃣ 수식을 활용한 가시성 높이기를 한 번 해보려 한다.1. ERD 설계관계형 DB를 계획해서 사용하려면 역시 설계부터 해야한다. 그래서 ERD CLOUD를 키고, DB 설계를 시작했다. 설계 전에는 설계의 목표를 세우고 시작해야한다. 내가 세운 목표는 다음과 같다.1️⃣ 팀 멤버 별로 자신이 해야할 일이 귀속되어있다.2️⃣ 진행 여..

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️⃣ ..