🔗 문제 링크

오픈채팅방

🔎 문제 풀이

이 문제는 보자마자 HashMap이 떠올라서 간단하게 풀었다.

채점할 때 테스트 케이스가 좀 많아서 살짝 두려웠지만 통과 !

Key Point

🔑 유저 아이디와 닉네임을 HashMap에 저장한다. (key: 유저 아이디, value: 닉네임)

🔑 count 변수 : answer 배열의 크기를 선언하기 위해 들어오고 나가는 경우의 수(=count)를 센다.

🔑 오픈 채팅방을 개설한 사람이 보는 메시지(= "ooo님이 들어왔습니다." or "ooo님이 나갔습니다.")를 문자열 배열 answer에 저장한다.

Java 코드

import java.util.*;

class Solution {
    public String[] solution(String[] record) {
        
        // 1. 유저 아이디와 닉네임을 HashMap에 저장한다. (key: 유저 아이디, value: 닉네임)
    
        Map<String, String> map = new HashMap<String, String>();
        int count = 0; 
        
        for (int i=0; i<record.length; i++) {
            String[] info = record[i].split(" ");
            
            if (info[0].equals("Enter") || info[0].equals("Change")) {
                map.put(info[1], info[2]);
            }
            
            // answer 배열의 크기를 선언하기 위해 들어오고 나가는 경우의 수(=count)를 센다.
            
            if (info[0].equals("Enter") || info[0].equals("Leave")) {
                count++;
            }
        }
        
        // 2. 오픈 채팅방을 개설한 사람이 보는 메시지를 문자열 배열 answer에 저장한다.
        
        String[] answer = new String[count];
        int idx = 0;
        
        for (int i=0; i<record.length; i++) {
            String[] info = record[i].split(" ");
            String nickname = map.get(info[1]);
            
            if (info[0].equals("Enter")) {
            	answer[idx++] = nickname + "님이 들어왔습니다.";
            }
            if (info[0].equals("Leave")) { 
            	answer[idx++] = nickname + "님이 나갔습니다.";
            }		 
        }
        
        return answer;
    }
}

문제는 길지만 잘 읽어보면 문자열을 탐색해서 조건에 맞게 처리해주면 된다. switch/case문을 사용했다. 점수 저장 변수(= score)를 int로 선언했더니 에러가 났는데, 찾아보니 두 자릿수인 10을 고려해서 String으로 저장하길래 String으로 바꿨다.

문제는 길지만 잘 읽어보면 문자열을 탐색해서 조건에 맞게 처리해주면 된다.

switch/case문을 사용했다.

점수 저장 변수(= score)를 int로 선언했더니 에러가 났는데,

찾아보니 두 자릿수인 10을 고려해서 String으로 저장하길래 String으로 바꿨다.

아래는 문제 풀이 코드이다.

import java.util.*;

class Solution {
    public int solution(String dartResult) {
        int answer = 0;
        
        // 점수 저장 변수
        
        String score = "";
        
        // 총 3번의 기회에서 얻은 점수 저장 배열
        
        int arr[] = new int[3];
        
        int idx = 0;
        
        // 숫자일 때는 score 변수에 점수를 저장하고, 
        // 그 외 문자열이 입력되는 경우 알맞게 처리해준다.
        
        for (int i=0; i<dartResult.length(); i++) {
            switch(dartResult.charAt(i)) {
                case 'S' :
                    arr[idx] = Integer.parseInt(score);
                    idx++;
                    score = "";
                    break;
                case 'D' :
                    arr[idx] = (int)Math.pow(Integer.parseInt(score),2);
                    idx++;
                    score = "";
                    break;
                case 'T' :
                    arr[idx] = (int)Math.pow(Integer.parseInt(score),3);
                    idx++;
                    score = "";
                    break;
                case '*' :
                    arr[idx-1] *= 2;
                    if (idx > 1) arr[idx-2] *= 2;
                    break;
                case '#' :
                    arr[idx-1] *= (-1);
                    break;
                default :
                    score += String.valueOf(dartResult.charAt(i));
                    break;
            }
            
        }
        
        answer = arr[0] + arr[1] + arr[2];
        
        return answer;
    }
}

자카드 유사도는 Double로 정의한다. 합집합이 0인 경우, 자카드 유사도는 1이 된다. 합집합이 0이 아닌 경우, 자카드 유사도는 교집합 크기 / 합집합 크기이다.

처음에는

주어진 문자열을 charAt()으로 한 문자씩 떼어 영문자인지 확인하고,

영문자라면 Stringbuilder에 append하고,

다 했으면 toUpperCase()를 사용해 대문자로 통일하고 시작할까 ? 

생각했었다.

그런데 굳이 Stringbuilder로 새로운 문자열을 만들 필요가 없다.

기타 공백이나 숫자, 특수문자가 들어있는 경우는 그 글자 쌍을 버린다는 점을 놓쳐서 복잡하게 생각했다.

문제 풀이의 논리는 다음과 같다.

1) 주어진 문자열을 대문자(혹은 소문자)로 통일한다.

2) ArrayList로 다중집합 두 개(집합 A, 집합 B)를 만든다.

각 문자열마다 두 개의 문자를 떼어 둘 다 영문자인지 확인하고, 맞다면 다중집합에 넣는다.

3)  ArrayList로 두 다중집합의 합집합과 교집합을 만든다.

집합 B의 원소 중 집합 A의 원소와 동일한 원소가 있다면 해당 원소를 교집합 ArrayList에 넣는다. 모든 원소는 합집합 ArrayList에 넣는다.

4) 자카드 유사도를 구한다.

자카드 유사도는 Double로 정의한다.

합집합이 0인 경우, 자카드 유사도는 1이 된다. 합집합이 0이 아닌 경우, 자카드 유사도는 교집합 크기 / 합집합 크기이다.

5) answer은 자카드 유사도에 65536을 곱한 정수값이다.

다음은 문제 풀이 코드이다.

import java.util.*;

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        
        // 대문자로 통일한다.
        
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        
        // 다중집합 만들기
        
        ArrayList<String> multiSetA = new ArrayList<>();
        ArrayList<String> multiSetB = new ArrayList<>();
        
        for (int i=0; i<str1.length()-1; i++) {
            char first = str1.charAt(i);
            char second = str1.charAt(i+1);
            
            if (first >= 'A' && first <= 'Z' && second >= 'A' && second <= 'Z') {
                multiSetA.add(first + "" + second);
            }
        }
        
        for (int i=0; i<str2.length()-1; i++) {
            char first = str2.charAt(i);
            char second = str2.charAt(i+1);
            
            if (first >= 'A' && first <= 'Z' && second >= 'A' && second <= 'Z') {
                multiSetB.add(first + "" + second);
            }
        }
        
        Collections.sort(multiSetA);
        Collections.sort(multiSetB);
        
         // 합집합과 교집합 만들기
        
        ArrayList<String> union = new ArrayList<>();
        ArrayList<String> intersection = new ArrayList<>();
        
        for (String s : multiSetA) {
            if (multiSetB.remove(s)) {
                intersection.add(s);
            }
            union.add(s);
        }
        
        for (String s : multiSetB) {
            union.add(s);
        }
        
        // 자카드 유사도 구하기
        
        double jakard = 0;
        
        if (union.size() == 0) {
            jakard = 1;
        }
        else {
            jakard = (double)intersection.size() / (double)union.size();
        }
        
        answer = (int)(jakard * 65536);
        
        return answer;
    }
}

이 문제에서 중요한 포인트는 cache size가 0인 경우를 잊지 말고 생각해야 한다는 점이다. cache size가 0이면 모든 경우는 cachs miss이므로 그냥 cities의 길이에 5를 곱해주면 된다.

캐시 교체 알고리즘 LRU를 처음 만났다. 관련 내용을 정리하면서 개념을 익혔다.

Kakao Tech 블로그에서 문제 해설을 보니 이 문제의 정답률은 45.26%이다.

물론 당연하다 . 나도 보자마자 살짝 당황했다 .

신기한 건 문제 풀고, 운영체제 강의 듣는데 바로 LRU 에 대해 배워서 반가웠다 !

LRU (Least Recently Used)는 가장 오랫동안 참조하지 않은 페이지를 캐시에서 교체하는 것이다.

LRU 캐시 교체 알고리즘 구현은 보통 Queue, ArrayList, LinkedList를 사용하는 것 같다.

Java에서는 LinkedList가 Queue의 구현체라고 한다.

그래서 LinkedList를 사용했다.

아래는 LinkedList 메소드이다.

add(Object object)는 LinkedList의 마지막에 데이터를 추가한다.

remove(int index)는 해당 인덱스 위치의 값이 지워지는 것이지만,

remove(Object object)는 해당 값이 없다면 false, 있다면 지우고 true를 반환한다고 한다.

이 문제는 세 가지 경우를 생각하면 된다.

1) cache size가 0인 경우

이 문제에서 중요한 포인트는 cache size가 0인 경우를 잊지 말고 생각해야 한다는 점이다.

cache size가 0이면 모든 경우는 cachs miss이므로 그냥 cities의 길이에 5를 곱해주면 된다.

2) cache hit 인 경우

3) cache miss 인 경우

아래는 문제 풀이 코드이다.

import java.util.*;

class Solution {
    public int solution(int cacheSize, String[] cities) {
        
        // cache size가 0이면 모든 경우는 cache miss 이다.
        
        if (cacheSize == 0) return cities.length*5;
        
        int answer = 0;
        LinkedList<String> cache = new LinkedList<>();
        
        for (int i=0; i<cities.length; i++) {
            
            // 대문자로 통일한다.
            
            String s = cities[i].toUpperCase();
            
            // cache hit 인 경우 실행시간은 1이다.
            
            if (cache.remove(s)) {
                answer += 1;
                cache.add(s);
            }
            
            // cache miss 인 경우 실행시간은 5이다.
            
            else {
                answer += 5;
                
                if (cache.size() >= cacheSize) {
                    cache.remove(0);
                }
                cache.add(s);
            }
        }
        
        return answer;
    }
}

운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상메모리 기법이라 한다. 페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시(페이지 부재) 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 한다.

목차

페이지 교체 알고리즘 (Page Replacement Algorithm)

• 페이지 교체 알고리즘이란 ?
• 페이지 교체 알고리즘의 종류  
  • OPT 알고리즘
  • FIFO 알고리즘
  • LRU 알고리즘
  • LFU 알고리즘
  • MFU 알고리즘  

LRU Cache

• 캐시 (Cache)
• LRU 알고리즘

페이지 교체 알고리즘 (Page Replacement Algorithm) 

페이지 교체 알고리즘이란 ?

운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상메모리 기법이라 한다. 페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시(페이지 부재) 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 한다.

즉, 필요한 페이지가 메모리에 없을 때 page-fault가 발생하고 Backing Store에서 해당 페이지를 찾아 빈 프레임에 로딩해야 한다. 만약 빈 프레임이 없을 경우 희생 당할 프레임(victim frame)을 고르는 알고리즘이 페이지 교체 알고리즘이다.

페이지 교체 알고리즘은 page-fault 발생 비율을 줄이는 것을 목표로 한다.

프레임: 물리 메모리를 일정한 크기로 나눈 블록
페이지: 가상 메모리를 일정한 크기로 나눈 블록

페이지 교체 알고리즘의 종류

• OPT (Optimal) : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
• FIFO (First In First Out) : 가장 오래된 페이지 교체
• LRU (Least Recently Used) : 가장 오랫동안 사용되지 않은 페이지 교체 = 많은 운영체제가 채택하는 알고리즘
• LFU (Least Frequently Used) : 참조 횟수가 가장 적은 페이지 교체
• MFU (Most Frequently Used) : 참조 횟수가 가장 많은 페이지 교체
• NUR (Not Used Recently) : 최근에 사용하지 않은 페이지 교체

OPT 알고리즘

• 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘이다.
• 모든 페이지 교체 알고리즘 중 page-fault 발생이 가장 적다.
• Belady`s Anomaly 현상이 발생하지 않는다.
• 프로세스가 앞으로 사용할 페이지를 미리 알아야한다.
• 실제로 구현하기 거의 불가능한 알고리즘으로, 연구 목적을 위해 사용된다.

Bealady's Anomaly : 프레임의 개수가 많아져도 page-fault가 줄어들지 않고 늘어나는 현상

FIFO 알고리즘

• 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘이다.
• 구현이 간단하고, 초기화 코드에 대해 적절한 방법이다.
• 성능은 좋지 않은 편이다.
• 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있다.
• Belady`s Anomaly 현상이 발생할 수 있다.

LRU (Least Recently Used) 알고리즘

• 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘이다.
• 최적 알고리즘과 비슷한 효과를 낼 수 있다.
• 최적 알고리즘보다 페이지 교체 횟수가 높지만 FIFO 알고리즘보다 효율적이다.
• 성능이 좋은 편이다.
• 많은 운영체제가 채택하는 알고리즘이다.

LFU (Least Frequently Used) 알고리즘

• 참조횟수가 가장 적은 페이지를 교체하는 알고리즘이다.
• 교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지를 교체한다.

• 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 문제가 될 수 있다.
• 앞으로 사용하지 않아도 초기에 사용된 참조횟수가 높아 메모리에 계속 남아있기 때문이다.
• 초기에만 쓰인 7이 메모리에 잔존해 낭비가 일어난다.

MFU (Most Frequently Used)  알고리즘

• LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다.
• 참조 횟수가 적은 페이지가 최근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단이다.

LFU와 MFU는 실제 잘 사용하지 않는다.
구현에 상당한 비용이 들고, 최적 페이지 교체 정책을 (LRU만큼) 제대로 유사하게 구현하지 못하기 때문이다.

LRU Cache

캐시 (Cache)

캐시는 연산에 필요한 데이터, 값을 미리 갖다놓는 임시 메모리이다. CPU에서 주기억장치, 보조기억장치까지 도달하는 비용은 매우 크고, 물리적으로 거리가 멀다고 할 수 있다. 그런데 캐시의 경우 CPU 바로 옆에 딱 달라붙어있기 때문에 물리적으로도 거리가 매우 짧아 접근 비용이 매우 적다. 따라서 자주 사용되는 값이나, 사용될 예정인 값을 미리 캐시에 적재해놓는다면 참조 시간을 대폭 줄여 성능을 높일 수 있다.

CPU는 어떤 값이 필요할 때 가장 먼저 캐시를 방문하고 만약 캐시에 원하는 값이 있을 경우 이를 사용하는데, 만약 없다면 주기억 장치를 방문한다. 따라서, CPU 가 자주 사용하는 값, 필요로 하는 값 등을 적절히 캐시에 배치해두어야 한다. 즉, 캐시 히트율을 높여야 성능을 높일 수 있다.

Cache Hit : CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우
Cache Miss : CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않는 경우

캐시의 내용물들은 자주 갈아끼워질 필요가 있다. 캐시의 용량은 한정적이지만 자주 사용되는 값 혹은 사용될 예정인 값은 시시각각 변하기 때문이다. 막무가내로 내용물을 갈아끼우면 캐시 히트율을 항상 높게 유지하기 어려울 것이고, 성능 악화로 이어질 수 있다. 따라서 캐시 히트율을 높게 유지하는 메모리 교체 알고리즘이 필요하다. Cache 알고리즘 중에 가장 유명한 알고리즘 중 하나는 LRU 알고리즘이다.

LRU 알고리즘

캐시에 공간이 부족할 때 가장 오랫동안 사용하지 않은 항목을 제거하고, 새로운 데이터를 배치한다.

구현은 보통 LinkedList, Queue, ArrayList 등을 사용한다.

Reference

이 문제는 비트 연산(Bitwise Operaiton)을 묻는 문제라고 한다. 2진수로 처리하라는 내용이 힌트이고, OR로 처리하면 된다. if else 풀이를 한 사람이 많았지만 ( 뜨끔 ,, ) 비트 연산을 잘 다룰 수 있는지를 묻고자 하는 의도였다고 한다. 이런 유형을 풀 때는 비트 연산을 기억하자 !.

처음 구상한 코드는 다음과 같다. 

1. toBinaryString()을 사용해 10진수를 2진수로 변환한다.

2. 변환한 2진수의 길이를 통일한다.

3.   StringBuilder를 이용해 공백 혹은 #을 append 하고, 그 값을 answer에 넣어준다.

import java.util.*;

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        
        for (int i=0; i<n; i++) {
            
            // 1. 10진수를 2진수로 변환한다.
            
            String x = Integer.toBinaryString(arr1[i]);
            String y = Integer.toBinaryString(arr2[i]);
            
            // 2. 변환한 2진수의 길이를 통일한다.
            
            String zero = "";
            if (x.length()<n) {
            	int num = n - x.length();
            	for (int j=0; j<num; j++) {
            		zero = "0" + zero ;
            	}
            	x = zero + x;
            }
            
            zero = "";
            if (y.length()<n) {
            	int num = n - y.length();
            	for (int j=0; j<num; j++) {
            		zero = "0" + zero ;
            	}
            	y = zero + y;
            }
            
            // 3. 두 장의 지도를 겹친다.
            
            StringBuilder sb = new StringBuilder();
            
            for (int j=0; j<n; j++) {
                char a = x.charAt(j);
                char b = y.charAt(j);
                
                if (a == '0' && b == '0') sb.append(" ");
                else sb.append("#");
            }
            
            answer[i] = sb.toString();

        }
        
        return answer;
    }
}

+ 더 나은 풀이 방법

문제를 다 풀고 다른 코드를 찾아보니

나처럼 arr1과 arr2 안의 숫자를 각각 2진수로 변환해 두 숫자를 합치지 않아도,

비트 논리 연산자 OR (논리합)를 사용하면 더 간단한 코드로 구현할 수 있다.

OR ( | )는 두 비트 중 하나만 1이면 연산 결과는 1이다.

변환한 2진수는 문자열의 형식을 설정할 때 이용하는 %s(=String Formatting)을 이용해 길이를 통일한다.

String.format("%" + n + "s", binary) :  binary의 길이보다 숫자 n이 더 작으면 앞에 공백을 추가해준다고 한다.

마지막으로 문자열 치환을 해주는 Replace 함수를 사용해 공백 혹은 #으로 바꾸어준다.

코드는 아래와 같다.

import java.util.*;

class Solution {
    public String[] solution(int n, int[] arr1, int[] arr2) {
        String[] answer = new String[n];
        
        for (int i=0; i<n; i++) {
            
            // 1. 10진수를 2진수로 변환 : 비트 논리 연산자 OR 사용
            
            String binary = Integer.toBinaryString(arr1[i] | arr2[i]);
            binary = String.format("%" + n + "s", binary);
            
            // 2. replace 함수로 문자열을 치환한다.
            
            binary = binary.replace('0', ' ');
            binary = binary.replace('1', '#');        
            answer[i] = binary;
        }
        return answer;
    }
}

그런데 실행 결과를 보면 효율은 첫 번째로 푼 코드가 더 좋아보인다 ,,

하지만 !

Kakao Tech 블로그에서 문제 해설을 보면 이 문제는 비트 연산(Bitwise Operaiton)을 묻는 문제라고 한다.

2진수로 처리하라는 내용이 힌트이고, OR로 처리하면 된다.

if else 풀이를 한 사람이 많았지만 ( 뜨끔 ,, ) 비트 연산을 잘 다룰 수 있는지를 묻고자 하는 의도였다고 한다.

이런 유형을 풀 때는 비트 연산을 기억하자 !

백트래킹 (Backtracking) 이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다.

코딩에서는 반복문의 횟수를 줄일 수 있어 효율적이다.

일종의 트리 탐색 알고리즘이라고 봐도 된다.

모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다.

보통 비선형으로 구성된 자료 구조를 깊이 우선 탐색(Depth First Search, DFS)할 때, 

더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정이다.

깊이 우선 탐색(DFS) VS 백트래킹(Backtracking)

DFS는 가능한 모든 경로를 탐색한다. (완전 탐색 O)

불필요할 것 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 줄이지 못한다.

백트래킹은 모든 경로 중 특정 조건을 만족하는 경로만 탐색한다. (완전 탐색 X)

유망성 (promising) VS 가지치기 (pruning)

불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미에서 '가지치기'라고도 한다.

가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다.

유망성을 판단했을 때,

해가 될 가능성이 있는 것은 promising, 유망하지 않은 노드에 가지 않는 것은 pruning ! 

주로 문제를 풀 때 DFS 등으로 모든 경우의 수를 탐색하는 과정에서 답이 절대로 될 수 없는 상황을 조건문으로 정의하고, 그러한 상황일 경우에는 탐색을 중지하고 그 이전으로 돌아가서 다시 다른 경우를 탐색하도록 구현한다. 

즉, 백트래킹은 최적화 문제와 결정 문제를 푸는 방법이 되고, 보통 재귀함수로 구현한다.

+ 탐색 알고리즘이란 ?

Reference