Unity 내일배움캠프 TIL 0824 | 알고리즘 Largest Rectangle in Histogram | 컴퓨터 핵심 부품 | 이진법

cheeseonrose·2023년 8월 24일
CCSTILstudy내일배움캠프스파르타 코딩클럽알고리즘
0

Unity 내일배움캠프

목록 보기
19/89
post-thumbnail

오늘 할 일은 오전에 알고리즘 세션 듣기 + 1시간 동안 주어진 알고리즘 문제들 풀기
끝나고 나면 어제 다 못한 5주차 과제 마저 풀어서 제출하기~~

알고리즘 세션

  • 디버깅시 조사식, 호출 스택, 직접 실행 창 추가하기



C# 5주차 과제

Largest Rectangle in Histogram

  • 하 ... 이거 하나 푼다고 너덜너덜해지다니 나약하다 나약해
    스택으로 푸는 어려운 문제들 중 유명한 유형인 것 같은데, 난 왜 이제 처음 봤지!!!
    아직도 풀어야 될 알고리즘 문제들이 정말 많구나 새삼 느꼈다
  • 처음에는 배열 정렬해서 푸는 줄 알고 착각했는데 순서를 바꾸며 안 되는 거였다. 당연함. 난이도 Hard임.
    그래서 혹시 DP인가 했는데 아무래도 그건 아닌 것 같고 이것저것 해보다가 결국 구글링을 해봤다.
  • 보통 세가지로 푸는데, 스택으로 풀거나 분할 정복으로 가운데 기준으로 나누거나 특정 막대를 기준으로 나누거나 하는 것 같다. 스택으로 푸는게 분할 정복 풀이법보다 더 효율적이고 간결하니 일단 풀이 방법은 스택으로 정했는데 중요한 건 풀이법이 이해가 안 된다는 것임.
    낑낑대다가 유투브에서 빛과 같은 강의를 찾았따!
    YouTube 히스토그램에서 가장 큰 직사각형
  • 개발 블로그에서는 다 똑같은 소리만 해서 헤매다가 찾았는데 이게 훨씬 이해가 잘 돼서 영상에 나오는 첫 번째 방법으로 풀이했다.
  • 스택 내부의 원소들을 오름차순으로 유지하는 방법을 "모노톤 스택" 이라고 한다.

풀이

  • 우리가 구하는 직사각형은 히스토그램 막대바의 윗변에 닿게 되어있다.
    그러니까 우리는 이 윗변을 기준으로 특정 윗변을 포함하는 직사각형들 중 넓이 최대값을 찾으면 되는 것.
  • 예를 들어, 위 그림의 5번째, 높이가 2인 막대바의 윗변을 포함하는 직사각형을 만든다고 가정하자.
    이 직사각형은 5번째 막대바 전체를 포함하게 될 것임
    그럼 이 5번째 막대바를 왼쪽, 오른쪽으로 최대한 늘리면 그게 우리가 정한 윗변을 포함하는 직사각형의 최대 넓이가 되는 것이다.
    그럼 왼쪽부터 늘려보자. 높이가 2인 이 윗변을 왼쪽으로 쭉 그으면 높이가 5인 세번째 막대바까지 늘릴 수 있고, 그 왼쪽에는 높이가 1짜리인 막대바가 있기 때문에 더 이상 늘릴 수 없다.
    오른쪽도 마찬가지로 쭉 늘려주면 마지막 막대바까지 늘릴 수 있게 된다.
    그러면 우리가 구하는 직사각형은 아래와 같아진다.
  • 그니까 쉽게 말해서 윗변을 하나 정하고 거기서 총을 쏜다고 생각하면 됨
    날아가는 총알이 벽에 맞고 떨어지는 곳까지가 직사각형의 넓이라는 것
    우리는 이 정보를 left[], right[] 배열에 담을 것인데
    left에는 i번째 막대의 왼쪽에서 이 막대의 높이보다 낮은 첫 번째 막대의 인덱스를 저장할 것이고, right는 오른쪽에서 이 막대 높이보다 낮은 첫 번째 막대의 인덱스를 저장할 것이다.
    i번째 막대를 포함하는 직사각형의 최대 넓이는 (right[i] - left[i] - 1) * heights[i] 가 되는 것
    영상 보면 이해가 더 쉬움
  • 암튼 이런 식으로 직사각형 넓이들을 구해서 그 중 최대값을 찾으면 됨
  • 한 가지 고려할 것은 왼쪽이나 오른쪽 가장 끝까지 늘릴 수 있는 경우에 왼쪽은 인덱스가 -1, 오른쪽은 인덱스가 heights.Length가 된다는 것
  • 전체 코드
public static int LargestRectangleArea(int[] heights)
{
	int[] left = GetFirstSmallerIndexArray(heights, true);
    Array.Reverse(heights);
    int[] right = GetFirstSmallerIndexArray(heights, false);
    Array.Reverse(heights);
    Array.Reverse(right);
    
    int maxArea = 0;
    for (int i = 0; i < heights.Length; i++)
    {
    	int curArea = (right[i] - left[i] - 1) * heights[i];
        if (curArea > maxArea) maxArea = curArea;
    }
    
    return maxArea;
}

public static int[] GetFirstSmallerIndexArray(int[] target, bool isLeft)
{
	int length = target.Length;
    Stack<int> stack = new Stack<int>();
    int[] result = new int[length];
    
    for (int i = 0; i < length; i++)
    {
    	while (stack.Count > 0)
        {
        	int idx = stack.Peek();
            if (target[idx] >= target[i])
            {
            	stack.Pop();
            }
            else break;
        }
        int resultIdx = (stack.Count == 0) ? -1 : stack.Peek();
        result[i] = (isLeft) ? resultIdx : (length - 1 - resultIdx);
        stack.Push(i);
    }
    return result;
}
  • 개발 블로그들에 주구장창 나온 스택으로 푸는 방법들보다는 훨씬 길지만 아무래도 난 이쪽이 이해하는게 편해서..이렇게 했다! 어쩔건데!

마참내 해결했다~,, 아이고,,,



과제 제출하고 나서는 CS 강의 듣기!!
이게 대체 몇년만에 듣는 기초 강의

컴퓨터가 이해하는 정보

데이터

  • 숫자, 문자, 이미지, 동영상 같은 정적인 정보
  • 컴퓨터와 주고 받는 / 내부에 저장된 정보
  • 0과 1로 숫자 / 문자를 표현하는 방법

명령어

  • 컴퓨터를 실질적으로 움직이는 정보
  • 데이터는 명령어를 위한 일종의 재료
1과 2를 출력하라 -> 명령어
-> 1, 2 : 데이터

컴퓨터의 네 가지 핵심 부품

CPU

  • 메모리에 저장된 명령어를 읽어 들이고, 해석하고 실행함
  • 구성 부품
    • ALU(산술 논리 연산 장치) : 계산기
    • 제어장치 : 제어 신호를 내보내고 명령어를 해석
      • 제어신호 : 컴퓨터 부품들을 관리하고 작동시키기 위한 전기 신호
        (ex : 메모리 읽기/쓰기 신호)
    • 레지스터 : CPU 내부의 작은 저장장치

메모리(RAM, 주기억장치)

  • 프로그램이 실행되기 위해서는 메모리에 저장되어야 함
  • 현재 실행되고 있는 프로그램의 데이터와 명령어를 저장
  • 주소를 가짐 -> 저장된 데이터와 명령어의 위치를 특정

보조기억장치

  • 메모리(RAM)에 저장된 데이터는 전원이 꺼지면 저장된 내용을 잃음
    -> 휘발성 저장장치
  • 전원이 꺼져도 보관될 프로그램을 저장
  • 메모리는 실행할 정보를, 보조기억장치는 보관할 정보를 저장

입출력장치

  • 컴퓨터 외부에 연결되어 컴퓨터 내부와 정보를 교환할 수 있는 부품
  • 보조기억장치와 입출력장치
    • 주변장치라고 통칭하기도 함
    • 보조기억장치는 메모리를 보조하는 특별한 입출력장치라고 이해하면 됨

메인보드

  • 컴퓨터의 부품들을 한 곳에 모아서 연결하는 곳

시스템 버스

  • 메인보드 안에 연결된 부품들이 정보를 주고 받는 통로 중 가장 중요한 통로
  • 주소 버스 : 주소를 주고받는 통로
  • 데이터 버스 : 명령어와 데이터를 주고받는 통로
  • 제어 버스 : 제어 신호를 주고받는 통로

0과 1로 숫자를 표현하는 방법

정보 단위

  • 비트(bit) : 0과 1을 표현하는 가장 작은 정보 단위
  • n비트로 2^n가지의 정보 표현 가능
  • 바이트, 킬로바이트, 메가바이트, 기가바이트, 테라바이트 등 여러 단위가 있음
1개 단위1,000개 단위
1바이트(1byte)8비트(8bit)
1킬로바이트(1kB)1,000바이트(1,000byte)
1메가바이트(1MB)1,000킬로바이트(1,000kB)
1기가바이트(1GB)1,000메가바이트(1,000MB)
1테라바이트(1TB)1,000기가바이트(1,000GB)
  • 1,024개씩 묶은 단위는 kiB, MiB, GiB ...
    • 과거에는 구분하지 않았으나 요즘은 구분함
  • 워드(word) : CPU가 한 번에 처리할 수 있는 정보의 크기 단위
    • 하프 워드(half word) : 워드의 절반 크기
    • 풀 워드(full word) : 워드 크기
    • 더블 워드(double word) : 워드의 두 배 크기

이진법(binary)

  • 0과 1로 수를 표현하는 방법
  • 1000(2) 또는 0b1000처럼 표현
    • (2)는 아래첨자임
  • 0과 1로 음수 표현하기 : 2의 보수
    • 어떤 수를 그보다 큰 2^n에서 뺀 값
    • 11(2)보다 큰 2^n = 100(2)
      • 100(2) - 11(2) = 01(2)
    • 모든 0과 1을 뒤집고 1을 더한 값임
    • -1011(2)을 표현하는 0101(2)과 5를 표현하기 위한 0101(2)의 구분
      • CPU 내부 플래그(flag) 레지스터에 플래그 값을 저장함

16진법

  • 이진법으로는 숫자의 길이가 너무 길어짐
10진수16진수10진수16진수
0010A
1111B
2212C
3313D
4414E
5515F
661610
771711
881812
99......
  • 15(16) 또는 0x15 로 표기
  • 2진수 -> 16진수 변환
    • 4개씩 나누어 변환
    • 0001 1010 0010 1011 (2)
      -> 1A2B(16)
  • 16진수 -> 2진수
    • 자리 하나씩 2진수로 변환하면 됨

문자 집합과 인코딩

  • 문자 집합(character set) : 컴퓨터가 이해할 수 있는 문자의 모음
  • 인코딩(encoding) : 코드화하는 과정
    • 문자를 0과 1로 이루어진 문자 코드로 변환
  • 디코딩(decoding) : 코드를 해석하는 과정
    • 0과 1로 표현된 문자 코드를 문자로 변환

아스키 코드

  • 초창기 문자 집합 중 하나
  • 알파벳, 아라비아 숫자, 일부 특수 문자 및 제어 문자
  • 7비트로 하나의 문자 표현 -> 2^7개의 문자 표현 가능
    • 실제로는 8비트이지만 1비트는 오류 검출을 위해 사용되는 패리티 비트(parity bit)
  • 코드 포인트(code point) : 문자에 부여된 값
  • 인코딩이 간단함
  • 한글 등 다른 언어 및 특수 문자 표현 불가능
    • 8비트 확장 아스키가 등장했으나 여전히 부족함

한글 인코딩

  • 완성형 인코딩 방식과 조합형 인코딩 방식이 존재
    • 완성형 인코딩 : 단어 하나하나에 코드를 부여 ("감", "자")
    • 조합형 인코딩 : 초성, 중성, 종성 하나하나에 코드를 부여 ("ㄱ", "ㅏ", "ㅁ")
  • EUC-KR : 완성형 한글 인코딩 방식
    • 글자 하나에 2바이트 크기 부여 (2바이트 == 16비트 == 4자리 16진수로 표현)
    • 하지만 여전히 제한적임

유니코드 문자 집합과 utf-8

  • 유니코드 : 통일된 문자 집합
  • 유니코드의 인코딩 방식 : utf-8, utf-16, utf-32...
  • utf-8 : 가변 길이 인코딩 (인코딩 결과가 1~4바이트)
    • UTF(Unicode Transformation Format)
    • 인코딩 결과가 몇 바이트가 될지는 유니코드에 부여된 값에 따라 다름



역대급 피곤한 하루 ~.~ 컨디션 관리 잘 해야겠당
저놈의 히스토그램 때문에 너무 오래 고민한 것 같아서 더 피곤한듯

어제 신의탑 정주행 하다가 늦게 잔건 비밀
히히..
신의탑은 전설이다 ...

오늘 공부는 여기까지~~
끗~

profile
cheeseonrose
푸헹
이전 포스트

Unity 내일배움캠프 TIL 0823 (2) | LIS

다음 포스트

Unity 내일배움캠프 TIL 0825 | 명령어 | 인터럽트

0개의 댓글