코드 훔쳐보는 변태 코더
춤 좋아하는 백엔드 개발자(였으면 좋겠다)
전체 글 (95)
컴퓨터 시스템을 구성하는 방법과 동작 원리

컴퓨터 시스템을 구성하는 방법과 동작 원리

  • 시스템 버스 → 통신하기 위한 경로를 버스라고 통하는데, CPU와 메모리간의 통신, CPU와 IO간의 통신은 모두 시스템 버스를 이용하게 된다.
    • 컨트롤 버스
      • 제어 신호를 전달하는 버스이다.
      • 양방향성 버스이다. (바이 디렉셔널)
      • 신호 선들의 집합이다.
    • 어드레스 버스
      • 주소 공간을 보내기 위한 버스이다. (포트번호 등)
      • 어드레스 버스와의 통신은 단방향이다. → 주소공간이라는 개념은 CPU에 의해서 발생이 되서 CPU에서 나가기만 하기 때문이다.
      • 신호 선들의 집합이다. → 주소 선의 갯수는 CPU와 접속될 수 있는 최대 기억장치의 용량을 결정한다. (주소 버스의 비트가 16비트인경우엔 64K의 기억장소의 주소를 지정할 수 있게 된다.)
    • 데이터 버스
      • 정보를 보내기 위한 버스이다.
      • 양방향성 버스이다.
      • 마찬가지로 신호 선들의 집합이다. 비트의 수를 결정하게 된다.
  • 메모리에서 사용되는 버스는 고속의 IO를 요구하는 경우가 많다.
  • 읽기 쓰기 신호는 1비트를 사용하는 신호이기 때문에 0과 1로 신호를 보내게 된다.

기억장치 액세스 동작

  • 액세스
    • 기억장치에 데이터를 쓰거나 읽는 동작을 액세스라고 한다.
  • 기억장치 쓰기
    • CPU는 데이터를 저장할 기억장치의 주소를 주소버스로 보내고 저장할 데이터를 동시에 데이터 버스로 보낸다.
    • 쓰기 신호를 활성화 해 1을 전송한다.
    • 해당 신호가 기억장치 쓰기 동작이 완료가 될때까지 유지가 된다.
      • 저장이 완료될때까지의 시간을 기억장치 쓰기 시간이라고 칭한다.
  • 기억장치 읽기
    • CPU가 기억장치 주소를 주소버스를 통해서 보내고 읽기 신호를 활성화한다.(0)을 보낸다.
    • 기억장치로부터 읽혀진 데이터가 데이터 버스에 실리고, CPU는 데이터버스를 통해서 읽어들인다.
    • 주소를 해독하는데 걸리는 시간이나 기억장치 내부에서 데이터를 인출하는데 시간이 걸리기 떄문에 지연시간이 발생된다.
      • 읽기 동작이 완료될떄까지의 시간을 기억장치 읽기 시간이라고 칭한다.

CPU와 I/O 장치의 접속

  • I/O 제어기 라는것을 이용해야 한다. (바로 연결이 불가능하다.)
  • 입력 출력 명력을 받아서 해당 IO장치에 제어를 하거나 데이터를 이동하거나 하는 명령을 수행하는 역할을 한다.
    • 상태 레지스터
      • IO 장치의 현재 상태를 나타내는 비트를 저장하는 레지스터이다.
    • 데이터 레지스터
      • CPU와 IO장치간에 이동되는 데이터를 일시적으로 저장 할 수 있도록 하는 레지스터이다.
  • IO 장치를 제어하는 방법은 3가지가 존재한다. (나중에 정리)
  • 키보드를 통해서 데이터를 입력한다면 ?
    • 키보드에 어떠한 키를 누르게 되면 해당 키에 대응되는 아스키 코드가 키보드 제어기를 통해서 데이터 레지스터에 저장이 된다.
      • 동시에 상태 레지스터는 입력준비비트가 1이 된다.
    • CPU는 키보드 제어기로부터 상태 레지스터를 읽어서 1이 되었는지 확인하고, 아닌 경우에는 대기했다가 1이 되었는지를 확인하는 과정을 반복한다.
    • 1이 되었다면 데이터 레지스터의 내용을 읽어 데이터를 전달받게 된다.
  • 보조 저장장치들도 IO 컨트롤러를 다 갖고 있다.
    • 키보드나 프린터같은 것들은 바이트 단위로 데이터를 전송하는데, 보조 저장장치는 블록을 단위로 전송한다.
    • 이것을 버퍼라고 한다.
    • 보조 저장장치에서 사용되는 데이터 레지스터를 데이터 버퍼라고 칭한다.

컴퓨터 구조의 발전 과정

계산장치의 역사

  • 초기의 계산 장치 → 기계식 계산기들을 얘기한다.
    • 1642년 파스칼 라인
      • 파스칼이 개발하였다.
      • 톱니바퀴를 이용한 수동계산기이다. (덧셈과 뺄셈만 가능하다.)
    • 1671년 가감승제 계산기
      • 라이프니츠 (2진법 창시자)
      • 곱셈과 나눗셈도 가능한 계산기이다.
    • 이후에 자동 계산기가 등장하게 된다.
    • 1823 년 차분기관 (차등기라고 표현하기도 한다.)
      • 찰스 배비지
      • 증기로 작동하는 자동 계산기이다.
      • 삼각 함수를 계산하여 종이에 인쇄한다. (소숫점 5자리까지 계산이 가능했다.)
    • 찰스 배비지가 차분기관을 발전시켜 1837년에 해석기관을 설계하게 된다.
      • 방정식을 순차적으로 풀 수 있도록 기계식 계산기를 설계하게 된다.
  • 해석기관의 기본 구조
    • 연산장치 MILL
    • 기억장치 STORE
    • 입력장치 카드 판독기
      • 출력장치 프린터, 카드천공기
    • 연산 카드에 의해서 미리 수행할 연산이 지정이 되고, 해당 연산에 사용될 데이터의 주소는 변수카드에 의해서 지정이 된다.
      • 그러면 MILL은 스토어 내의 지정된 위치로부터 데이터를 읽어와서 레지스터에 저장하고, 연산을 수행한 후에 결과값을 스토어에 저장한다.
      • 여기서 연산 카드와 변수 카드의 내용을 합한것이 프로그램 코드에 해당이 된다.
      • 현대 컴퓨터와 아주 유사한 방식을 갖고 있다.
    • 주요 부품들이 기계장치였기 때문에 속도가 느릴 수 밖에 없었다.
    • 진공관이 발명이 되면서 단점이 개선이 되었다.

주요 컴퓨터 부품들의 발전

  • 릴레이 (진공관 이전)
    • 기계식 스위치를 얘기한다.
    • 마모가 일어나고 수명이 짧다.
    • 개폐를 할때 채터링이라는 현상이 일어난다. (스위치를 눌렀다가 떼면 스위치가 물리적으로 떨리기 때문에 진동에 의해서 여러번 눌러진것같은 현상)
  • 진공관
    • 진공 속에서 전자의 움직임을 통해서 제어를 했다.
    • 움직이는 부분이 없기 때문에 마모도 적고, 전환 속도도 굉장히 빨랐다.
    • 잘 부숴지고 고장이 잘 났고, 고가였다.
  • 트랜지스터
    • 트랜스퍼 + 래지스터의 합성어 (저항기)
    • 반도체이다.
    • 반극성 트랜지스터와 쌍극성 트랜지스터로 나뉜다.
    • 쌍극성 트랜지스터가 우리가 일반적으로 말하는 트랜지스터이다.
    • 주로 실리콘을 재료로 한다.

폰노이만 구조

  • 메모리 영역이 프로그램과 데이터가 나뉘어져 있지 않다.
  • 주소버스 데이터버스를 메모리가 공유하게 된다.
  • 하버드 구조와 달리 병합이 일어난다.
  • 폰노이만 구조는 만들기가 단순하기 떄문에 많이 채택되고있다.

 

마무리

  • 시스템버스가 단순히 하나로 이뤄진게 아닌 세분화되어 있다는것을 알게됐습니다.
    • 중요하게 생각해봐야 할 부분은 단방향으로 통신하는 주소버스와 양방향으로 통신하는 데이터버스, 컨트롤버스의 차이점 같습니다.
    • 약간 어떻게 생각을 해보니 MVC 패턴과 비슷한....? 것 같습니다. 비슷하다고 말하지 말고 이해를 해야되는 상황에 MVC에 대입해서 생각해보면 이해가 좀 더 빠르지 않을까 하는 생각이 듭니다.
  • 강의가 살짝 불친절한것 같다는 생각이 듭니다.
  • 폰노이만 구조에 대해서 제대로 설명을 안하고 넘어가셨습니다.
  • 따로 검색해서 정리를 하라는 뜻으로 받아들여야겠습니다. 
  • 단순히 타이핑을 할때도 한번의 통신을 하는게 아닌 상태 레지스터를 통해 확인을 하고 다시 데이터 레지스터에 접근해 내용을 읽어서 데이터 버스로 전달이 되는것 같습니다.
  Comments,     Trackbacks
컴퓨터 시스템의 기본 구성과 정보의 표현과 저장

컴퓨터 시스템의 기본 구성

  • 하드웨어
    • 물리적인 실체가 있는 장비, 부품
  • 시스템 소프트웨어
    • OS를 포함하는 부트로더, 장치드라이버, 쉘 같은 것들을 얘기함
  • 응용 소프트웨어
    • 애플리케이션

하드웨어

  • 입력, 연산, 제어, 기억, 출력 기능을 구현한다.
  • 변경이 어렵다는 의미가 될 수 있다.

컴퓨터 하드웨어의 주요 구성 요소

  • 디스플레이 (모니터 / 출력장치)
  • 메인보드
    • 머더보드라고도 칭한다. (주요 칩들과 메모리 모듈, I/O장치 인터페이스를 위해서 슬롯이 장착된 기판을 의미한다.)
  • CPU
    • 가장 중요한 구성 요소이다.
  • 주기억장치 모듈
    • 램 (메인메모리 모듈 이라고도 부른다.)
  • 확장보드
    • 사운드카드, 랜카드, 등 기능추가를 위해서 장착하는 보드들을 확장보드라고 칭한다.
    • 그래픽카드 또한 확장보드에 장착된다
  • 전원 공급 장치
  • 광 저장 장치
    • ODD라고도 한다.
  • 하드디스크, SSD 등
  • 키보드, 마우스와 같은 입력장치

소프트웨어

  • 특정 작업을 수행하기 위해서 하드웨어에 의해서 저장되고 실행되는 명령어
  • 정보처리의 종류와 수행시간을 지정해주는 명령들의 집합이라고도 한다.
  • 시스템 소프트웨어
    • 컴퓨터를 유지/관리하는 데 사용되는 소프트웨어를 얘기한다. (운영체제, 런타임환경, 펌웨어 등등)
    • 로우레벨 언어로 작성되는 경우가 많다.
  • 응용 소프트웨어
    • 사용하는 목적에 따라서 제작된 기능적인 프로그램을 칭한다.
    • 고급언어로 작성되어있는 경우가 많다.
  • 하드웨어에 의존적이다.

컴퓨터의 기본 구조

  • 가장 중요한 3요소
    • CPU / Memory / IO Devices이다
      • CPU : 중앙처리 장치, 프로그램의 실행과 데이터 처리를 담당하는 핵심 요소이다. (프로세서라고도 불린다.)
        • 입출력 장치로부터 정보를 받아오고 처리한 결과를 내보내는 역할을 한다.
        • 메인보드 내에서도 가장 큰 칩이다.
        • 산술 논리 연산장치 *ALU)와 컨트롤유닛/, 레지스터 (임시메모리)로 구성이 되어있다.
      • 기억 장치 : 저장장치라고도 한다. CPU에서 처리한 결과를 보관하는 용도로 주로 사용된다.
        • 1차 메모리, 2차 메모리로 나뉜다.
        • 프로그램 코드라던가 데이터를 저장하는 역할을 한다.
        • 1차 메모리는 휘발성인 경우가 많다. (램) 휘발성 → 전력공급이 중단되는 경우에 데이터가 유실되는 장치를 뜻한다. 빠른 IO를 특징으로 한다.
        • 2차 메모리는 보조저장 장치를 얘기한다. 비휘발성이다. (영구 데이터 보존을 위해 사용되는 경우가 많다. 디스크나 테이프)
      • 입출력 장치 : 사용자와 컴퓨터 간의 상호작용을 위한 장치이다.
    • 이 3가지가 시스템 버스로 통신하는 구조로 이루어져 있다.

정보의 표현과 저장

  • 정보의 종류
    • 프로그램 코드
    • 데이터
    • 2진수 비트들의 조합으로 표현이 된다.

프로그램 코드

  • 고급 언어 프로그램 (영문자와 숫자로 이루어져 있어서 사람들이 이해하기는 쉽지만 컴퓨터는 이해할 수 없다. 그래서 컴파일러가 존재한다.)
    • 컴파일러 → 고급 언어들을 컴퓨터 하드웨어가 이해할 수 있는 언어로 번역하는 일을 담당한다.
      • 언어 번역 프로그램
      • 해석기 번역기 정도로 이해하면 쉽다.
      • 원래 문서를 소스 코드, 출력된 문서를 타깃 코드라고 칭한다.
      • 소스 코드를 타겟 코드로 옮기는 과정을 컴파일이라고 한다. (다른 말로 빌드라고도 얘기한다.)
      • 일반적으로 인터프리터를 거치는 것보다 컴파일된 파일 실행이 훨씬 빠르다.
      • 네이티브 컴파일러와 크로스 컴파일러로 구분이 된다.
        • 구분이 되는 기준은 컴파일러가 실행되는 컴퓨터 또는 운영체제가 같은가 다른가에 따라서 나뉘게 된다.
        • 같은 경우 → 네이티브 / 다른 경우 → 크로스 컴파일러
        • 크로스컴파일러가 많이 쓰이고 있다.
    • 고급언어로 작성된 프로그램을 실행하는 방법은 두 가지가 있다.
      • 첫 번째는 컴파일을 하는 방법이다.
      • 두 번째는 인터프리터를 사용하는 방법이다.
        • 소스코드를 한줄한줄 읽어서 그 즉시 결과를 출력하는 방식이다. (베이식 같은 언어)
      • 프로그램 크기가 아주 큰 경우에 인터프리터로 더 빨리 실행할 수도 있다.
      • 컴파일 과정을 안 거치기 때문에 교육 목적에서 바로 결과를 확인할 수 있다.
  • 어셈블리 프로그램 로우레벨 랭귀지
    • 언어 사항의 차이를 해결하기 위해서 존재하는 어셈블리어로 작성된 프로그램을 뜻한다.
  • 기계어 로우레벨 랭귀지

고급언어에서 기계어 프로그램으로 번역되는 과정

  • 고급 언어 프로그램이 컴퓨터에서 처리가 되려면 어셈블리 프로그램으로 번역이 되어야 한다.
  • 그리고 해당 CPU를 위한 기계어 프로그램으로 번역이 되어야 한다.
  • 고급 언어 프로그램 ⇒ Z = X + Y → 기억장치에 저장되어 있는 데이터 X와 Y를 더하고 결괏값을 기억장치의 Z 번지에 저장해라 라는 뜻
    • 어셈블리 프로그램 ⇒ LOAD A, X → 기억장치의 X번지에 있는 내용을 읽어 레지스터 A에 로드해라
    • ADD A, Y → 기억장치의 Y번지에 있는 내용을 읽어서 레지스터 A에 적재된 값과 더하고 결과를 레지스터 A에 적재해라
    • STOR Z, A → 레지스터 A의 내용을 기억장치의 Z번지에 저장하라는 명령이다.
  • 고급언어 프로그램 → 어셈블리 프로그램으로 번역이 되면서 3줄로 번역이 되었다.
  • 어셈블리 프로그램 → 기계어 프로그램
    • LOAD A, X ⇒ 00100101
    • ADD A, Y ⇒ 10000110
    • STOR Z, A ⇒ 01000111

명령어 형식

  • 명령어의 비트 수와 용도 및 필드 구성 방법을 지정해주는 형식이다.
  • 기계어 필드가 두 개로 구성된 것으로 가정을 한다면
  • 00100101 → 연산코드 001 , 오퍼랜드 00101
  • 연산코드 필드
    • CPU가 수행할 연산을 지정한다.
    • 레지스터 A에 저장해라 라는 명령어를 기계어로 표현한 것이다. ⇒ 001
    • 비트가 3개라면 2^3 이기 때문에 8가지의 연산 방법을 가질 수 있다.
  • 오퍼랜드 필드
    • 명령어 실행에 필요한 데이터가 저장된 주소이다.
    • 비트가 5개라면 2^5 , 기억장치의 주소를 32개 가질 수 있다는 뜻이다.

마무리

  •  컴퓨터의 기본 구성에 대해서 공부해 보았습니다.
  • 하드웨어, 시스템 소프트웨어, 응용 소프트웨어 이렇게 크게 3개로 분류할 수 있습니다.
    • 하드웨어는 말 그대로 딱딱한 부품, 고치기 힘든 부품으로 CPU 메인보드 입출력장치 등등을 뜻합니다.
    • 시스템 소프트웨어는 하드웨어에 의존적인 시스템을 구동시키기 위한 프로그램 등을 칭합니다.
      • 명령들의 집합이라고도 합니다.
    • 응용 소프트웨어는 보통 평소에 사용하는 프로그램 같은 것이라고 생각하면 될 것 같습니다.
  • 하드웨어는 단순히 CPU가 가장 큰 역할을 하고 메모리가 부수적인 역할, 그리고 해당 데이터들의 입출력을 담당하는 입출력 장치로 나누면 될 것 같습니다.
  • 시스템 버스로 통신하는 구조로 이루어져 있다고 합니다. 
    • 하드웨어 부품 하나하나가 각각의 장치와 서로 협력을 하여 동작하는 것 같습니다.
    • 시스템버스가 그 협력관계를 유지시켜준다고 보면 될 것 같습니다.
  • 어셈블리어와 기계어에 대해서 살짝 개념을 짚었으나, 아직 이해는 되지 않습니다.
  • 어떻게 해서 연산코드 필드와 오퍼랜드 필드를 구별할 수 있는지, 생성할 수 있는지에 대해서 배우지 못해서 나중에 정리가 한번 더 필요할 것 같습니다.

 

  Comments,     Trackbacks
22-12-26 TIL

오늘 진행한 것들 🤔

  • 동적계획법 / 분할정복 정리 (분할정복 응용한 병합정렬,퀵정렬 정리)
 

다이나믹 프로그래밍 / 분할정복 (을 활용한 병합정렬/퀵정렬)

동적 계획법 / 분할 정복 동적 계획법 (다이내믹 프로그래밍) 입력 크기가 작은 부분 문제들을 해결한 후 메모이제이션 기법을 사용해서 (미리 결괏값을 저장하여) 문제를 푸는 것 상향직 접근법

codinghentai.tistory.com

  • 분할정복/재귀용법 알고리즘 풀이
 

백준 2447번 별 찍기 - 10 (자바) 풀이

시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 59667 32112 24013 53.832% 문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각

codinghentai.tistory.com

 

백준 17829번 222-풀링 (자바) 풀이

시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 2019 1447 1157 74.501% 문제 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Con

codinghentai.tistory.com

 

백준 1992번 쿼드트리 (자바) 풀이

시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 35339 21993 17231 61.423% 문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과

codinghentai.tistory.com

 

백준 1780번 종이의 개수 (자바) 풀이

시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 34215 20278 15221 58.515% 문제 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행

codinghentai.tistory.com

 

백준 2630번 색종이 만들기 (자바) 풀이

시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 28779 19535 15790 68.832% 문제 아래 과 같이 여러 개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은

codinghentai.tistory.com

  • 테스트코드 노하우 정리
 

내가 기억하기 쉬우라고 작성한 단위테스트

단위테스트는 어떻게 진행될까? 사람마다 다를 수 있으나 (?) 기본적으론 gwt (given & when & then)으로 진행된다. Given ⇒ 어떠한 상황이 주어진다. When ⇒ 어떠한 행동을 한다면 Then ⇒ 어떠한 행동이

codinghentai.tistory.com

  • 실시간 강의 데이터베이스 수강
    • 각종 실습문제 풀이 (join 과 서브쿼리 활용)

오늘의 배운 점 🤔

  • 다이나믹 프로그래밍과 분할정복에 대해서 배웠습니다.
    • 오늘은 뭔가 분할정복 문제를 풀이해보고 싶어서 알고리즘을 5문제나 풀었습니다.
    • 모든 문제를 완벽하게 혼자 힘으로 풀이하지 못했습니다.
      • 재귀용법과 분할정복을 배운지 얼마 되지도 않았는데 어떻게 저 혼자 풀죠? 귀신같이 구현법을 모르겠을때 풀이를 참고했습니다.
      • 하지만 기본적인 로직은 제가 생각했던것과 거의 비슷했었습니다.
      • 처음부터 잘하길 바라면 안되겠습니다. 오히려 오늘같이 풀이하는게 더 이해가 잘되는것 같았습니다.
      • 알고리즘으로 문제를 잘 푸느냐도 중요하지만, 결국 코딩테스트를 준비하는 과정이기때문에 실제로 해당 알고리즘을 실무에서 써먹을 수 있으려면 이해도가 높아야한다고 생각하는데, 급하게 하면 안되겠다는 생각이 들었습니다.
    • 보통 분할정복 문제에서 막혔던 부분은 재귀호출을 어느 부분에서 해야할지가 가장 헷갈렸던것 같습니다.
      • 보통은 쪼개는 부분에서 호출하고, 브레이크 포인트는 더이상 쪼갤 수 없는 부분에서 걸어주면 되는걸 느꼈습니다.
      • 알고리즘 문제도 한마디 한마디 문장을 이해하듯이 풀이하면 더 쉽게 다가오는것 같습니다.
  • 데이터베이스 실습문제들을 풀었습니다.
    • 실시간 강의에서 저번주에 배웠던 join 에 이어서 subquery 를 이용하여 원하는 데이터를 가져올 수 있도록 실습문제들을 풀이하였습니다.
      • 보통 어려워지기 시작하는 부분은 테이블들이 복잡하게 얽히기 시작할때 입니다. 조인에 대한 순서보다는 원하는 데이터를 어떻게 조인해야지 한번의 쿼리실행으로 가져올 수 있을지가 관건이었던거 같습니다.
      • inner join 과 outer join 에 대한 차이를 직전 강의때 정리했었는데, 오늘 문제가 등장했었습니다.
        • 바로 두 테이블을 조인했을때, 값이 null인 로우의 갯수를 가져오는 문제였는데, right 조인을 사용하여 풀이하라고 되어있길래 right outer join 으로 조인해 where 로 가져오도록 했더니 쉽게 풀렸습니다.
      • 대체적으로 서브쿼리를 사용해 가져오는것보단 join을 사용해 가져오는것이 머리로도 잘 그려지고 이해가 잘되는것 같습니다.
      • 단순히 각각 겹치는 컬럼을 inner join 으로 조인 후 원하는 조건에 대한 데이터를 가져오는 문제들이 많았습니다.
        • join문에 대한 반복적인 쿼리문 작성은 코파일럿이 도와주긴 했지만, 해당 로직에 대한 구현은 제 머리로 했으나, 강사님께서 어려운 문제라고 극찬을 해주셨습니다.. 기분이 좋았습니다 :D

 

내일 목표 🤔

  • 동적계획법 알고리즘 문제 풀이
  • 새 토이프로젝트 설계
  • 실시간 강의 컴퓨터구조 수강
  • 그룹스터디 인사이트 공유 후 정리

'TIL' 카테고리의 다른 글

22-12-29 TIL  (0) 2022.12.29
22-12-28 TIL  (0) 2022.12.28
22-12-22 TIL  (0) 2022.12.22
22-12-21 TIL  (0) 2022.12.21
22-12-20 TIL  (0) 2022.12.20
  Comments,     Trackbacks
백준 2447번 별 찍기 - 10 (자바) 풀이
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB 59667 32112 24013 53.832%

문제

재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다.

크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다.

***
* *
***

N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다.

입력

첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.

출력

첫째 줄부터 N번째 줄까지 별을 출력한다.

예제 입력 1 복사

27

예제 출력 1 복사

***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************
*********         *********
* ** ** *         * ** ** *
*********         *********
***   ***         ***   ***
* *   * *         * *   * *
***   ***         ***   ***
*********         *********
* ** ** *         * ** ** *
*********         *********
***************************
* ** ** ** ** ** ** ** ** *
***************************
***   ******   ******   ***
* *   * ** *   * ** *   * *
***   ******   ******   ***
***************************
* ** ** ** ** ** ** ** ** *
***************************

풀이

일단 해당 문제가 어떠한 패턴으로 진행되는지를 먼저 이해하면 된다.

  • 가운데를 제외한 모든 칸에 *을 찍어준다.

예제 출력을 보면 패턴이 다 똑같다는것을 알 수 있다.

 

저 하나의 프린트 

***
* *
***

가 몇개가 반복되어도 똑같이 (1,1) 에는 공백이 들어가게 된다.

 

해당 부분을 인지한 상태로 풀이하면 된다.

 

이 문제도 마찬가지로 분할정복과 재귀용법을 활용하여 풀이하는 문제이므로, 브레이크 포인트를 정한다.

단순하다 '더 이상 쪼갤 수 없을 때' 를 브레이크 포인트로 두면 된다.

 

모든 데이터를 null 로 두고 별을 찍어나가는것 대신 미리 공백으로 채워둔 후 (1,1) 이 아닐때 별을 찍어주면 된다.

 

package baekjoon.a2447;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class a2447 {
    public static char[][] arr;
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        arr= new char[N][N];
        for(int i=0; i<N;i++){
            Arrays.fill(arr[i],' ');
        }
        func(0,0,N);
        for(int i=0; i<N; i++){
            for(int j=0;j<N;j++){
                sb.append(arr[i][j]);
            }
           sb.append("\n");
        }
        System.out.println(sb);

    }
    public static void func(int row,int col, int N){
        if(N==1){
            arr[row][col]='*';
            return;
        }
        N = N/3;
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                if(i ==1 && j==1){
                    continue;
                }else{
                    func(row+(i*N),col+(j*N),N);
                }
            }
        }

    }

}

 

(1,1) 일때는 별을 찍지 않고 패스하기때문에 continue 를 해주면 된다.

  Comments,     Trackbacks
백준 17829번 222-풀링 (자바) 풀이
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB 2019 1447 1157 74.501%

문제

조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다.

다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다

  1. 행렬을 2×2 정사각형으로 나눈다.
  2. 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1 라 했을 때, 원소 a2를 뜻한다.
  3. 2번 과정에 의해 행렬의 크기가 줄어들게 된다.

종욱이는 N×N 행렬에 222-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지 궁금해한다.

랩실 활동에 치여 삶이 사라진 종욱이를 애도하며 종욱이의 궁금증을 대신 해결해주자.

입력

첫째 줄에 N(2 ≤ N ≤ 1024)이 주어진다. N은 항상 2의 거듭제곱 꼴이다. (N=2K, 1 ≤ K ≤ 10)

다음 N개의 줄마다 각 행의 원소 N개가 차례대로 주어진다. 행렬의 모든 성분은 -10,000 이상 10,000 이하의 정수이다. 

출력

마지막에 남은 수를 출력한다.

예제 입력 1 복사

4
-6 -8 7 -4
-5 -5 14 11
11 11 -1 -1
4 9 -2 -4

예제 출력 1 복사

11

예제 입력 2 복사

8
-1 2 14 7 4 -5 8 9
10 6 23 2 -1 -1 7 11
9 3 5 -2 4 4 6 6
7 15 0 8 21 20 6 6
19 8 12 -8 4 5 2 9
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24

예제 출력 2 복사

17

 

 

풀이

해당 문제는 재귀용법, 분할정복을 활용하여 풀이하면 된다.

 

마찬가지로 브레이크 포인트를 어디서 잡느냐가 중요하다.

해당 문제는 2X2 배열이 끝이고 그 배열에서 2번쨰로 가장 큰 수를 반환해야하기 때문에

배열의 크기가 N*N 즉 N=2 일때 반환하도록 하면 된다.

 

다른 문제들과 마찬가지로 상하좌우로 4등분 하는식으로 쪼개기 때문에 

브레이크 포인트에서 크기가 4인 배열을 만들고 정렬 후 2번째로 큰 값 반환

 

그리고 각 파트별로 (상하좌우) 2번쨰로 큰 값을 구한 후 마지막으로 2번째로 큰 값을 구하는식으로 전개를 하면 된다.

 

      if(N==2){
            int count=0;
            int[] funcArr= new int[4];
            for(int i=row ; i<row+N;i++){
                for(int j=col ; j<col+N; j++){
                    funcArr[count] = arr[i][j];
                    count++;
                }
            }
            Arrays.sort(funcArr);
            return funcArr[funcArr.length-2];
        }

브레이크 포인트를 이렇게 잡아준다.

 

    public static int func(int row,int col,int N){
        if(N==2){
            int count=0;
            int[] funcArr= new int[4];
            for(int i=row ; i<row+N;i++){
                for(int j=col ; j<col+N; j++){
                    funcArr[count] = arr[i][j];
                    count++;
                }
            }
            Arrays.sort(funcArr);
            return funcArr[funcArr.length-2];
        }
        N = N/2;
        int[] funcArr = new int[4];
        int count =0;
        for(int i=0; i<2;i++){
            for(int j=0; j<2;j++){
                funcArr[count] = func(row+(i*N),col+(j*N),N);
                count++;
            }
        }
        Arrays.sort(funcArr);
        return funcArr[funcArr.length-2];
    }

함수를 이렇게 호출해주면 된다 .

 

package baekjoon.a17829;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.Arrays;
import java.util.StringTokenizer;

public class a17829 {
    public static int[][] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N][N];
        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(func(0,0,N));
    }

    public static int func(int row,int col,int N){
        if(N==2){
            int count=0;
            int[] funcArr= new int[4];
            for(int i=row ; i<row+N;i++){
                for(int j=col ; j<col+N; j++){
                    funcArr[count] = arr[i][j];
                    count++;
                }
            }
            Arrays.sort(funcArr);
            return funcArr[funcArr.length-2];
        }
        N = N/2;
        int[] funcArr = new int[4];
        int count =0;
        for(int i=0; i<2;i++){
            for(int j=0; j<2;j++){
                funcArr[count] = func(row+(i*N),col+(j*N),N);
                count++;
            }
        }
        Arrays.sort(funcArr);
        return funcArr[funcArr.length-2];
    }
}
  Comments,     Trackbacks
내가 기억하기 쉬우라고 작성한 단위테스트

단위테스트는 어떻게 진행될까?

  • 사람마다 다를 수 있으나 (?) 기본적으론 gwt (given & when & then)으로 진행된다.
    • Given ⇒ 어떠한 상황이 주어진다.
    • When ⇒ 어떠한 행동을 한다면
    • Then ⇒ 어떠한 행동이 돌아온다.
  • 단순히 이렇게 기억하면 쉽다.

사용되는 라이브러리

  • 보통 테스트는 비즈니스 로직 단위테스트, 컨트롤러 단위테스트, 리포지토리 단위테스트 이렇게 이뤄지는것 같다.
    • 비즈니스 로직 단위테스트에는 MockitoExtension을 사용한다.
    • 컨틀롤러 단위테스트에는 SpringBootTest 어노테이션을 달고 MockMvc 를 객체로 사용한다.
    • 리포지토리 단위테스트에는 DataJPATest 어노테이션을 달고 테스트한다.
  • 단순히 하나하나가 어떠한 행동들을 지원하는지는 나중에 알아보고, 어떻게 테스트해야지 성공적인 결과를 가져올 수 있는지 일단 행동해보자.

비즈니스 로직 단위테스트

테스트 클래스 생성

단순히 테스트 폴더에 테스트 클래스를 생성한다.

spring boot starter test 디펜던시를 추가하면 자동으로 junit 라이브러리까지 사용이 가능하다.

@DisplayName("비즈니스 로직 - 게시글")
@ExtendWith(MockitoExtension.class)
class ArticleServiceTest {

테스트를 원하는 클래스에 MockitoExtension 을 상속받아주고 어떠한 테스트를 진행할 것인지 @DisplayName으로 명시해 준다.

@InjectMocks private ArticleService sut;
@Mock private ArticleRepository articleRepository;

핵심이 되는 서비스클래스를 @InjectMocks 어노테이션을 사용하여 필드변수로 선언해 준다.

sut는 System Under Test 테스트 대상 시스템을 뜻한다.

그리고 해당 서비스 클래스에 주입되어야 하는 Repository 들을 @Mock 어노테이션을 사용해 주입시켜 준다.

(주축이 되는 객체에 주입되어야 하는 객체들을 하나라도 주입시키지 않으면 오류가 발생한다.)

테스트에 사용되는 메서드

  • given → 테스트가 진행되는 목업 객체가 가 어떠한 메서드를 호출할 때의 결과를 가정할 수 있다.
    • 리턴값이 있다면 목업 객체를, 예외가 발생해야 한다면 예외를 던져주는 등 상황을 지정할 수 있다.
      • 보통 테스트 대상 시스템의 비즈니스 로직 속 호출되는 메서드들에 대한 리턴값을 지정하는데 쓰인다.
  • when & then → 해당 비즈니스 로직을 호출했을 시에 어떠한 결과가 나와야 하는지를 명시한다.
    • when에는 예외가 발생되어야 하는 상황이나 메서드를 호출한다.
    • then 에는 AssertJ 라이브러리를 활용해 assertThat 메서드로 검증을 진행하거나 then() 메소드로 어떠한 메서드를 호출을 했는지 확인할 수 있다.

비즈니스 로직 단위테스트 코드 작성

  • 단위테스트 메서드의 네이밍은 given 주어진 것_when 어떠한 행동을 할 때_then 어떠한 것을 하거나 반납한다. 이런 느낌으로 작성해도 좋고, @DisplayName 어노테이션을 사용하여 따로 상황만 명시해줘도 된다.
  • 어떠한 행동을 했을 때 대상이 되는 엔티티에 변경사항이 존재하는지, 혹은 엔티티매니저가 어떠한 행동을 실행했는지 에 대한 상황을 가정 후 테스트를 진행할 수 있다.
  • 예외가 발생할 때는 Throwable 클래스의 정적 메서드인 catchThrowable()를 이용하여 람다식으로 예외를 캐치해 준다.
@Test
    @DisplayName("댓글 단건 조회시 없는 댓글을 조회하면 예외가 발생한다$")
    void givenNotExistArticleCommentId_whenGetAnArticleComment_thenThrowsException() {
        //given
        given(articleCommentRepository.findById(any())).willReturn(Optional.empty());

        //when
        Throwable throwable = catchThrowable(() -> sut.getArticleComment(1L));

        //then
        then(articleCommentRepository).should().findById(any());
        assertThat(throwable).isInstanceOf(EntityNotFoundException.class);
    }
  • 이때의 생각해볼 수 있는 상황들은 무엇이 있을까? 바로 단위테스트를 진행하는 목업 객체의 역할분담이다.
    • 사실 data repository 테스트를 따로 진행한 후 비즈니스 로직 테스트는 단순히 then에 해당 비즈니스 로직이 호출되었는지 를 확인할 수 있다.
    • 하지만 위에 작성해둔 코드로 실행시켜도 문제는 없다. 단순히 해당 계층의 테스트인데 다른 계층까지 점령해도 되느냐의 차이인 것 같다.
    • 더 세분화한다면 Data Repository 테스트 / 비즈니스 로직 테스트 / MVC테스트 이렇게 세분화하여 진행할 수 있지만 결국엔 비즈니스 로직에서는 해당 비즈니스 로직을 호출할 때 모든 repository 메서드를 호출할 것이며, MVC 테스트를 진행할 때도 리퀘스트를 보내면 컨트롤러가 비즈니스 로직을 호출하게 될 것이다.
      • 이에 대한 고민을 할 필요가 있으나, 현재 상황에서는 repository 자체에 여러 커스텀 메서드 (쿼리 dsl을 활용하거나 jpql을 활용해 직접 쿼리문으로 조회하는 메서드)가 존재하지 않기 때문에 비즈니스 로직에서 데이터계층까지 테스트하는 식으로 작성했다.

예외가 발생하지 않는 정상적인 상황에서의 테스트

@Test
    @DisplayName("getArticleCommet() - 댓글 단건 조회")
    void givenArticleCommentId_whenGetAnArticleComment_thenGetsArticleComment() {
        //given
        ArticleComment articleComment = createArticleComment(createArticle(createUserAccount()),createUserAccount());
        given(articleCommentRepository.findById(any())).willReturn(Optional.of(articleComment));

        //when
        ArticleComment.ArticleCommentDto articleCommentDto = sut.getArticleComment(articleComment.getId());

        //then
        then(articleCommentRepository).should().findById(any());
        assertThat(articleCommentDto).isNotNull();
    }
  • getArticleComment 메서드의 내용물로는 articleCommentRepository 가 findById로 댓글을 조회한 후 존재한다면 해당 댓글을, 존재하지 않는다면 EntityNotFoundException을 발생시키도록 되어있다.
  • given으로 상황을 만들어준다. 모키토는 여러 가지 메서드를 제공해주는데, 그중 any() 는 말그대로 어떠한 상황에서든지 willReturn() 메소드의 매개값을 리턴해준다.
  • when은 해당 시점을 뜻한다. 어떠한 메소드를 호출할 때 then에서 검증을 진행한다.
  • then에서는 assertThat() 메서드로 어떠한 엔티티를 영속시켰을 때 해당 레포지토리에 저장된 데이터의 수가 +1 이 되었는지 , 혹은 해당 엔티티 객체의 멤버변수에 변동사항이 있는지 까지 테스트가 가능하다.

이렇게만 작성하면 성공적인 테스트 결과를 얻을 수 있다.

 

이렇게 여러 상황을 지정할 수 있다.


컨트롤러 단위테스트

테스트 클래스 생성

컨트롤러 테스트도 마찬가지로 새 패키지를 생성해 테스트가 진행되는 클래스의 이름뒤에 test를 붙여서 클래스를 새로 생성한다.

여기에 쓰이는 어노테이션은

  • @AutoConfigureMockMvc
  • @SpringBootTest
  • *@Import*(*SecurityConfig*. class)

이렇게 어노테이션을 달아주면 된다.

스프링 시큐리티를 사용 중에 컨트롤러 테스트를 진행하면 시큐리티 설정도 같이 가져와야지 허튼짓을 하지 않고 테스트를 마무리 지을 수 있다.

private final MockMvc mvc;
    @MockBean
    private final SaveFileService saveFileService;
    private final ObjectMapper objectMapper;

    public SaveFileControllerTest(@Autowired MockMvc mvc, @Autowired SaveFileService saveFileService, @Autowired ObjectMapper objectMapper) {
        this.mvc = mvc;
        this.saveFileService = saveFileService;
        this.objectMapper = objectMapper;
    }

이렇게 필드변수로 MockMvc 객체를 주입해 주고, 본인의 입맛에 맞게 주입할 객체를 선언해주면 된다.

생성자에 꼭 Autowired 어노테이션을 달아주자.. 여기에 달아놓지 않으면 오류가 발생한다..

테스트에 사용되는 메서드

  • given → 비즈니스 로직 테스트와 마찬가지로 뷰에서 요청이 들어왔을 때 호출되는 메서드에 대한 리턴값이나 상황을 지정해줄 수 있다.
  • perform
    • get → GET 요청을 할 때 사용한다.
    • post → POST 요청을 할 때 사용한다. 위에 있는 objectMapper 객체로 dto를 json 형태로 변환해서 매개값으로 전달할 수 있다.
      • contentType → 데이터를 어떠한 타입으로 전송하는지를 명시한다.
      • cotent → 전달하는 데이터를 목업 데이터로 전송한다.
    • put → PUT 요청을 할 때 사용한다. 제공하는 메서드는 post와 같다.
    • delete → DELETE 요청을 할 때 사용한다.
      • 마찬가지로 delete 요청을 보내기 위해 전달되어야 하는 데이터들을 contentType과 content로 정의해 전달할 수 있다.
    • andExpect / andDo → 해당 요청을 보내면 어떠한 응답이 와야 하는지를 명시한다.
      • view → 어떠한 페이지로 이동이 된다든가.. 하는지를 명시한다.
      • model → 어떠한 모델이 attribute 되었는지를 명시한다.
  • 해당 메서드만 적절히 잘 사용하면 모든 테스트를 실패 없이 끝낼 수 있다.

컨트롤러 테스트 코드 작성

이전에 신경 써야 하는 부분이 있다.

  • 스프링 시큐리티를 적용한 프로젝트인데, 시큐리티 콘텍스트에 담긴 인증정보를 가져오는 메서드가 존재한다거나, authenticatedPrincipal 어노테이션을 사용하는 메소드가 존재할 때의 상황이다.
  • 이때를 대비해 @BeforeEach 어노테이션을 사용한 메서드를 선언해 각 테스트메서드 별로 호출 전 상황을 잡아줄 수 있다.
    • 계정을 생성해 놓는다던지, 글을 등록해놓는다던지 할 수 있다.
  • 상황을 잡아줬다면 @WithUserDetails 같은 @With~~ 어노테이션을 사용하여 해당 문제를 해결할 수 있다.
  • 만약 커스텀 필터를 구현하여 토큰을 사용하거나 하는 상황에서는 따로 어노테이션과 그에 대한 설정 클래스를 생성해 구현할 수 있다.
    • Spring Securit Test 디펜던시를 추가해야 사용이 가능하니 꼭 추가하자.
@DisplayName("[view][GET] 게시글 페이지 ")
    @Test
    public void givenNothing_whenRequestingArticlesView_thenReturnsArticlesView() throws Exception {
        //given
        given(articleService.searchArticles(eq(null), eq(null), any(Pageable.class))).willReturn(Page.empty());
        //when & then
        mvc.perform(get("/articles")).andExpect(status().isOk())
                .andExpect(content().contentTypeCompatibleWith(MediaType.TEXT_HTML))
                .andExpect(view().name("articles/index"))
                .andExpect(model().attributeExists("articles"));
        then(articleService).should().searchArticles(eq(null), eq(null), any(Pageable.class));
    }
  • 기본적인 GET 요청을 보냈을 때의 테스트코드이다.
  • @DisplayName에 마찬가지로 테스트 상황을 명시한다.
    • 이때 의문점은 메서드의 이름에 given 에 해당 메소드 필드 속 given 메소드의 내용을 명시해야 하는지, 아니면 실제 상황을 명시해야 하는지를 아직 정확히 이해하지 못했다.
  • perform() 메서드를 호출해 어떠한 url로 어떠한 요청을 보냈을 때, 어떠한 응답이 올 때 어떠한 것을 반환하는지를 명시해 준다.
  • 본인은 then에 해당 url로 요청을 보냈을 때 어떠한 비즈니스 로직이 호출되는지를 명시해 주었다.
    • 해당 부분도 솔직히 정답은 없을 거라 본다.. 각자 프로젝트를 진행할 때 정해둔 규칙에 따라서 작성하면 될 것 같다.
@DisplayName("[view][POST] 게시글 등록 ")
    @Test
    @WithUserDetails("test")
    public void givenArticleInfo_whenSavingArticle_thenSavesArticle() throws Exception {
        //given
        Article.ArticleRequest articleRequest = Article.ArticleRequest.builder()
                .title("haha421")
                .content("haha412")
                .fileIds("")
                .build();
        Article article = createArticle(createUserAccount());
        given(saveFileService.getFileDtosFromRequestsFileIds(any())).willReturn(new HashSet<>());
        given(articleService.saveArticle(any(), any())).willReturn(Article.ArticleDto.from(article));

        //when & then
        mvc.perform(post("/articles")
                        .contentType(MediaType.APPLICATION_JSON)
                        .content(mapper.writeValueAsString(articleRequest)))
                .andExpect(status().isOk())
                .andExpect(content().contentTypeCompatibleWith(MediaType.TEXT_PLAIN));
        then(saveFileService).should().getFileDtosFromRequestsFileIds(any());
    }
  • POST / PUT 요청을 보낼 때의 테스트코드이다.
  • ObjectMapper 객체를 활용해 json으로 변환 후 전달 할 수 있다.
  • given 에는 마찬가지로 해당 url로 요청을 보냈을 때 호출되는 비즈니스 로직 속 또 다른 메서드까지 반환값을 지정해줄 수 있다.
@DisplayName("[view][DELETE] 로그인이 되어있지 않은 상태로 게시글을 삭제하면 BAD_REQUEST를 반환한다.")
    @Test
    public void givenArticleId_whenTryingToDELETEArticle_thenReturnBadRequest() throws Exception {
        Map<String, String> articleId = Map.of("articleId", "1");
        //when&then
        mvc.perform(delete("/articles").contentType(MediaType.APPLICATION_JSON).content(mapper.writeValueAsString(articleId)))
                .andExpect(status().isBadRequest());
    }
  • DELETE 요청을 보냈을 때, 예외가 발생하는 상황을 담은 테스트코드이다.

 

이렇게 각 REST API 별로 상황을 만들어서 테스트가 가능하다.

 


마무리

테스트코드 작성하는 법을 배워보진 않았지만, 어쩌다 보니 규칙을 알게 되어 제 나름대로 정리해본 글입니다.

 

제가 직접 실행해보았을 때의 각각의 역할은 어느 정도 알게 되었지만, 해당 메서드들의 원리는 아직 알지 못합니다.

 

조언해주시거나 고쳐야 할 부분이 존재한다면 댓글 꼭 달아주세요! 감사합니다.

 

  Comments,     Trackbacks
백준 1992번 쿼드트리 (자바) 풀이
시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB 35339 21993 17231 61.423%

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

예제 입력 1 복사

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

예제 출력 1 복사

((110(0101))(0010)1(0001))

 

풀이

해당 문제는 어떻게 풀이하면 될까?

문제에 주어진 힌트대로 이해하면 된다.

 

문제를 보면 4분할을 실시할때 괄호가 열리고, 종료될때 괄호가 닫히는것을 볼 수 있다.

단순히 스트링 빌더로 재귀함수 호출시에 그 직전에 "(" 를 더해주고 닫을떄 ")" 를 더해주면 된다.

 

마찬가지로 브레이크포인트는 모든 부분의 숫자가 일치할때이고, 브레이크 포인트에 해당 숫자를 스트링빌더에 append 후 return 해주면 된다.

 

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class a1992 {
    static char[][] board;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        board = new char[N][N];
        for(int i=0; i<N; i++){
            String n = br.readLine();
            for(int j=0; j<N; j++){
                board[i][j] = n.charAt(j);
            }
        }

        divide(0,0,N);
        System.out.println(sb);
    }

    public static void divide(int row,int col,int size){
        if(check(row,col,size)){
            sb.append(board[row][col]);
            return;
        }
        sb.append("(");
        int newSize= size/2;
        divide(row,col,newSize);
        divide(row,col+newSize,newSize);
        divide(row+newSize,col,newSize);
        divide(row+newSize,col+newSize,newSize);
        sb.append(")");
    }
    public static boolean check(int row,int col,int size){
        char temp = board[row][col];
        for(int i=row; i<row+size; i++){
            for(int j=col; j<col+size; j++){
                if(temp!=board[i][j]){
                    return false;
                }
            }
        }
        return true;

    }
}
  Comments,     Trackbacks
백준 1780번 종이의 개수 (자바) 풀이
시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB 34215 20278 15221 58.515%

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

  1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
  2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

예제 입력 1 복사

9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

예제 출력 1 복사

10
12
11

 

풀이

해당 문제는 바로 직전에 업로드한 2630번과 거의 같다.

전 문제에 엄청 헤맸었기 때문에 응용을 할 수 있는 문제를 찾아야겠다 하고 찾으니 바로 등장했다.

해당 문제도 단순히 문제에서 제시하는 힌트를 그대로 이해하면 된다.

  • 모든 부분의 수가 같다면 나누지 않는다.
  • 같지 않다면 9 등분한다. (종이는 보통 9의 배수가 면적으로 주어진다.)

 

이 두 조건을 두고 봤을 때, 전 문제와 다른 것은 단순히 몇 등분을 하냐 와 조건이 몇 개인가? 를 따지면 된다.

 

이 문제도 마찬가지로 좌표를 이용해서 풀이해야하기 때문에 어렵게 느껴질 수 있다.

 

하지만 한번 문제의 유형을 익힌다면 전혀 어렵지 않으니 이해가 어렵다면 자존심을 굽히고 풀이를 참고하자.

 

 

 

마찬가지로 계속 나눌거라는 힌트가 주어졌기 때문에 재귀용법이 사용될 것이다.

브레이크포인트를 먼저 잡아주자. 바로 각각 부분의 숫자가 모두 같아야 한다는 점이다.

말 그대로 기준점을 잡아 2중 반복문으로 순회하면서 데이터가 같다면 true, 아니라면 false를 반환하는 체크용 메서드를 선언하자

 

    public static boolean check(int row,int col,int size){
        int pivot = paper[row][col];
        for(int i=row; i<row+size;i++){
            for(int j=col;j<col+size;j++){
                if(paper[i][j]!=pivot){
                    return false;
                }
            }
        }
        return true;
    }

마찬가지로 배열과 카운트에 대한 변수는 모두 정적변수로 선언했다.

 

그리고 브레이크 포인트를 만들었으니 재귀함수를 만들면 된다.

 

마찬가지로 9 등분이라는 건 각 변을 3으로 나눠서 체크하는 것이기 때문에 사이즈를 3 등분해서 함수를 호출해주면 된다.

 

그런데 여기서는 9등분이라고 했으면, 메서드를 9번 호출해야 되는데 , 단순히 그냥 한 줄씩 작성해 9번 호출할까..?

 

에 대한 대답은 그러면 16등분 25등분 이러면 어떻게 하시려고..?

 

이중 반복문으로 각각 로우와 칼럼에 늘어나는 인덱스*등분 사이즈 (나눠진 사이즈)를 더해가면서 함수를 호출하도록 하면 된다.

 

마찬가지로 브레이크 포인트를 먼저 선언해주고 통과했을 때 해당 값들이 어떠한 숫자로 이루어져 있는지 (-1,0,1 중에 하나)를 체크해서 카운트를 ++해주도록 하면 된다.

 

 public static void divide(int row,int col,int size){
        if (check(row, col, size)) {
            if(paper[row][col]==-1){
                minus++;
            }else if(paper[row][col]==0){
                zero++;
            }else{
                plus++;
            }
            return;
        }
        int[] move = {0,1,2};
        int newSize= size/3;
        for(int i=0; i<3;i++){
            for(int j=0; j<3;j++){
                divide(row+(i*newSize),col+(j*newSize),newSize);
            }
        }
    }

이렇게 하면 깔끔하게 표현이 가능하다.

 

package baekjoon.a1780;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class a1780 {
    public static int minus =0;
    public static int zero =0;
    public static int plus =0;
    public static int[][] paper;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        paper = new int[N][N];
        for(int i=0; i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N;j++){
                paper[i][j]= Integer.parseInt(st.nextToken());
            }
        }
        divide(0,0,N);
        System.out.println(minus);
        System.out.println(zero);
        System.out.println(plus);
    }

    public static void divide(int row,int col,int size){
        if (check(row, col, size)) {
            if(paper[row][col]==-1){
                minus++;
            }else if(paper[row][col]==0){
                zero++;
            }else{
                plus++;
            }
            return;
        }
        int[] move = {0,1,2};
        int newSize= size/3;
        for(int i=0; i<3;i++){
            for(int j=0; j<3;j++){
                divide(row+(i*newSize),col+(j*newSize),newSize);
            }
        }
    }
    public static boolean check(int row,int col,int size){
        int pivot = paper[row][col];
        for(int i=row; i<row+size;i++){
            for(int j=col;j<col+size;j++){
                if(paper[i][j]!=pivot){
                    return false;
                }
            }
        }
        return true;
    }
}
  Comments,     Trackbacks