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

• [Programmers] 12909. 올바른 괄호

  2023-02-04

  devfancy

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

  문제 링크

  성능 요약

  • 메모리: 52.8 MB, 시간: 19.78 ms - Answer Code1

  • 메모리: 53.1 MB, 시간: 7.90 ms - Answer Code2

  구분

  코딩테스트 연습 > 스택／큐

  Answer Code1(23.02.04)

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

  Answer Code1 - 문제 풀이

  • 스택을 이용하여 괄호가 짝을 이룬다면 스택을 제거한다.

  • 문자열을 끝까지 검사했을 때 스택의 크기가 0이면 올바른 괄호이므로 true를 반환하고, 그렇지 않으면 false를 반환한다.

  • [1] 정답을 저장할 변수로 answer와 stack을 선언하고, 반복문을 이용하여 문자열을 앞에서부터 비교한다.

  • [2] 문자를 비교할 때 ( 일 경우 스택에 push 한다.

  • [3] )일 경우 이때, stack의 크기가 0이 아니라면 스택에 pop 한다.

    • stack의 크기가 0이 아니라면 (가 있다는 의미이고, 스택의 크기가 0이라면 (가 없으므로 짝을 이룰 수 없다.

  • [4] 문자열을 끝까지 확인한 이후에 스택의 크기가 0이면 true, 아니면 false를 return 한다.

  Answer Code2(23.02.04)

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

  Review

  • (2번째 풀이) 다른 사람의 풀이를 가져와봤는데, 스택을 사용안하면서 count 변수를 사용하여 깔끔하게 풀이했다.

  • 그 결과 1번째 풀이보다 시간적인 측면에서 3배 가까이 시간을 절약하는 것을 볼 수 있었다.

  • 스택을 사용한다고 해서 좋은 정답은 아니라는 것을 알 수 있었다.

  Read All

  ---

• [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

  ---