poArlim poArlim

List 를 사용하여 데이터를 조회하다 보면, 조회된 데이터가 없을 경우 NullPointerException 등이 터질 수 있기 때문에 null 체크를 해주어야 합니다. 1. List 가 null 일 경우 인스턴스 자체가 생성되지 않았을 경우 List 는 null 값을 가진다. null 인 리스트를 조회하려고 하면, NullPointerException 이 터진다. null 체크는 "list == null" 로 할 수 있다. if(list != null){ // task } 위 코드를 추가하면, list 가 null 이 아닌 경우에만 작업을 수행한다. 다만, 여전히 문제가 있다. 데이터를 받아오는 과정에서 list 에 null 이 아닌 빈 값이 저장되는 경우 위의 null 체크에 걸리지 않는다. (li..

1. 탐욕적 기법(Greedy Algorithm)이란? 탐욕적 기법, 혹은 욕심쟁이 기법이라고 불리는 이 알고리즘은 말 그대로 욕심쟁이처럼 항상 눈앞의 가장 큰 이익만을 좇는 방법이다. 대부분의 알고리즘은 큰 문제를 작은 문제로 쪼개어 해결하는 과정을 거치는데, 탐욕적 기법은 작은 문제들을 해결하는 과정에서 전체 결과를 생각하지 않고 당장 작은 문제의 최적해를 찾고 이를 모두 더하여 최종 결과를 도출하게 된다. 이러한 기법은 생각보다 잘 통하는 경우가 많지 않다. 아래 그림을 보자. 서울에서 부산까지 최단거리로 가는 방법은 서울->대전->부산의 경로로 4.5km 이지만, 이 상황에 탐욕적 기법을 적용하면 알고리즘은 각 단계에서 최적해, 즉 가장 가까이 있는 도시로 이동하여 서울->인천->대전->부산의 경..

https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 접근 우선 문제의 접근법부터 생각해야 한다. 이 문제를 이분탐색으로 풀게 된 이유는 문제의 범위를 보면 간단히 알 수 있다. 입국 심사를 기다리는 사람이 최대 1,000,000,000 명, 한 명을 심사하는 데 걸리는 시간이 최대 1,000,000,000 분이므로 O(n) 의 시간복잡도 마저 부담스러운 값이 나온다. 이러한 매우 큰 범위가 주어지면, O(logn)..

이분 탐색이란 주어진 데이터 중에서 원하는 데이터를 찾는 탐색 기법 중 하나로, 전체 범위를 두 부분으로 나누는 과정을 반복하여 목표값을 찾아내는 기법이다. 간단하게 예를 들면, 레크레이션 등에서 많이 하는 업다운(Up, Down) 게임을 생각하면 된다. 1~100 숫자 중 사회자가 생각한 숫자를 맞출 때 중간값인 50을 처음 부르고 이후 사회자의 Up, Down 대답에 따라 75, 25 등 나머지 범위의 중간값을 계속 부르는 방식으로 진행된다. 진행 순서 초기 설정 (left = 최소 index 값, right = 최대 index 값) mid 값 설정 (left : 최소 index 값, right : 최대 index 값, mid = (left+right)/2 ) 이분 탐색을 적용하기 위해서는 데이터가 ..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 대표적인 DP 문제이다. 우선 문제를 보는 순간 점화식으로 표현될 것 같다는 생각이 든다. 2*n 크기의 직사각형을 1*2, 2*1 두 종류의 타일로 채울 때, 모든 경우는 2가지로 나눌 수 있다. 가장 왼쪽 타일이 2*1 타일로 시작하는 경우 가장 왼쪽 타일이 1*2 타일로 시작하는 경우 -> 1*2 타일은 위아래로 붙어서 2*2 형태로만 존재할 수 있다. 타일의 종류는 2종류만 존재하므로 가장 왼쪽 타일은 2*1타..

std::getline() 함수는 입력스트림에서 한 줄을 읽어 저장한다. 아래는 여러 줄의 문자열을 그대로 출력하는 코드이다. #include using namespace std; int main (){ string s; while (getline(cin, s)){ cout

C 에서는 eof 입력을 보통 다음과 같이 처리했었다. while (scanf("%d %d", &a, &b) != EOF){ /* code here */ } C++ 에서는 cin 객체와 >> operator 로 입력을 받을 때는 eof 의 입력을 다른 방식으로 처리해 주어야 한다. while (std::cin >> a >> b) { /* code here */ } 위와 같이 입력 받으면 eof 를 입력받을 시 반복문이 종료된다. cin 은 실제 입력을 수행하는 클래스인 istream 클래스 객체이고, >> operator 는 istream 클래스에 정의되어 있는 연산자이다. >> operator 는 istream 객체의 값을 추출하여 변수로 넘겨주는 역할을 하고 호출한 자신을 반환한다. 1 2 를 입력하..

자 이제 스레드의 마지막 미션인 Advanced Scheduler 를 구현해보도록 하자. Advanced Scheduler 는 Pintos 도큐먼트 Appendix B 에 기록되어 있는 4.4BSD Scheduler 와 같은 맥락의 스케줄러를 구현하도록 요구한다. 4.4BSD Scheduler 는 Multi-Level Feedback Queue Scheduler 의 구성이며, 이를 줄여서 pintos 의 코드에서는 mlfqs 로 나타나 있다. 4.4BSD 스케줄러의 상세한 내용은 전에 다룬 포스트가 있으니 자세한 이해를 원한다면 아래 링크에서 읽어보길 바란다. (recent_cpu, load_avg 값의 계산식을 분석하는 부분이 매우 흥미롭다.) [Pintos] 4.4BSD 스케줄러(4.4BSD Sche..