전체 글

[백준 2004] 조합 0의 개수 (Java) 출처 : 링크 그냥 조합으로 풀면 시간 안에 해결이 불가능하다. 끝자리 0의 개수만 구하면 되므로 다 계산할 필요가 없다. 일단 조합의 식은 아래와 같다. nCm = n! / (n-m)! * m! 결국 이 값에서 2의 배수와 5의 배수의 갯수를 찾으면 된다. 2의 배수 1개와 5의 배수 1개가 만나면 10이 되어 끝자리 0 하나가 생기기 때문 주의) 25부터는 5가 두개, 4부터는 2가 2개이므로 반복문을 잘 돌려야 함 5와 2 모두 n!에서 개수를 구해주고, 나눠지는 (n-m)!이랑 m!에서 나오는 개수를 빼주면 된다. 그리고 5와 2 중에 개수 최소값을 출력하면 끝이다 123456789101112131415161718192021222324252627282..

[백준 2503] 숫자 야구 (Java) 출처 : 링크 완탐 문제다. 처음에 규칙을 어떻게 가져와야할까 고민했지만, 그냥 다 돌면서 해당하는 규칙과 비교하고 성립하는 수만 고르면 된다. 123~987까지 for문으로 돌아도 되지만, 중복되는 수를 없애기위해 순열을 만들어 풀었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105import java.io.BufferedReader;impo..

[백준 3055] 탈출 (java, bfs) 문제 출처 : 링크 숲의 2차원 배열 : int [R][C]비어있는 곳 : '.'물이 차있는 지역 : '*'돌 : 'X'도착지점 : 'D'고슴도치 위치 : 'S' 물이 차있는 지역은 시간이 지날 때마다 상하좌우로 퍼지게 되고, 동시에 고슴도치는 한 칸을 움직인다.물에 막히기 전에 도착지점까지 도착할 수 있는지 확인하는 문제다. 숲의 2차원 배열을 입력할 때, 고슴도치와 물이 차있는 지역에 대한 행과 열을 큐에 각각 저장하고, bfs를 통해 이동 시간을 구했다. 큐를 2개로 진행하는 bfs는 처음해봐서 조금 어려웠지만, 원리는 크게 다르지 않았다. 둘다 큐에 들어온 size만큼 반복문을 돌려 진행하고, 고슴도치의 큐 사이즈가 0이 되어버리면 이동이 불가능한 것이..

[swexpert 1494] 사랑의 카운슬러 (java) 문제 출처 : 링크 지렁이를 둘러 짝을 지어주는 모든 경우의 수 각 짝이 연결되는 벡터를 구하여 전체 합의 크기를 구해야 한다 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer; /** * 지렁이 개수 짝수개, 둘씩 짝을 지어줌 * 짝을 지어주는 모든 경우의 ..

[백준 2583] 영역 구하기 (java, BFS) 문제 출처 : 링크 단지번호와 유사한 문제같다. BFS를 활용하여 눈금이 칠해지지 않은 부분의 영역 수와, 각 넓이를 구해야 한다. 눈금이 칠해지는 곳을 1로 값을 주고, 0인 부분에 대해서 BFS로 탐색했다. 아직 class를 만들 때부터 배열을 보기 편하게 하기 위해 y축 x축 순으로 작성하는 게 약간 어색한 감이 있어서 더 연습해야겠다.. 방문이 끝날 때 마다 count 변수를 추가하면서 갯수를 세줬고, BFS 안에서 방문이 진행될 때마다 넓이를 1씩 추가시키며 저장했다. 넓이의 순서가 문제의 출력값과 달라서, 한번 배열을 sort해줬는데 정답처리 되었다. 작은 순으로 나열하라고 하지는 않았는데 왜인지는 모르겠다;; 12345678910111213..

[백준 6603] 로또 (java) 문제 출처 : 링크 입력 받은 수 중에서 나올 수 있는 로또의 결과를 모두 출력해야 하는 문제다. 이 문제는 DFS 백트래킹을 이용해서 많이 푼다고 하는데, 12개의 숫자 중에 6개를 고르는 것이므로 조합을 이용해도 충분히 결과를 구할 수 있을 것 같아서 조합을 이용했다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main6603 {..

03_김규석_스케줄러2 [운영체제] CPU 스케줄링 스케줄링이 뭐였죠?!실행 중인 모든 프로세스들에게 골고루 CPU를 할당하는 것! CPU 스케줄링이 필요한 이유는?!CPU를 점유하고 있는 한 프로세스가 입출력 요청에 의해 wait 상태로 되었다고 생각해보자.이 프로세스가 다시 ready 상태로 올 때까지 기다리고만 있는 것은 매우 비효율적임다중 프로그램의 목적은 CPU 효율을 극대화 하는데 있으므로, CPU 스케줄링은 다중 프로그램을 지원하는 운영체제에서 필수적인 요소다!또한, 시스템의 용도에 따라 적절하고 효율적인 스케줄링 알고리즘을 선택하는 것도 매우 중요함 CPU 스케줄링이 일어나는 시점running → waiting (비선점 ex. 입출력 요청)running → ready (선점 ex. 인터럽트..

[백준 1261] 알고스팟 문제 출처 : 링크 경로를 이동하는 걸 생각하면 DFS나 BFS를 활용해야 될 것 같다. 하지만 기존의 문제와는 다르게, '가중치'가 존재한다. 1인 값을 가지고 있는 곳을 지날 때는 벽이 있는 것이므로 부수고 지나갈 수 밖에 없다. 따라서 그냥 움직이는 것이 아닌, 1인 곳을 지나갈 때마다 값을 변경시켜나가야 하는 문제다. 우선 미로탐색처럼 BFS와 유사한 방식으로 나아가지만, 이 가중치 값을 최소화 시키기 위해 그냥 큐가 아닌 우선순위 큐를 사용해서 저장한다. (우선순위를 위해 comperable 활용) 123456789101112131415161718class Spot implements Comparable{ int y; int x; int cost; public Spot..

[운영체제] 스케줄러 [운영체제] 스케줄러 스케줄링이란?시스템이 실행하고자 할 때 프로세서(CPU)를 프로그램들에게 할당하는 과정 프로세스(Process)는 자신의 임무를 모두 수행하고 사라질 때까지 많은 큐를 돌아다님이때 프로그램들은 제한된 프로세서(CPU)를 서로 사용하려고 함OS는 이러한 프로세스 중 하나를 택하는데, 바로 스케줄러가 이러한 역할을 담당 가장 자주 사용되는 스케줄러는 장기 스케줄러와 단기 스케줄러(주로 일괄처리 시스템에서 사용) 실행 준비가 완료된 프로세스들은 준비 큐에 놓임프로세스는, 프로세서(CPU)를 할당 받을 때까지 준비 큐에서 대기함 장기 스케줄러(Long Term Scheduler)작업 스케줄러, 승인 스케줄러라고도 함디스크 내의 작업을 어떤 순서로 메모리에 가져올 지 결..

서로소 집합(Disjoint-sets) [알고리즘] 서로소 집합(Disjoint-sets) 서로소 or 상호배타 집합서로 중복 포함된 원소가 없는 집합(= 즉, 교집합이 없는 것) 대표자(representative)집합에 속한 하나의 특정 멤버를 통해서 각 집합들을 구분 상호배타 집합 표현 방법연결 리스트트리 상호배타 집합 연산Make-Set(x), Find-Set(x), Union(x,y) 트리를 이용해 상호배타 집합 표현된 모습부모는 해당 노드의 Find-Set 값 연산Make_Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산Find_Set(x) : x를 포함하는 집합을 찾는 연산(해당 노드의 부모 정보 갱신)Union(x,y) : x와 y를 포함하는 두 집합을 통합하는 연산 M..