참조의 지역성이란? CPU가 프로그램을 실행하는 동안 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복 참조(액세스)하는 경향이 있는데 이것이 참조의 지역성이라고 한다. 참조의 지역성 특성 참조의 지역성은 프로그램이 가지는 기본적인 실행 특성이다. 프로세스의 실행동안 메모리가 균일하게 참조되지 않고 특정 부분이 집중 참조된다. 참조의 지역성은 지역성(locality), 지역성의 원리(principle of locality)라고도 부른다. 프로세스는 최근에 참조한 데이터와 코드를 다시 참조하는 경향이 있다. 프로세스가 실행되는 동안 메모리 영역을 옮겨 다니면서 참조의 지역성이 나타난다. 경험적 관찰에서 발견한 90/10 규칙은 "프로그램 코드의 10%가 프로그램 전체 실행 시간의 90%를 소비한다"는 ..
가상 메모리(Virtual Memory System) 란? 메모리가 실제 메모리보다 많아 보이게 하는 기술로, 어떤 프로세스가 실행될 때 메모리에 해당 프로세스 전체가 올라가지 않더라도 실행이 가능하다는 점에 착안하여 고안된 메모리 기법이다. 왜 가상 메모리를 사용하는가? 물리 메모리는 컴퓨터에 장착된 실제 메모리로서 최대 크기는 CPU에 의해 제한된다. 그렇다면 운영체제는 물리메모리보다 큰 프로세스를 실행시킬 수 없는 것인가? 또한 운영체제는 여러 프로세스를 합쳐 물리 메모리보다 클 때 이들을 동시에 실행 시킬 수 없는 것인가? 이에 대한 해답으로 가상메모리 기법이 등장하게되었다. 결국에 가상 메모리는 물리 메모리보다 큰 프로세스나 여러 개의 작은 프로세스를 동시에 실행시켜, 사용자나 응용프로그램에게 ..
1 초 256 MB 38794 23051 16934 59.164% 문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다. https://www.acmicpc...
2 초 128 MB 28997 16202 12714 55.805% 문제 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백..
6 초 256 MB 60302 14809 9491 20.877% 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 ..
1 초 128 MB 45640 26178 20111 56.427% 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1..
이전에 클린아키텍처가 무엇인지에 대해서 글을 썻다. 오늘은 클린아키텍처를 안드로이드에서 실습해보자. 사이드 프로젝트 형식으로 해보았다. 1. 맨 처음에 Android Project 형식을 App -> Project로 바꾼 이후에 Project를 우 클릭하면 다음과 같은 화면이 나온다. 2. 이후 Module을 클릭하면 이와같은 Create New Module이 나온다. 그러면 2번째에 있는 Android Library를 클릭하여 사용자가 생성하고 싶은 이름으로 새로운 모듈을 생성하자. (ex. Data. Domain. Presentaion) 3. 위와 같은 방법으로 실행하였다면 아래와 같이 셋팅이 되어있을 것이다. 그렇다면 Gradle 파일로 가서 의존성을 넣어주자. Data 모듈의 Gradle 파일에는..
Intent 란? 인텐트는 컴포넌트(액티비티, 서비스, 브로드캐스트 리시버)간에 통신을 하기 위한 메시지 객체 이다. 즉, 쉽게 말하자면 Component를 실행시키기 위해 시스템에 넘기는 정보이다. Intent를 사용하는 방법은 여러가지가 있지만 일반적으로 3가지이다. 액티비티의 시작: startActivity(Intent), startActivityForResult(Intent, requestCode) 서비스의 시작: startService(Intent), bindService(Intent) 브로드케스트 전달: sendBroadcast(Intent), sendOrderedBroadcast(Intent), sendStickyBroadcast() 또한 인텐트의 유형으로는 명시적 인텐트(Explicit I..
오늘은 안드로이드의 Context에 대해서 공부해보자. Context란? 애플리케이션(객체)의 현재 상태의 맥락(context)를 의미한다. Context 는 크게 두 가지 역할을 수행하는 Abstract 클래스 입니다. 어플리케이션에 관하여 시스템이 관리하고 있는 정보에 접근하기 안드로이드 시스템 서비스에서 제공하는 API를 호출 할 수 있는 기능 컨텍스트는 새로 생성된 객체가 지금 어떤일이 일어나고 있는지 알 수 있도록 한다. 따라서 액티비티와 애플리케이션에 대한 정보를 얻기 위해서는 컨텐스트를 사용한다. 또한 컨텍스트는 시스템의 핸들러와도 같다. 리소스, 데이터베이스, preferences 등에 대한 접근을 제공한다. 안드로이드 앱에서는 Activity가 존재하는데, 액티비티는 애플리케이션이 현재 ..
2 초 128 MB 32096 13748 9567 41.616% 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다. 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하..
1 초 (추가 시간 없음) (하단 참고) 128 MB 57145 26728 21044 48.845% 문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음..
2 초 128 MB 17766 8661 6917 48.708% 문제 후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오. 입력 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. 3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 100보다 작거나 같은 자연수이다. 후위 표기식을 앞에서부터 계산했을 때, 식의 결과와 중..
