메모리: 메모리: 52 MB, 시간: 1.57 ms - Answer Code1
코딩테스트 연습 > 연습문제
import java.util.Arrays;
class Solution
{
public int solution(int []A, int []B)
{
int answer = 0;
// 기본 정렬 조건 : 오름차순
Arrays.sort(A);
Arrays.sort(B);
for(int i = 0; i < A.length; i++) {
answer += A[i] * B[B.length - 1 - i];
}
return answer;
}
}
양쪽에서 각각 한개의 숫자를 뽑아 곱한 값을 누적하였을 때 한 쪽의 최댓값과 다른 쪽의 최솟값을 곱하는 경우 누적값을 최소로 구할 수 있다
정렬을 하기 위해서는 import java.util.Arrays;
선언해야 한다.
Arrays.sort()
: 기본 정렬 조건이 오름차순 이다.
따라서 A와 B 배열을 정렬하여 한 쪽의 최댓값과 다른 쪽의 최솟값을 곱해 누적하면 최소값을 구할 수 있다
최솟값을 구하는 조건을 바로 떠올리지 않아서 시간이 좀 걸렸지만, 조건만 알 수 있으면 바로 풀 수 있는 문제였다.
최솟값을 구하는 조건에 대해서 잘 기억해두자.
메모리: 52.8 MB, 시간: 19.78 ms - Answer Code1
메모리: 53.1 MB, 시간: 7.90 ms - Answer Code2
코딩테스트 연습 > 스택/큐
import java.util.*;
class Solution {
boolean solution(String s) {
// [1] 정답을 저장할 변수로 answer와 stack을 선언
boolean answer = true;
Stack <Character> stack = new Stack<>();
// 반복문을 이용하여 문자열을 앞에서부터 비교
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// [2] 문자를 비교할 때 `(` 일 경우 스택에 push
if(c == '(') {
stack.push(c);
}
// [3] `)`일 경우
if( c == ')') {
// stack의 크기가 0이면 false 반환
if(stack.size() == 0) {
answer = false;
}
// stack의 크기가 0이 아니라면 `(`가 있다는 의미이므로 스택에 pop
else {
stack.pop();
}
}
}
// [4] 문자열을 끝까지 확인한 이후에 스택의 크기가 0이면 true 반환
if(stack.size() != 0) {
answer = false;
}
return answer;
}
}
스택을 이용하여 괄호가 짝을 이룬다면 스택을 제거한다.
문자열을 끝까지 검사했을 때 스택의 크기가 0이면 올바른 괄호이므로 true를 반환하고, 그렇지 않으면 false를 반환한다.
[1] 정답을 저장할 변수로 answer와 stack을 선언하고, 반복문을 이용하여 문자열을 앞에서부터 비교한다.
[2] 문자를 비교할 때 (
일 경우 스택에 push 한다.
[3] )
일 경우 이때, stack의 크기가 0이 아니라면 스택에 pop 한다.
(
가 있다는 의미이고, 스택의 크기가 0이라면 (
가 없으므로 짝을 이룰 수 없다.[4] 문자열을 끝까지 확인한 이후에 스택의 크기가 0이면 true, 아니면 false를 return 한다.
class Solution {
boolean solution(String s) {
boolean answer = false;
int count = 0;
for(int i = 0; i<s.length();i++){
if(s.charAt(i) == '('){
count++;
}
if(s.charAt(i) == ')'){
count--;
}
if(count < 0){
break;
}
}
if(count == 0){
answer = true;
}
return answer;
}
}
(2번째 풀이) 다른 사람의 풀이를 가져와봤는데, 스택을 사용안하면서 count 변수를 사용하여 깔끔하게 풀이했다.
그 결과 1번째 풀이보다 시간적인 측면에서 3배 가까이 시간을 절약하는 것을 볼 수 있었다.
스택을 사용한다고 해서 좋은 정답은 아니라는 것을 알 수 있었다.
메모리: 86.2 MB, 시간: 4.88 ms - Answer Code1
코딩테스트 연습 > 연습문제
import java.util.*;
class Solution {
public String solution(String str) {
String answer = "";
// 1. 공백을 기준으로 문자열을 잘라서 String 배열에 저장
String [] strArr = str.split(" ");
// 2. 잘린 String 배열을 순서대로 처리
for(int i = 0; i < strArr.length; i++) {
String now = strArr[i];
// 문자열의 길이가 0이면 " " 추가
if(strArr[i].length() == 0) {
answer += " ";
}
// 문자열의 길이가 있다면
else {
// 첫번째 문자는 소문자 -> 대문자로 변환
answer += now.substring(0, 1).toUpperCase();
// 나머지 문자는 대문자 -> 소문자로 변환
answer += now.substring(1, now.length()).toLowerCase();
// 단어 사이에 공백을 위해 마지막에 `" "`을 추가
answer += " ";
}
}
// 3. 입력 받은 문자열의 맨 마지막이 " "이라면(기존에 있었던 공백이면), 바로 answer 반환
if(str.substring(str.length()-1, str.length()).equals(" ")) {
return answer;
}
// 4. 입력 받은 문자열의 맨 마지막이 `" "`이 아니라면 해당 부분을 제거하고 반환
return answer.substring(0, answer.length()-1);
}
}
기존 문자열 이름인 str 을 split(" ")
을 사용하여 공백을 기준으로 잘라서 String 배열에 저장한다.
잘린 String 배열을 순서대로 처리한다.
첫 번째 문자와 나머지 문자를 나눈다 -> substring()
첫 번째만 대문자로, 나머지는 소문자로 변환한다.
toUpperCase() : 소문자 -> 대문자
toLowerCase() : 대문자 -> 소문자
단어 사이에 공백을 위해 마지막에 " "
을 추가한다.
입력 받은 문자열의 맨 마지막이 " "
이라면(기존에 있었던 공백이면), 바로 answer을 반환한다.(마지막 공백을 지우지 않는다)
입력 받은 문자열의 맨 마지막이 " "
이 아니라면 해당 부분을 제거하고 반환한다.
첫 번째 부분과 나머지 부분을 구분하는 경우에는 substring()
을 사용하자.
소문자와 대문자간 변환할 때 쓰이는 toUpperCase()
, toLowerCase()
에 대해 다시 공부하게 되었고,
(중요) 문제풀이 - 3번째 조건 부분이 없으면 테스트케이스 부분이 실패로 되버렸다.
메모리: 83.7 MB, 시간: 28.33 ms - Answer Code1
메모리: 87.1 MB, 시간: 9.33 ms - Answer Code2
코딩테스트 연습 > 연습문제
import java.util.*;
class Solution {
public String solution(String s) {
String answer = "";
ArrayList<Integer> arr = new ArrayList<Integer>();
String [] str = s.split(" ");
for(int i = 0; i < str.length; i++) {
arr.add(Integer.parseInt(str[i]));
}
answer = "" + Collections.min(arr) + " " + Collections.max(arr);
return answer;
}
}
import java.util.*;
class Solution {
public String solution(String s) {
int max, min, n;
String [] str = s.split(" ");
max = min = Integer.parseInt(str[0]);
for(int i = 0; i < str.length; i++) {
n = Integer.parseInt(str[i]);
if(max < n) max = n;
if(min > n) min = n;
}
return min + " " + max;
}
}
이 글의 사진과 내용은 공룡책 과 컴퓨터학부 수업인 운영체제 강의자료를 기반으로 작성했습니다.
Paging
은 프로세스의 가상 주소 공간을 고정적인 크기(fixed-sized)로 나누어서 메모리에 할당하는 방식이다. 이때 고정적인 크기 단위를 page
라고 부른다.
그리고 이러한 가상공간의 page 를 실제 메모리에 할당할 때 이를 page frame
이라고 부른다.
즉 가상 메모리(주소 공간)에서는 page, 실제 메모리(주소 공간)에서는 frame 이라고 불리는 고정 크기의 공간으로 프로세스를 실행하겠다는 의미이다.
Flexibility : 주소 공간의 추상화를 효율적으로 지원한다.
Simplicity : 여유 공간(free-space)의 관리가 쉽다.
가상 메모리의 page와 page frame이 같은 크기를 가진다.
할당이 쉽고 여유 공간을 유지한다.
128-byte physical memory with 16 bytes page frames
64-byte address space with 16 bytes pages
page
들이 실제 메모리의 어디에 위치를 하는 지를 기억하는 Page table
을 가지고 있어야 한다.Page table
이란 가상 주소 공간의 page가 실제 메모리(주소 공간)에 어디에 위치해 있는 지를 기록한다.
Per-process structure(프로세스별 구조)
OS 가상 메모리의 영역에 저장된다.
Paging 기법을 이용하여 주소 변환을 구하는 방법에 대해 알아보자.
가상 주소 공간에는 두 가지 요소가 있다.
VPN : Virtual Page Number -> 상위 2개의 bit이 Page를 표현한다.
Offset : page 안에 있는 offset -> 나머지 4개의 bit이 offset을 표현한다.
A Simple 64-byte Address Space
Page table을 통해서 Virtual Page, Physical Page frame 의 i번째를 찾는다.
Offset을 통해 그 Page 안에 몇번째 메모리 주소인지 찾는다.