지금의 기록이 미래의 자산이 된다.

• [Programmers] 12951. JadenCase 문자열 만들기

  2023-02-03

  devfancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(23.02.03)
  • Answer Code1 - 문제풀이
  • Review

  문제 링크

  성능 요약

  메모리: 86.2 MB, 시간: 4.88 ms - Answer Code1

  구분

  코딩테스트 연습 > 연습문제

  Answer Code1(23.02.03)

  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);
      }
  }
  

  Answer Code1 - 문제풀이

  1. 기존 문자열 이름인 str 을 split(" ")을 사용하여 공백을 기준으로 잘라서 String 배열에 저장한다.

  2. 잘린 String 배열을 순서대로 처리한다.

     • 첫 번째 문자와 나머지 문자를 나눈다 -> substring()

     • 첫 번째만 대문자로, 나머지는 소문자로 변환한다.

       • toUpperCase() : 소문자 -> 대문자

       • toLowerCase() : 대문자 -> 소문자

     • 단어 사이에 공백을 위해 마지막에 " "을 추가한다.

  3. 입력 받은 문자열의 맨 마지막이 " "이라면(기존에 있었던 공백이면), 바로 answer을 반환한다.(마지막 공백을 지우지 않는다)

  4. 입력 받은 문자열의 맨 마지막이 " "이 아니라면 해당 부분을 제거하고 반환한다.

  Review

  • 첫 번째 부분과 나머지 부분을 구분하는 경우에는 substring() 을 사용하자.

  • 소문자와 대문자간 변환할 때 쓰이는 toUpperCase(), toLowerCase()에 대해 다시 공부하게 되었고,

  • (중요) 문제풀이 - 3번째 조건 부분이 없으면 테스트케이스 부분이 실패로 되버렸다.

    • 문제에 대한 설명 부분을 놓치지 말고, 완벽히 이해해야 한다는 것을 일깨워줬다.
  Read All

  ---

• [Programmers] 12939. 최댓값과 최솟값

  2023-02-03

  devfancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(23.02.03)
  • Answer Code2(23.02.03)

  문제 링크

  성능 요약

  메모리: 83.7 MB, 시간: 28.33 ms - Answer Code1

  메모리: 87.1 MB, 시간: 9.33 ms - Answer Code2

  구분

  코딩테스트 연습 > 연습문제

  Answer Code1(23.02.03)

  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;
      }
  }
  

  Answer Code2(23.02.03)

  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;
      }
  }
  

  Read All

  ---

• 18. Paging

  2023-02-02

  devfancy

  OS
  • Concept of Paging
  • Advantages Of Paging
  • A Simple Paging
  • How To Store Address Translation
  • Address Translation

  이 글의 사진과 내용은 공룡책 과 컴퓨터학부 수업인 운영체제 강의자료를 기반으로 작성했습니다.

  Concept of Paging

  • Paging은 프로세스의 가상 주소 공간을 고정적인 크기(fixed-sized)로 나누어서 메모리에 할당하는 방식이다. 이때 고정적인 크기 단위를 page라고 부른다.

  • 그리고 이러한 가상공간의 page 를 실제 메모리에 할당할 때 이를 page frame이라고 부른다.

  • 즉 가상 메모리(주소 공간)에서는 page, 실제 메모리(주소 공간)에서는 frame 이라고 불리는 고정 크기의 공간으로 프로세스를 실행하겠다는 의미이다.

  Advantages Of Paging

  • Flexibility : 주소 공간의 추상화를 효율적으로 지원한다.

    • 얼마나 heap과 stack이 커지고 사용하는지에 대한 고민을 할 필요가 없다.

  • Simplicity : 여유 공간(free-space)의 관리가 쉽다.

    • 가상 메모리의 page와 page frame이 같은 크기를 가진다.

    • 할당이 쉽고 여유 공간을 유지한다.

  A Simple Paging

  • 128-byte physical memory with 16 bytes page frames

  • 64-byte address space with 16 bytes pages

  

  • 위의 그림에서 4개의 page로 구성된 가상 주소 공간을 8개의 page frame으로 쪼갠 것을 볼 수 있다.

  How To Store Address Translation

  • Paging 기법을 사용하기 위해서 가상 주소 공간에 있는 프로세스의 page들이 실제 메모리의 어디에 위치를 하는 지를 기억하는 Page table을 가지고 있어야 한다.

  

  • Page table 이란 가상 주소 공간의 page가 실제 메모리(주소 공간)에 어디에 위치해 있는 지를 기록한다.

    • Per-process structure(프로세스별 구조)

    • OS 가상 메모리의 영역에 저장된다.

  Address Translation

  • Paging 기법을 이용하여 주소 변환을 구하는 방법에 대해 알아보자.

  • 가상 주소 공간에는 두 가지 요소가 있다.

    • VPN : Virtual Page Number -> 상위 2개의 bit이 Page를 표현한다.

    • Offset : page 안에 있는 offset -> 나머지 4개의 bit이 offset을 표현한다.

  

  • Example: virtual address 21 in 64-byte address space

  

  A Simple 64-byte Address Space

  

  • Page table을 통해서 Virtual Page, Physical Page frame 의 i번째를 찾는다.

    • VPN 에서 상위 2개의 bit 값이 1이므로 page 1에 해당한다.

  • Offset을 통해 그 Page 안에 몇번째 메모리 주소인지 찾는다.

    • offset 값이 5이므로 16부터 시작해서 5번째인 21를 의미한다.
  Read All

  ---

• [Programmers] 17680. [1차] 캐시

  2023-01-31

  devfancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(23.01.31)
  • Answer Code2(23.02.20)
  • Review
  • Reference

  문제 링크

  성능 요약

  • 메모리: 78.5 MB, 시간: 2.76 ms - Answer Code1(23.01.31)

  • 메모리: 81.4 MB, 시간: 2.66 ms - Answer Code2(23.02.20)

  구분

  코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT

  Answer Code1(23.01.31)

  import java.util.*;
  
  class Solution {
      public int solution(int cacheSize, String[] cities) {
          int answer = 0;
          ArrayList<String> cache = new ArrayList<>();
  
          if(cacheSize == 0) // 캐시크기가 0
              return cities.length * 5;
  
          for(int i=0; i<cities.length; i++) {
              cities[i] = cities[i].toUpperCase(); // 대소문자 구분X
              if(cache.contains(cities[i])) { // cache hit
                  cache.remove(cities[i]);
                  cache.add(cities[i]);
                  answer += 1;
              }
              else { // cache miss
                  if(cache.size()==cacheSize) {
                      cache.remove(0);
                      cache.add(cities[i]);
                  }
                  else
                      cache.add(cities[i]);
                  answer += 5;
              }
          }
          return answer;
      }
  }
  

  Answer Code2(23.02.20)

  import java.util.*;
  
  class Solution {
      public int solution(int cacheSize, String[] cities) {
          int answer = 0;
          
          List<String> cacheList = new ArrayList<>();
          
          if(cacheSize == 0) {
              return cities.length * 5;
          }
          
          for(int i = 0; i < cities.length; i++) {
              cities[i] = cities[i].toLowerCase(); // 소문자로 변환
              //cache hit
              if(cacheList.contains(cities[i])) {
                  cacheList.remove(cities[i]);
                  cacheList.add(cities[i]);
                  answer += 1;
              }
              //cache miss
              else {
                  answer += 5;
                  if(cacheList.size() == cacheSize) {
                      cacheList.remove(0);
                      cacheList.add(cities[i]);
                  }
                  else {
                      cacheList.add(cities[i]);
                  }
              }
          }
          
          return answer;
      }
  }
  

  Review

  • LRU(Least Recently Used)에 대해 알고 있어야 풀 수 있는 문제였다.

    • LRU : 가장 오랫동안 참조하지 않은 페이지를 캐시에서 교체하는 것이다.

    • LRU 알고리즘 구현을 보통 자료구조 Queue(큐)로 사용하면 편리하지만, Java에서는 LikedList가 Queue의 구현체이므로 Likedlist로 구현했다.

  • cache hit 인 경우(캐시에 존재한 경우) hit된 데이터를 기존 위치에서 가장 최근 위치로 이동 시킨다.(기존 위치를 제거하고 맨 뒤에 데이터를 추가한다)

  • cache miss 인 경우

    • 새로 만든 cache의 크기가(cache.size()) 기존 캐시 크기(cacheSize)와 동일한다면, 꽉차있는 의미이므로 가장 오랫동안 사용하지 않은 것을 제거하고, 맨 뒤에 데이터를 추가한다.

    • 새로 만든 cache의 크기가(cache.size()) 기존 캐시 크기(cacheSize)와 동일하지 않다면, 맨 뒤에 데이터를 추가한다.

  Reference

  • LRU 개념
  Read All

  ---

• [Programmers] 92334. 신고 결과 받기

  2023-01-29

  devfancy

  Algorithm
  • 성능 요약
  • 구분
  • Answer Code1(23.01.29)
  • Review

  문제 링크

  성능 요약

  메모리: 70.2 MB, 시간: 0.49 ms

  구분

  코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT

  Answer Code1(23.01.29)

  import java.util.*;
  
  class Solution {
      public int[] solution(String[] id_list, String[] report, int k) {
          int[] answer = new int[id_list.length];
          ArrayList<User> users = new ArrayList<>();
          HashMap<String,Integer> suspendedList = new HashMap<>();
          HashMap<String,Integer> idIdx = new HashMap<String,Integer>();
          int idx = 0;
  
          //각 유저에 대한 고유 index를 setting후 users ArrayList에 User 객체 추가
          for(String name : id_list) {
              idIdx.put(name, idx++);
              users.add(new User(name));
          }
  
          //users의 idIdx.get(str[0])번째 index에 reportList에 피신고자 추가
          //users의 idIdx.get(str[1])번째 index에 reportedList에 신고자 추가
          for(String re : report){
              String[] str = re.split(" ");
              users.get(idIdx.get(str[0])).reportList.add(str[1]);
              users.get(idIdx.get(str[1])).reportedList.add(str[0]);
          }
  
          //reportedList의 크기가 주어진 k와 같거나 크면 suspendedList의 피신고자 put
          for(User user : users){
              if(user.reportedList.size() >= k)
                  suspendedList.put(user.name,1);
          }
  
          //answer 배열 각 index에 해당하는 유저의 신고당한 횟수를 count up
          for(User user : users){
              for(String nameReport : user.reportList){
                  if(suspendedList.get(nameReport) != null){
                      answer[idIdx.get(user.name)]++;
                  }
              }
          }
          return answer;
      }
  }
  
  class User{
      String name;                        //해당 유저명
      HashSet<String> reportList;		    //피신고자 리스트
      HashSet<String> reportedList;	    //신고자 리스트
      public User(String name){
          this.name = name;
          reportList = new HashSet<>();
          reportedList = new HashSet<>();
      }
  }
  

  Review

  • 해당 문제를 제대로 이해하지 못한다면 2022 카카오 신입 공채 1차 온라인 코딩테스트 for Tech developers 문제해설

    를 참고하자.

  Read All

  ---