Jean Web Developer

면접 예상 문제 답안 정리 - 프론트엔드

브라우저의 동작 원리

브라우저가 하나의 화면을 그려내는 과정을 Critical Rendering Path 라고 한다. 주소창에 url을 입력하고 엔터를 치면 브라우저는 서버에 request를 보낸다. 서버에서는 응답으로 HTML 데이터를 내려주는데, 이를 화면으로 그리기까지 다음 단계를 거쳐 작업을 진행한다.

  1. 서버에서 응답으로 받은 HTML 데이터를 파싱한다
  2. HTML을 파싱한 결과로 DOM Tree를 만든다
  3. 파싱하는 중 CSS 파일 링크를 만나면 CSS 파일을 요청해서 받아온다
  4. CSS 파일을 읽어서 CSSOM (CSS Object Model)을 만든다
  5. DOM Tree와 CSSOM이 모두 만들어지면 이 둘을 사용해 Render Tree를 만든다
  6. Render Tree에 있는 각각의 노드들이 화면의 어디에 어떻게 위치할지를 계산하는 Layout 과정을 거쳐서
  7. 화면에 실제 픽셀을 Paint 한다.

서버에서 응답으로 받은 HTML 데이터를 파싱한다

HTML에서 DOM Tree로

브라우저는 읽어들인 HTML 바이트 데이터를 해당 파일에 지정된 인코딩에 따라 문자열로 바꿈.
바뀐 문자열을 다시 읽어, 문자열을 토큰으로 변환.
이렇게 만든 토큰을 다시 노드로 바꿈. 토큰들이 HTML 노드의 자식 노드로 넣는 식으로 변환이 이러우지기 때문에, 과정이 끝나면 Tree 모양의 DOM(Document Object Model)이 완성됨.

CSS에서 CSSOM으로

HTML을 파싱하다 CSS 링크를 만나면, CSS 파일을 요청해서 받아오게 됨.
받아온 파일은 HTML을 파싱한 것과 유사한 과정으로 Tree형태의 CSSOM으로 만들어짐.

DOM(Content) + CSSOM(Style) = Render Tree

DOM과 CSSOM을 합쳐 Render Tree를 만든다. Render Tree는 DOM Tree에 있는 것들 중 화면에 실제로 보이는 것들로만 이루어진다.
Render Object의 속성에 따라 필요한 경우 Render Layer가 만들어짐. 여기서 GPU에서 처리되는 부분이 있으면 다시 Graphic Layer로 분리됨. 다음과 같은 속성을 가졌을 때.

  • CSS 3D Transform이나 perspective 속성이 적용된 경우
  • video 또는 canvas 요소
  • CSS3 애니메이션 함수나 CSS 필터 함수를 사용하는 경우
  • 자식 요소가 레이어로 구성된 경우
  • z-index 값이 낮은 형제 요소가 레이어로 구성된 경우

Layout (reflow)

Render Tree에 있는 각각의 노드들이 화면의 어디에 위치할 지를 계산하는 Layout 과정을 거침. 여기에서 CSS box model이 쓰이며 position, width, height 등 틀과 위치에 관련된 부분이 계산됨.
브라우저를 리사이저하면 Render Tree는 그대로인 상태에서 layout 단계만 다시 거쳐 위치를 계산해서 그림.

Paint (repaint)

Render Tree의 각 노드들을 실제로 화면에 그림.

CORS

HTTP 요청은 기본적으로 Cross-Site HTTP Request가 가능하다.
그러나 script에서 생성된 request는 Same Origin Policy를 적용받기 때문에 동일 도메인, 동일 포트, 동일 프로토콜 내에서만 요쳥이 가능하다.
그러다 HTML5에서 다른 도메인 간 통신이 가능한 스펙이 추가되었는데, 그것이 바로 CORS이다.

CORS 요청의 종류

Simple/Preflight, Credential/Non-Credential의 조합으로 4가지가 존재한다.

Simple Request

아래 3가지 조건을 모두 만족하면 Simple Request

  • GET, HEAD, POST 중의 한 가지 방식을 사용해야 한다
  • POST 방식일 경우 Content-type이 아래 셋 중 하나여야 한다
    • application/x-www.-form=urlencoded
    • multipart/form-data
    • text/plain
  • 커스텀 헤더를 전송하지 말아야 한다 Simple Request는 서버에 1번 요청하고, 서버도 1번 회신하는 것으로 처리가 종료된다

Preflight Request

Simple Request 조건에 해당하지 않으면 브라우저는 Preflight 방식으로 요청.
따라서 preflight는

  • GET, HEAD, POST 외의 다른 방식으로도 요청을 보낼 수 있고
  • application/xml 처럼 다른 Content-type으로 요청을 보낼 수도 있으며
  • 커스텀 헤더도 사용할 수 있다

Request with Credential

HTTP Cookie와 HTTP Authentication 정보를 인식할 수 있게 해주는 요청

크로스 브라우징

웹 표준에 따라 개발하여 서로 다른 OS 또는 플랫폼에 대응하는 것. 웹 사이트를 서로 비슷하게 만들어 어떤 환경에서도 이상없이 작동되게 하는데 그 목적이 있다.

서버 사이드 렌더링 vs 클라이언트 사이드 렌더링

모바일의 시대가 도래하면서 모바일 웹에 대한 수요가 폭증, 새로운 웹 출력 방식인 SPA(Single Page web Application)이 등장한다.
SPA는 브라우저에 로드되고 난 뒤 페이지 전체를 서버에 요청하는 것이 아니라, 최초로 한 번 페이지를 로딩한 후부터는 데이터만 변경하여 사용할 수 있는 웹 어플리케이션이다.
서버는 단지 JSON 파일을 보내주는 역할을 하고, html을 그리는 역할을 클라이언트 측에서 자바스크립트가 수행하게 된다. 이것이 바로 클라이언트 사이드 렌더링이다.
Angular JS와 Backbone JS 같이 single page를 생성하기 쉬운 JS 프레임워크가 등장한다. 또한 클라이언트 쪽이 점점 무거워지자 view만 관리하자는 철학으로 React가 등장한다.

각 렌더링의 장단점 비교

클라이언트 사이드 렌더링은 사용자 행동에 따라 필요한 부분만 다시 읽어들인다. 때문에 서버측에서 렌더링하는 것보다 빠른 인터랙션을 기대할 수 있다.
하지만 렌더링할 때 페이지를 읽어들이는 시간, 자바스크립트를 읽어들이는 시간, 자바스크립트가 화면을 그리는 시간까지 모두 마쳐야 콘텐츠가 사용자에게 보여진다. 즉 초기 구동 속도가 느리다는 단점이 있다.
또한 검색 엔진 최적화의 문제가 존재한다. 웹 크롤러, 봇들이 자바스크립트 파일을 실행시키지 못하기 때문.
여기에 추가적으로 보안문제가 발생한다. 서버 사이드 렌더링에서는 사용자 정보를 서버 측에서 세션으로 관리를 했다. 그러나 클라이언트 측에는 쿠키말고는 정보를 저장할 공간이 마땅치 않다.

서버 사이드 렌더링은 반대이다.
유저가 처음으로 컨텐츠를 접하는 시점을 당길 수 있다. 보안, 검색 엔진 최적화 등도 장점.
문제점은 사용자와 인터랙션 하는 부분. 매번 서버에 request 요청을 통해서 해결해야 함. DOM 조작에 있어서도 요청하는 과정과 엄청난 탐색 비용이 요구됨.

참조

  • https://asfirstalways.tistory.com/244

면접 예상 문제 답안 정리 - JavaScript

https://github.com/JaeYeopHan/Interview_Question_for_Beginner 위 링크에 있는 문제에 대한 답안을 정리해보았다.

JavaScript Event Loop

자바스크립트 엔진은 크게 세 부분으로 나뉜다

Call stack, Task Queue(Event Queue), Heap 그리고 추가적으로 Event loop 가 존재하여 Task Queue에 들어가는 task를 관리한다.

Call Stack

  • 자바스크립트는 단 하나의 호출 스택을 사용한다.
  • 요청이 들어올 때마다 순차적으로 요청을 호출 스택에 담아 처리
  • 그 말은 하나의 함수가 실행되면 다른 어떤 task도 수행될 수 없다는 것

Heap

  • 동적으로 생성된 객체(인스턴스)는 힙에 할당된다.
  • 대부분 구조화되지 않는 더미같은 메모리 영역을 heap이라 표현

Task Queue (Event Queue)

  • 자바스크립트의 런타임 환경에서 처리해야 하는 Task들을 임시 저장하는 대기 큐
  • Call Stack이 비워졌을 때 먼저 대기열에 들어온 순서대로 수행됨

  • 이벤트 루프는 반복해서 call stack과 queue 사이의 작업들을 확인하고, call stack이 비워져있는 경우 queue에서 작업을 꺼내어 call stack에 넣음

참조

  • https://asfirstalways.tistory.com/362
  • http://sculove.github.io/blog/2018/01/18/javascriptflow/

Hoisting

  • hoist란? 끌어올리기
  • var 변수 선언과 함수선언문에서만 호이스팅이 일어남
    • var 변수의 할당이 아닌 선언만 호이스팅 발생
    • let/const 변수 선언과 함수표현식에서는 호이스팅 발생X
  • 변수의 정의가 그 범위에 따라 선언과 할당으로 분리됨.

Hoisting 사용 시 주의

  • 코드의 가독성과 유지 보수를 위해 가급적 호이스팅이 일어나지 않도록 한다
    • 함수와 변수를 가급적 코드 상단부에 선언
    • let/const를 사용

참조

  • https://gmlwjd9405.github.io/2019/04/22/javascript-hoisting.html

Execution Context

실행 컨텍스트

실행 가능한 코드를 형상화하고 구분하는 추상적인 개념. 실행 가능한 코드가 실행 되기 위해 필요한 환경. 여기서 말하는 실행 가능한 코드는

  • 전역 코드: 전역 영역에 존재하는 코드
  • Eval 코드: eval 함수로 실행하는 코드
  • 함수 코드: 함수 내에 존재하는 코드 자바스크립트 엔진은 코드를 실행하기 위해 아래와 같은 정보를 알고 있어야 한다
  • 변수: 전역변수, 지역변수, 매개변수, 객체의 프로퍼티
  • 함수 선언
  • 변수의 유효범위(Scope)
  • this

코드를 실행하면 아래와 같은 과정이 일어난다.

  1. 컨트롤이 실행 가능한 코드로 이동하면 논리적 스택 구조를 가지는 새로운 실행 컨텍스트 스택이 생성된다.
  2. 전역 코드로 컨트롤이 진입하면 전역 실행 컨텍스트가 생성되고 실행 컨텍스트 스택에 쌓인다. 전역 실행 컨텍스트는 애플리케이션이 종료될 때까지 유지된다
  3. 함수를 호출하면 해당 함수의 실행 컨텍스트가 생성되며 직전에 실행된 코드 블록의 실행 컨텍스트 위에 쌓인다
  4. 함수 실행이 끝나면 해당 함수의 실행 컨텍스트를 파기하고 직전의 실행 컨텍스트에 컨트롤을 반환한다.

실행 컨텍스트의 3가지 객체

실행 컨텍스트는 물리적으로 객체의 형태를 가지며 아래 3가지 프로퍼티를 소유한다

  • Variable object
  • Scope chain
  • thisValue

Variable Object (변수 객체)

variable object는 아래 정보를 담는다

  • 변수
  • 매개변수(parameter)와 인수 정보(arguments)
  • 함수 선언(함수 표현식은 제외) variable object는 다른 객체를 가리키는 값을 갖는다. 그런데 전역 코드 실행시 실행되는 전역 컨텍스트의 경우와 함수를 실행할 때 실행되는 함수 컨텍스트는 가리키는 값이 다르다. 전역 코드와 함수의 내용이 다르기 때문.

전역 컨텍스트의 경우

  • variable object는 전역 객체를 가리킨다.

함수 컨텍스트의 경우

  • Activation object를 가리키며 매개변수와 인수들의 정보를 배열의 형태로 담고 있는 객체인 arguments object가 추가된다.

Scope Chain

해당 전역 또는 함수가 참조할 수 있는 변수, 함수 선언 등의 정보를 담고 있는 전역 객체 또는 활성 객체의 리스트를 가리킨다

this value

this 프로퍼티에는 this 값이 할당된다. this에 할당되는 값은 함수 호출 패턴에 의해 결정된다.

참조

  • https://poiemaweb.com/js-execution-context

Scope

Closure

함수가 특정 스코프에 접근할 수 있도록 의도적으로 그 스코프에서 정의하는 것.
스코프를 함수 주변으로 좁히는closing 것.
자신의 scope 외부에 있는 것을 가져와 쓰는 것.

let globalFunc;
{
	let blockVar = 'a';
    globalFunc = function() {
    	console.log(blockVar);
    }
}
globalFunc();     // "a"

globalFunc가 있는 블록 스코프와 그 부모인 전역 스코프가 클로져를 형성. globalFunc를 어디서 호출하든 이 함수는 클로저에 들어있는 식별자에 접근할 수 있다.

즉시 호출하는 함수 표현식

함수 표현식을 사용하면 즉시 호출하는 함수 표현식(IIFE)을 만들 수 있다. IIFE는 함수를 선언하고 즉시 실행. 다음과 같은 형태를 취한다.

(function(){
	// IIFE 바디
})();

IIFE의 장점은 내부에 있는 것들이 모두 자신만의 스코프를 가지지만, IIFE 자체는 함수이므로 그 스코프 밖으로 무언가를 내보낼 수 있다는 것이다. IIFE는 함수이므로 무엇이든 반환할 수 있다.

var, let, const의 차이

  • var : function level scope를 가지며, 재할당이 가능하다. 호이스팅이 일어난다.
  • let : block level scope를 가지며, 재할당이 가능하다
  • const : block level scope를 가지며, 재할당이 불가능하다.

참조

  • 책 ‘러닝 자바스크립트(이선 브라운)’

this에 대해서

자바스크립트의 모든 함수는 실행될 때마다 함수 내부에 this라는 객체가 추가된다. 그렇기 때문에 자바스크립트에서 this는 함수가 호출된 상황에 따라 그 모습을 달리한다.

생성자 함수 / 객체에서의 this

new 키워드로 새로운 객체를 생성했을 경우 생성자 함수 내의 this는 new를 통해 만들어진 새로운 변수가 됨.

bind, call, apply 에서

명시적으로 this를 바꾸기에 this가 객체를 가리킴

arrow function

화살표 함수는 this로 window 대신 상위 함수의 this를 가져옴

참조

  • https://www.zerocho.com/category/JavaScript/post/5b0645cc7e3e36001bf676eb
  • https://blueshw.github.io/2018/03/12/this/

Promise

프로미스 기반 비동기적 함수를 호출하면 그 함수는 Promise 인스턴스를 반환한다. 프로미스는 fullfilled or rejected 두 가지뿐. 프로미스가 성공하거나 실패하면 그 프로미스를 settled 됐다고 말한다.
프로미스에 접근하려면 .then()을 쓴다.
error를 처리하려면 .catch()를 쓴다.

Async / Await

JavaScript 개발자들이 Promise로 만족하지 못하고 더 훌륭한 방법을 고안해낸 것. function 키워드 앞에 async를 붙여주면 되고, function 내부의 promise를 반환하는 비동기 처리 함수 앞에 await를 붙여주기만 하면 된다.
Promise 보다 비동기 코드의 겉모습을 더 깔끔하게 한다.

참조

  • https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/JavaScript

면접 예상 문제 답안 정리 - 전산기초 (운영체제)

https://github.com/JaeYeopHan/Interview_Question_for_Beginner 위 링크에 있는 문제에 대한 답안을 정리해보았다.

운영체제

프로세스와 스레드의 차이

  • 프로그램이란?
    • 실행가능한 명령어의 집합
  • 프로세스란?
    • 컴퓨터에서 연속적으로 실행되고 있는 프로그램
    • 정적인 프로그램과 달리 실제 실행 중이기 때문에 동적
    • 운영체제로부터 시스템 자원을 할당받는 작업의 단위
    • 유저가 사용하는 메모리 공간 상의 프로세스 정보는 다음과 같이 나뉜다
      • Code(text): 프로그램의 실제 코드를 저장
      • Data: 프로세스가 실행될 때 정의된 전역 변수,Static 변수들을 저장
      • Heap: 프로세스 런타임 중 동적으로 할당되는 변수들을 저장(함수 내에서 할당되는 변수 등)
      • Stack: 함수에서 다른 함수를 실행하는 등의 서브루틴들의 정보를 저장(재귀와 스택이 관련 있는 이유)
    • 운영체제는 각각의 프로세스를 독립적으로 관리하기 때문에 서로 다른 프로세스가 겹칠 일이 없다
    • 때문에 각 프로세스가 다른 프로세스의 정보를 변경하는 것을 극도로 주의하며 필요한 경우 최소한의 인터페이스를 제공해 소통할 수 있게 한다. 이런 프로세스간 소통을 Inter Process Communication(IPC)라고 한다
  • 스레드
    • 프로세스 내에서 실행되는 흐름
    • 하나의 프로세스는 하나의 스레드로 시작되며 이를 메인 스레드라 한다
    • 현대적인 운영체제는 하나의 프로세스 내에 여러 스레드가 존재할 수 있는 멀티스레딩을 지원한다. 왜일까?
    • 순차적인 방식은 한 작업이 오래 걸리면 전체 프로그램이 지연되는 병목현상이 생길 수 있음. 멀티 스레드의 경우 이런 문제점을 방지
    • 스레드의 장점
      • 프로세스 간 통신에 비해 스레드 간 통신이 훨씬 간단하다
      • 시스템의 자원 소모가 줄어든다
        • 기존 프로세스 자원을 다른 스레드와 공유
      • 전체 응답 시간이 줄어든다
    • 스레드의 단점 - 여러 스레드를 이용하는 경우 설계에 더 신경을 써야 한다 - 디버깅이 어렵다
  • 프로세스와 스레드의 차이
    • 프로세스는 운영체제로부터 독립된 시간, 공간 자원을 받아 할당되고 스레드는 한 프로세스 내에서 많은 자원을 공유하며 병렬적으로 실행된다
    • 프로세스는 독립적. 스레드는 독립적이지 않음. 여러 스레드가 같은 프로세스 자원을 공유하기 때문.
    • 프로세스간 통신은 스레드간 통신보다 어려움. 프로세스는 시스템이 제공하는 IPC 메커니즘을 통해서만 통신할 수 있고 시스템에 의해 관리되기 때문에 상재적으로 안전. 반면 스레드는 통신이 용이하지만 안전성이 떨어진다.
    • Context Switch에 있어서도 스레드가 일반적으로 더 빠르고 자원소모가 적다. 프로세스는 Switch 될 때 Context를 PCB에 저장하는 등 오버헤드가 발생하는데 스레드는 그런 부하가 적다.
  • 참조
    • https://shoark7.github.io/programming/knowledge/difference-between-process-and-thread

스케줄러의 종류

  • 스케줄링: 시스템이 실행하고자 할 때 프로세서를 프로그램들에게 할당하는 과정
  • 프로세스는 자신의 임무를 수행하고 사라질 때까지 많은 큐를 돌아다님
  • 이때 프로그램들은 제한된 프로세서(CPU)를 서로 사용하려고 함
  • OS는 이러한 프로세스 중 하나를 택하는데, 스케줄러가 이 역할을 담당
  • 프로세스를 스케줄링하는 큐에는 세 가지 종류가 존재
    • Job Queue: 현재 시스템 내에 있는 모든 프로세스의 집합
    • Ready Queue: 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합
    • Device Queue: Device I/O 작업을 대기하고 있는 프로세스의 집합 각각의 Queue에 프로세스들을 넣고 빼주는 스케줄러에도 세 가지 종류가 존재
  • 장기 스케줄러 (Long-term scheduler or job scheduler)
    • 메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리에 임시로 저장됨. 이 pool에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue로 보낼지 결정
    • 메모리와 디스크 사이의 스케줄링을 담당
    • 프로세스에 memory를 할당
    • degree of Multiprogramming 제어. 메모리에 몇 개의 프로그램이 올라갈지를 제어
    • 프로세스의 상태: new -> ready
  • 단기 스케줄러 (Short-term scheduler or CPU scheduler)
    • CPU와 메모리 사이의 스케줄링을 담당
    • Ready Queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정
    • 프로세스에 CPU를 할당
    • 프로세스의 상태: ready -> running - waiting -> ready
  • 중기 스케줄러 (Medium-term sheculer or Swapper)
    • 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 (Swapping)
    • 프로세스에게서 memory를 deallocate
    • degree of Multiprogramming 제어
    • 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러
    • 프로세스의 상태: ready -> suspended
  • 참조
    • https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS
    • https://shoark7.github.io/programming/knowledge/difference-between-process-and-thread

      CPU 스케줄러

  • 스케줄링 대상은 Ready Queue에 있는 프로세스들
  • FCFS (First Come First Served)
    • 먼저 온 순서대로 처리
    • 비선점형 (Non-preemptive) 스케줄링
      • 일단 CPU를 잡으면 CPU burst가 완료될 때까지 CPU를 반환하지 않는다. 할당되었던 CPU가 반환될 때만 스케줄링이 이루어진다
      • CPU를 사용중인 프로세스가 자율적으로 반납
      • Time-slice가 없음
    • 문제점 - convoy effect: 소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다
  • SJF (Shortest - Job - First)
    • CPU burst time이 짧은 프로세스에게 선 할당
    • 비선점형(Non-Preemptive) 스케줄링
    • 문제점
      • starvation: 사용시간이 긴 프로세스는 거의 영원히 CPU를 할당받을 수 없음
  • SRT(Shortest Remaining time First)
    • 최단 잔여시간을 우선으로 하는 스케줄링
    • 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어짐
    • 선점형(Preemptive) 스케줄링
      • 현재 수행 중인 프로세스의 남은 burst time 보다 더 짧은 CPU birst time을 갖는 새로운 프로세스가 도착하면 CPU를 뺏긴다
    • 문제점 - 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU birst time을 측정할 수가 없다
  • Priority Scheduling
    • 우선순위가 가장 높은 프로세스에 CPU를 할당. 우선순위는 정수로 표현, 작은 숫자가 우선순위가 높음
    • 선점형 스케줄링 방식
      • 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점
    • 비선점형 스케줄링 방식
      • 더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣는다
    • 문제점 - starvation - Indefinite blocking: 실행 준비는 되어있으나 CPU를 사용 못하는 프로세스를 CPU가 무기한 대기하는 상태
    • 해결책 - aging: 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여줌
  • Round Robin
    • 현대적인 CPU 스케줄링
    • 각 프로세스는 동일한 크기의 할당 시간을 갖게 됨
    • 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 뒤에 가서 다시 줄을 선다
    • CPU 사용시간이 랜덤한 프로세스가 섞여있을 경우 효율적
    • 장점
      • Response time이 빨라진다
      • 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가한다. 공정한 스케줄링.
  • 참조
    • https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS
    • https://hyunah030.tistory.com/4

동기와 비동기의 차이

  • 동기
    • 요청과 그 결과가 동시에 일어난다
    • 값이 반환되기 전까지는 blocking 되어 있음
    • 장점: 설계가 간단하고 직관적
    • 단점: 결과를 볼 때까지 아무것도 못하고 대기해야함
  • 비동기
    • 요청과 결과가 동시에 일어나지 않음
    • 장점: 결과가 주어지는데 시간이 걸리더라도 그 시간 동안 다른 작업이 가능해 자원의 효율적인 사용이 가능
    • 단점: 설계가 복잡함

멀티 스레드

  • 장점
    • 메모리 공간과 시스템 자원 소모가 줄어든다
    • 스레드 간 통신이 필요한 경우에도 Heap 영역을 이용하여 데이터를 주고 받을 수 있다. 프로세스 간 통신 방법에 비해 훨씬 간단함.
    • 실행의 흐름을 명확히 분리할 수 있다
    • 대기 시간, 응답시간을 최소화 할 수 있다
  • 단점
    • 구현하기 어려움
    • 테스트, 디버깅하기 어려움
    • 다른 스레드가 데이터와 힙 영역을 공유하기 때문에 다른 스레드에서 사용중인 변수나 자료구조에 접근하여 문제를 일으킬 수 있음
    • 때문에 동기화 작업 필요. 이로 인해 병목현상이 발생하여 성능이 저하될 수 있음

프로세스 동기화

  • 프로세스가 공유 자원을 사용하는 상황에서, 경쟁 조건이 발생하면 공유 자원을 신뢰할 수 없게 만들 수 있음. 이를 방지하기 위해 공유 자원을 사용할 때 특별한 규칙을 만드는 것이 프로세스 동기화
  • 경쟁 조건 (Race Condition)
    • 여러 프로세스(또는 스레드)가 공유 자원에 동시에 접근할 때, 공유 자원에 대한 접근 순서에 따라 실행 결과가 달라질 수 있는 상황
  • Critical Section (임계영역)
    • 여러 프로세스(또는 스레드)가 자원을 공유하는 상황에서, 하나의 프로세스(스레드)만 접근할 수 있도록 제한해둔 코드 영역
  • Critical Section 문제의 해결 조건
    • 상호 배제(Mutual Exclusion): 어떤 프로세스(또는 스레드)가 임계 구역에서 작업 중일 때, 다른 프로세스는 임계 구역으로 접근할 수 없다
    • 진행 (Process): 임계 구역에서 작업 중인 프로세스가 없다면, 임계 구역으로 진입하려는 프로세스 중 하나를 선택하여 진입할 수 있게 해야 한다
    • 유한 대기 (Bounded Wating): 다른 프로세스의 starvation을 방지하기 위해, 임계 구역에 한 번 접근했던 프로세스는 다시 임계구역에 들어갈 때 제한을 두어야 한다
  • 해결책
    • 하드웨어 동기화 방법
      • lock을 이용한 해결책. 특정 프로세스가 공유 자원에 접근 중일 때는 다른 프로세스는 접근 하지 못하도록 Lock을 건다.
      • 싱글 프로세서 환경에서는 공유 데이터가 변경되는 동안 인터럽트를 막으면 임계 구역 문제를 해결할 수 있다. 비선점형 커널에서도 이 방법을 사용한다
    • 고전적인 소프트웨어 해결책: 피터슨 알고리즘, 데커 알고리즘 - CPU가 여러 개일 때는 동작 안함
  • 세마포어 (Semaphore)
    • Critical Section 문제를 해결하기 위한 동기화 도구
    • 종류
      • 카운팅 세마포 (counting semaphore)
        • 세마포는 공유자원의 개수를 나타내는 변수임
        • ex) 다섯 대의 프린터가 있을 때 세마포는 5. 사용할 프린터가 없어지면 0.
        • 사용가능한 자원의 개수로 초기화됨
      • 이진 세마포 (binary semaphore) - MUTEX 라고도 함 - shared data의 개수 - ex) 두 개의 기차가 동시에 이용하는 기찻길이 있을 때, 어떤 기차가 지나가고 있으면 0, 비어있으면 1
    • 단점 - Busy Waiting(바쁜 대기) - lock의 해제를 기다리는 동안 빈 반복문을 반복해서 돌기 때문에 context switching이 발생
    • 해결방법 - block()을 통해서 프로세스를 대기 상태로 전환하고 CPU 스케줄링을 실행
    • Deadlock (교착상태) - 세마포가 Ready Queue를 가지고 있고, 둘 이상의 프로세스가 Critical Section 진입을 무한정 기다리고 있고, Critical Section에서 실행되는 프로세스는 진입 대기 중인 프로세스가 실행되야만 빠져나올 수 있는 상황
  • 참조
    • https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS
    • https://jhnyang.tistory.com/101
    • https://jungwoon.github.io/os/2019/07/31/Process-Synchronization/

메모리 관리 전략

  • 메모리는 CPU가 직접 접근하는 유일한 저장장치. 메모리 시스템(하드웨어)은 주소(메모리 위치)를 관리하며 할당과 접근을 제어한다.
  • 목적
    • 제한된 물리 메모리의 효율적인 사용 (할당)
    • 효율적인 메모리 참조 (논리-물리 주소 할당)

메모리 전략

  • Swapping
    • CPU 할당 시간이 끝난 프로세스의 메모리를 보조 기억장치로 내보내고 다른 프로세스의 메모리를 불러들임
    • Swap in: 주 기억장치(RAM)으로 불러옴
    • Swap out: 메모리 공간이 부족하면 보조 기억장치로 내보냄
  • Fragmentation (단편화)
    • 프로세스들이 메모리에 적재되고 제거되는 일이 반복되다 보면 프로세스들이 차지하는 메모리 틈 사이에 사용 하지 못할 만큼의 작은 자유 공간들이 늘어남. 이것이 단편화
    • 종류
      • 외부 단편화: 메모리 공간 중 사용하지 못하게 되는 일부분. 물리 메모리에서 사이사이 남는 공간들을 모두 합치면 충분한 공간이 되는 부분들이 분산되어 있을 때 발생
      • 내부 단편화: 할당된 기억 공간이 요청된 기억 공간보다 더 커 기억 공간이 남는 현상
  • Paging (페이징)
    • 단편화의 문제를 해결하기 위해 프로그램 전체를 연속된 공간에 적재하지 않고 일정 크기의 단위로 나누어서 분산 적재하는 방법
    • 물리 메모리는 Frame이라는 고정 크기로 분리되어 있고, 논리 메모리는 페이지라 불리는 고정 크기의 블록으로 분리됨
    • 논리 메모리는 물리 메모리에 저장될 때, 연속되어 저장될 필요가 없고 물리 메모리의 남는 프레임에 적절히 배치됨으로써 외부 단편화를 해결
  • Segmentation
    • 페이징처럼 논리 메모리와 물리 메모리를 같은 크기의 블록이 아닌, 서로 다른 크기의 논리적 단위인 세크먼트로 분할.
    • 단점: 서로 다른 크기의 세그먼트들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 자유 공간들이 많은 수의 조각으로 나뉘어져 못 쓸 수도 있다 (외부 단편화)
  • 참조
    • http://blog.naver.com/PostView.nhn?blogId=yeop9657&logNo=220728971005&parentCategoryNo=&categoryNo=145&viewDate=&isShowPopularPosts=true&from=search
    • https://jungwoon.github.io/os/2019/07/31/Virtual-Memory/
    • https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS

면접 예상 문제 답안 정리 - 전산기초 (네트워크)

https://github.com/JaeYeopHan/Interview_Question_for_Beginner 위 링크에 있는 문제에 대한 답안을 정리해보았다.

네트워크

GET, POST 방식의 차이점

  • GET
    • 데이터를 url의 쿼리스트링을 통해 전송
    • url이라는 공간에 담기 때문에 전송할 수 있는 데이터의 크기가 제한적
    • 데이터가 url에 노출되므로 보안이 필요한 데이터에는 적합하지 않음
    • Idempotent함. 서버에게 동일한 요청을 여러번 전송해도 동일한 응답이 나타나야 함.
    • 때문에 주로 조회를 할 때 사용
  • POST
    • HTTP Message의 Body에 담아 데이터를 전송
    • 보낼 수 있는 데이터의 크기가 크고 보안 면에서 GET보다 낫다
    • Non-idempotent. 서버에게 동일한 요청을 전송해도 결과값은 다를 수 있음.
    • 때문에 서버의 상태나 데이터를 변경할 때 사용.

OSI 7 계층

  • 1 : Physical Layer
    • 전기적, 기계적 특성을 통해 통신 케이블로 데이터를 전송
    • 이 단계에서 통신 단위는 bit. 1과 0으로 나타나는 전기적으로 on, off 상태
    • 데이터를 전달하기만 할 뿐 전송하려는 데이터가 무엇인지 신경쓰지 않음
    • 통신 케이블, 허브, 리피터
  • 2 : Data-Link Layer
    • 물리 계층에서 받은 정보의 전달을 수행
    • 물리 계층의 오류를 찾아내고 수정하는 기능 제공
    • 맥 주소를 가지고 통신
    • 이 계층에서 부르는 데이터의 단위는 프레임
    • 브리지, 스위치
  • 3 : Network Layer
    • 데이터를 목적지까지 빠르고 안전하게 전달(라우팅)
    • 어느 컴퓨터에 데이터를 전송할지 주소를 갖고 있음. IP 주소
    • 데이터 단위는 패킷
    • 주소 부여(IP), 경로 설정(Route)
  • 4 : Transport Layer
    • 양 끝단의 사용자들이 신뢰성 있는 데이터를 주고 받을 수 있게 해줌
    • 송신자와 수신자 간의 효율적인 데이터 전송을 위해 오류검출 및 복구, 흐름제어와 중복조사 등을 수행
    • 데이터 전송을 위해 Port 번호가 사용됨
    • 대표적인 프로토콜로는 TCP와 UDP가 있음
    • 데이터 단위는 세그먼트
  • 5 : Session Layer
    • 응용 프로세스가 통신을 관리하기 위한 방법 정의
    • TCP/IP 세션을 만들고 없애는 역할
    • 통신하는 사용자들을 동기화하고 오류복구 명령들을 일괄적으로 다룸
  • 6 : Presentation Layer
    • 데이터를 어떻게 표현할지 정하는 역할을 하는 계층, 일종의 확장자
    • 데이터 압축, 암호화 등의 기능을 수행
    • ex) EBCDIC로 인코딩된 파일을 ASCII 로 인코딩된 파일로 바꿔주는 것
  • 7 : Application Layer
    • 최종 목적지. HTTP, FTP, SMTP 등과 같은 프로토콜이 있다
    • 응용 프로세스와 직접 관계하여 일반적인 응용 서비스를 수행
  • 참조
    • https://shlee0882.tistory.com/110
    • https://reakwon.tistory.com/59

TCP 3-way-handshake

  • Transport Layer의 프로토콜에는 크게 TCP와 UDP가 있음. 전자는 연결지향적이고, 후자는 비연결적. TCP가 연결 지향적인 특성을 갖게 해주는 방법이 바로 TCP 3-way-handshake 방식.
  • 과정
    • SYN은 Synchronize Sequence Number, ACK는 Acknowledge의 약자
      1. A 클라이언트는 B 서버에 접속을 요청하는 SYN 패킷을 보낸다. 이때 A 클라이언트는 SYN을 보내고 SYN/ACK 응답을 기다리는 SYN_SENT 상태가 된다
      1. 이때 서버는 Listen 상태로 포트 서비스가 가능한 상태여야 한다. B 서버는 SYN 요청을 받고 A 클라이언트에게 요청을 수락한다는 ACK와 SYN flag가 설정된 패킷을 발송하고 A가 다시 ACK로 응답하길 기다린다. 이때 B 서버는 SYN_RECEIVED 상태가 된다
      1. A 클라이어트는 B 서버에게 ACK를 보내고 이후로 연결이 이어져 데이터가 오간다. 이때 B 서버의 상태는 ESTABLISHED 이다.
  • 참조
    • https://mindnet.tistory.com/entry/%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-%EC%89%BD%EA%B2%8C-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-22%ED%8E%B8-TCP-3-WayHandshake-4-WayHandshake

TCP 와 UDP 의 차이점

  • TCP (Transmission Control Protocol)
    • 연결형 서비스로 가상 회선 방식을 제공한다 (3-way-handshake 방식으로 연결 설정, 4-way-handshake 방식으로 연결 해제)
    • 서버와 클라이언트는 1대1로 연결된다
    • 흐름 제어 : 데이터 처리 속도를 조절하여 수산자의 버퍼 오버플로우를 방지
    • 혼잡 제어 : 네트워크 내의 패킷 수가 넘치게 증가하지 않도록 방지
    • 신뢰성이 높은 전송
      • Dupack-based retransmission
        • 정상적인 상황에서는 ACK 값이 연속적으로 전송되어야 한다
        • 그러나 ACk 값이 중복으로 올 경우 패킷 이상을 감지하고 재전송을 요청한다
      • Timeout-based retransmission - 일정시간동안 ACK 값이 수신을 못할 경우 재전송을 요청한다
    • 패킷에 대한 응답을 해야 하기 때문에(시간지연, CPU 소모) 성능이 낮다
    • Streaming 서비스에 불리하다 (손실된 경우 재전송 요청을 하므로)
  • UDP (User Datagram Protocol)
    • 비연결형 서비스로 데이터그램 방식을 제공한다
    • 정보를 주고 받을 때 신호절차를 거치지 않는다
    • UDP 헤더의 CheckSum 필드를 통해 최소한의 오류만 검출한다
    • 신뢰성이 낮다
    • TCP보다 속도가 빠르다
    • 서버와 클라이언트는 1대1, 1대N, N대M 등으로 연결될 수 있다
    • 흐름 제어가 없어서 패킷이 제대로 전송되었는지 확인할 수 없다
    • 파일 전송과 같은 신뢰성이 필요한 서비스보다 성능이 우선되는 경우에 사용한다
  • 참조
    • https://mangkyu.tistory.com/15
    • https://velog.io/@hidaehyunlee/TCP-%EC%99%80-UDP-%EC%9D%98-%EC%B0%A8%EC%9D%B4

HTTP 와 HTTPS 의 차이점

  • HTTP (HyperText Transfer Protocol)
    • 서버와 클라이언트가 인터넷에서 데이터를 주고받기 위한 프로토콜
    • 장점
      • 불특정 다수를 대상으로 하는 서비스에 적합
      • 클라이언트와 서버가 계속 연결된 상태가 아니기 때문에 클라이언트와 서버 간 최대 연결수보다 많은 요청과 응답 처리가 가능
    • 단점
      • 연결을 끊어버리기 때문에, 클라이언트는 이전 상황을 알 수 없음
      • 이러한 특징을 무상태성(stateless)라고 함
      • 정보 유지를 위해 cookie 같은 기술이 등장
    • 문제점 - 통신 상대를 확인하지 않기 때문에 누구나 요청을 보낼 수 있다. 액세스 제한이 없는 경우 요청이 오면 그게 누구든지 응답을 반환한다. - 평문 통신이기 때문에 도청이 가능 - 통신 상대를 확인하지 않기 때문에 위장이 가능 - 완전성을 증명할 수 없기 때문에 변조가 가능 - 의미없는 리퀘스트도 수신한다 -> DoS 공격을 방지할 수 없다
    • 보안 방법 - TCP/IP 구조의 통신은 도청이 가능한 네트워크 - 1. 통신 자체를 암호화 - SSL(Secure Socket Layer) or TLS(Transport Layer Security)라는 다른 프로토콜을 조합해 HTTP 통신 내용을 암호화한다 - SSL을 조합한 HTTP를 HTTPS(HTTP Secure)라고 한다
        1. 콘텐츠를 암호화 - HTTP 메시지에 포함되는 콘텐츠만 암호화하는 것으로 받은 측에서는 암호를 해독화하는 처리가 필요하다
  • HTTPS
    • HTTP에 암호화, 인증, 완전성 보호를 더한 것
    • HTTP가 통신하는 소켓 부분을 SSL(Secure Socket Layer)이나 TLS라는 다른 프로토콜로 대체하는 것
    • HTTPS의 SSL에서는 공통키 암호화 방식과 공개키 암호화 방식을 혼합한 하이브리드 암호 시스템을 이용한다
    • 모든 웹페이지에서 HTTPS를 이용하지 않는 이유
      • 평문 통신에 비해 암호화 통신은 CPU나 메모리 등 리소스가 많이 필요하다
      • 통신할 때마다 암호화를 하면 많은 리소스를 소비하게 되어 서버 한 대당 처리할 수 있는 리퀘스트 수가 줄어든다
    • HTTP 2.0이 나오면서 HTTPS가 HTTP보다 빨라졌다고 한다
  • 참조
    • https://brenden.tistory.com/45

DNS round robin 방식

  • DNS(Domain Name System): 도메인 이름과 IP 주소를 변환하는 역할
  • DNS Round Robin
    • DNS를 이용해 하나의 서비스에 여러 대의 서버를 분산시키는 방법
    • 웹 사이트에 접속하는 다수의 사용자는 복수의 웹 서버를 접속, 자연스럽게 서버의 부하가 분산됨
  • 장점
    • 비용적인 부담이 줄어든다
    • 중간 장비 없이도 서비스가 가능하다
  • 단점
    • 서버의 수만큼 공인 IP 주소가 필요하다
    • 한 대의 서버에서 장애가 발생할시, 원인을 찾기 힘들다
    • 부하의 분산이 고르지 않다
    • 서버에 이상이 있는 경우에도 서버로 부하를 분산한다
  • 참조
    • https://server-talk.tistory.com/121

웹 통신의 큰 흐름

브라우저에 url을 입력했을 때 일어나는 일

  1. 브라우저의 url 파싱
    • url의 구조 : https(protocol)://www.naver.com(URL):443(port)
    • 어떤 프로토콜, url, 포트로 요청할지 해석하여 분석한다
    • 포트를 명시적으로 선언하지 않았다면 기본값 (HTTP-80, HTTPS-443)을 요청
  2. HSTS 목록 조회
    • HSTS(HTTP Strict Transport Security)는 HTTP를 허용하지 않고 HTTPS만 허용하는 기능
    • HTTP로 응답 요청이 오면 헤더에 Strict Transport Security라는 필드를 포함하여 응답하고 이를 확인한 브라우저는 HSTS 캐시에 해당 URL을 저장 -> HSTS 목록
    • 브라우저에서는 이 목록을 조회하여 해당 요청을 HTTPS로 보낼지 판단
  3. URL을 IP 주소로 변환
    • URL을 컴퓨터가 읽을 수 있는 IP로 변환해야 함
    • 브라우저는 자신의 로컬 hosts 파일과 브라우저 캐시에 해당 url이 존재하는지 확인
    • 존재하지 않느다면 도메인 주소를 IP 주소로 변환해주는 DNS 서버에 요청하여 변환
  4. 라우터를 통해 해당 서버의 게이트웨이까지 이동
    • 라우터는 라우팅을 통해 해당 요청이 어디로 가야할지 경로를 정해줌
  5. ARP를 통해 IP 주소를 MAC 주소로 변환
    • 논리 주소인 IP 주소를 물리 주소인 MAC 주소로 변환
  6. 대상 서버와 TCP 소켓 연결
    • 소켓 연결은 3-way-handshake 과정을 통해 이루어짐
    • HTTPS 에서는 서로 암호화 통신을 위해 TLS 핸드쉐이킹이 추가됨
  7. HTTP(HTTPS) 프로토콜로 요청, 응답
    • 해당 페이지를 달라고 서버에게 요청
    • 서버에서 요청을 받고 수행할 수 있는지 검사
    • 서버는 응답을 생성하여 브라우저에 전달
  8. 브라우저에서 응답을 해석
    • 서버에서 응답한 내용은 HTML, CSS, JavaScript 등으로 이루어짐
    • 이를 브라우저에서 해석하여 그려줌 - 참조
    • https://deveric.tistory.com/97

면접 예상 문제 답안 정리 - 전산기초 (자료구조)

https://github.com/JaeYeopHan/Interview_Question_for_Beginner 위 링크에 있는 문제에 대한 답안을 정리해보았다.

1. 전산 기초

자료구조

Array vs Linked List

  • Array
    • index를 통해 element에 직접적으로 접근할 수 있다. 특정 element에 접근하는 시간 복잡도는 O(1)
    • memory 위치가 고정적이기에 삽입과 삭제 연산 시 시간이 많이 소요됨. 삭제 시 삭제한 원소보다 큰 인덱스의 원소들을 shift하는 비용이 발생, 시간 복잡도는 O(n). 삽입의 경우에도 비슷하게 O(n)
  • Linked List
    • 각각의 원소들이 자기 다음 원소만을 기억하게 함. 때문에 search시 시간 복잡도는 O(n)
    • 삭제와 삽입 시 다음 원소를 가리키는 값을 바꾸면 되므로 시간 복잡도는 O(n)
    • Tree 구조의 근간

Stack and Queue

  • Stack
    • Last In First Out (LIFO). 나중에 들어간 원소가 먼저 나옴.
  • Queue
    • First In First Out (FIFO). 먼저 들어간 원소가 먼저 나옴.

Tree

  • Stack이나 Queue와 다르게 비선형적 자료 구조.
  • Tree는 root와 leaf로 이루어짐
  • Binary Tree (이진 트리)
    • 모든 노드의 차수가 2 이하인 트리
    • Full Binary Tree (포화 이진 트리)
      • 모든 레벨에서 노드들이 모두 채워져있는 이진 트리
    • Complete Binary Tree (완전 이진 트리) - 마지막 레벨을 제외하고는 모든 노드가 자식 노드를 2개 가진 이진 트리
  • Binary Search Tree (이진 탐색 트리)
    • 모든 노드에 대하여
      • 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
      • 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 크고
      • 왼쪽과 오른쪽 서브트리 역시 각각 이진 탐색 트리여야 한다
    • 이진 탐색과 연결 리스트를 결합한 자료 구조의 일종
  • Red Black Tree
    • Search, Insert, Delete에 O(logn)의 시간 복잡도 소요
    • 정의
      • 각 노드는 Red or Black이란 색을 갖는다
      • 루트 노드는 블랙이다
      • 모든 리프 노드들은 블랙이다
      • 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다
      • 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다
    • 특성
      • 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배 보다 작다
      • 레드-블랙 트리는 개략적으로 균형잡혀있다
      • 시간 복잡도가 높이에 따라 결정됨
  • 참조
    • https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

Hash Table

  • 연관배열 구조를 이용해 key 값에 value를 저장하는 자료 구조
  • 해시 테이블은 key, hash function, hash, value, bucket(저장소)으로 이루어져 있다
  • key는 hash function을 통해 hash로 변경되며 value와 매칭되어 저장소에 저장 된다
    • key: 고유한 값, 해시 함수의 input.
    • hash function: key를 hash로 바꾸어 줌. 서로 다른 key가 같은 해시가 되는 경우 hash collision이 일어난다. collision을 최소화하는 방식이 필요.
    • hash: hash function의 결과물.
    • value: 저장소에 최종적으로 key와 매칭되어 저장되는 값
  • Insertion
    • 시간 복잡도는 O(1). key는 고유하며 해시함수의 결과로 나온 hash와 value를 저장소에 넣으면 되기 때문.
    • 최악의 경우 O(n)이 될 수도 있음. 해시 충돌로 인해 모든 value를 찾아봐야 할 경우.
  • Deletion
    • 시간 복잡도 O(1), 최악의 경우 O(n)
  • Search
    • 시간 복잡도 O(1), 최악의 경우 O(n)
  • Hash Collision을 해결하는 법
    • Seperate Chaining
      • 연결 리스트를 이용하는 방식
        • 각각의 bucket을 연결 리스트로 만들어 collision 이 발생하면 해당 bucket의 리스트에 추가. 연결 리스트의 특성을 물려받아 삭제 또는 삽입이 간단.
    • Open Addressing - 비어있는 해시를 찾아 데이터를 저장하는 방법 - 해시 테이블은 1개의 해시와 1개의 값이 매칭되어있는 방식으로 유지 - 장점 - 다른 저장공간 없이 해시테이블 내에서 저장 및 처리가 가능 - 다른 저장공간에서 추가적인 작업이 없음
      • 단점 - 해시함수의 성능에 따라 전체 해시테이블의 선응이 좌우됨 - 데이터의 길이가 늘어나면 해당하는 저장소 필요
  • 해쉬 테이블 구조의 단점
    • 순서가 있는 배열에 어울리지 않음
    • 공간 효율성이 떨어짐
    • Hash Function의 의존도가 높음
  • 참조
    • https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table%ED%95%B4%EC%8B%9C-%ED%95%B4%EC%8B%B1-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%9D%98-%EC%9D%B4%ED%95%B4-6ijyonph6o

Graph

  • 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료구조
  • 연결되어 있는 객체 간의 관계를 표현할 수 있음
  • 트리 또한 그래프에 속하며, 그 중 사이클이 허용되지 않는 그래프임
  • 그래프의 종류
    • 무방향 그래프 vs 방향 그래프
      • 무방향 그래프 (Undirected Graph)
        • 간선을 통해 양방향으로 갈 수 있는 그래프
        • 정점 A와 정점 B를 연결할 수 있는 간선은 (A, B)와 같이 정점의 쌍으로 표시
      • 방향 그래프 (Directed Graph)
        • 간선에 방향성이 존재하는 그래프
        • A -> B로만 갈 수 있는 간선은 <A, B>로 표시한다
        • 트리 또한 방향 그래프
    • 가중치 그래프 (Weighted Graph)
      • 간선에 비용이나 가중치가 할당된 그래프
      • ‘네트워크’라고도 한다
    • 연결 그래프 vs 비연결 그래프 - 연결 그래프 (Connected Graph) - 무방향 그래프에 있는 모든 정점쌍에 대해 항상 경로가 존재하는 경우 - ex) 트리
      • 비연결 그래프 (Unconnected Graph) - 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
    • 사이클 vs 비순환 그래프 - 사이클 (Cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우 - 비순환 그래프 (Acyclic Graph) : 사이클이 없는 그래프
    • 완전 그래프 (Completed Graph) - 그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프
  • 그래프의 구현
    • 인접 리스트 (adjacent list)
      • 각각의 정점에 인접한 정점들을 리스트로 표시
      • 장점
        • 어떤 노드에 인접한 노드를 쉽게 찾을 수 있다
        • 모든 간선의 수는 O(N + E)안에 알 수 있다 (정점의 수 + 간선의 수)
      • 단점 - vertex 간 연결되어 있는지 확인하는데 오래 걸림
    • 인접 행렬 (Adjancy Matrix) - matrix[i][j]가 true이면 i -> j로의 간선이 있음 - 정점의 개수가 n인 그래프를 인접 행렬로 표현할 때, 간선의 수와 무관하게 항상 n^2의 메모리 공간이 필요하다 - 장점 - 두 정점을 연결하는 간선의 존재여부를 O(1)에 알 수 있다 - 정점의 차수는 O(N) 안에 알 수 있다. 인접 배열의 i번째 행 또는 열을 전부 더하면 되기 때문
      • 단점 - 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 한다 - 그래프에 존재하는 모든 간선의 수를 파악하는데 O(N^2)이 소요됨
    • 정점의 개수가 적으면 인접 행렬, 많으면 인접 리스트를 사용하는 것이 효율적일 수 있음
  • 그래프의 탐색
    • 깊이 우선 탐색 (DFS)
      • 모든 노드를 방문하고자 할 때 사용
    • 너비 우선 탐색 (BFS)
      • 두 노드 사이의 최단 경로나 임의의 경로를 찾고 싶을 때 사용
  • 참조
    • https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

면접 예상 문제 답안 정리 - 전산기초

https://github.com/JaeYeopHan/Interview_Question_for_Beginner 위 링크에 있는 문제에 대한 답안을 정리해보았다.

1. 전산 기초

개발상식

객체 지향 프로그래밍이란?

  • 컴퓨터 프로그래밍 패러다임 중 하나. 프로그램을 단순히 명령어 모음(절차적 프로그래밍)으로 보는 것이 아니라, 객체라는 기본 단위들의 상호작용으로 보는 것. 이전 패러다임에 비해 인간 중심적 패러다임이라고 할 수 있다. 현실 세계의 사물을 객체라 보고 그 객체로부터 필요한 특징을 추상화해 프로그래밍 하는 것이기 때문.

###RESTFulAPI란?

  • REST는 Representational State Transfer. 웹에 존재하는 모든 자원에 고유한 URI를 부여해 활용하는 것. REST의 구성 요소로는 자원(URI), 행위(HTTP METHOD), 표현(Representations)으로 이루어져 있다. 즉 REST는 HTTP 기반으로 필요한 자원에 접근하는 방식을 정해놓은 아키텍쳐.
  • REST의 특징
    • Uniform Interface: HTTP 표준만 따른다면 어떤 플랫폼에서도 사용할 수 있는 인터페이스 스타일
    • Stateless: Rest는 상태 정보를 유지하지 않고 서버는 각각의 요청을 다른 것으로 인식하고 처리
    • Cachable: HTTP의 기존 웹 표준을 그대로 이용하기 때문에 HTTP가 가진 캐싱 기능 적용
    • Self-descriptiveness
    • Client-Server 구조: REST 서버는 API 제공, 클라이언트는 사용자 인증에 관한 일 관리. 각각의 역할이 구분되므로 의존성이 적어짐.
    • Layered System
  • REST API?
    • REST 기반 규칙을 지켜서 설계된 API
  • REST API 설계 규칙
    • URI는 정보의 자원을 표기. 자원의 이름은 동사보다는 명사.
    • 자원의 행위는 HTTP METHOD로 표현.
    • 슬래시(/)는 계층 관계를 표현
    • URI 마지막은 슬래시 사용X
    • 하이픈(-)은 가독성을 높이는데 사용. 언더바(_)나 밑줄은 사용하지 않음.
    • 파일 확장자는 URI에 포함 X
  • 장점
    • Open API를 제공하기 쉽다
    • 멀티플랫폼 지원 및 연동이 용이
    • 원하는 타입으로 데이터를 주고받을 수 있다
    • 기존 웹 인프라(HTTP)를 그대로 사용할 수 있다
  • 단점
    • 사용할 수 있는 메소드가 4가지밖에 없다
    • 분산환경에는 부적합하다
    • HTTP 통신 모델에만 지원한다
  • 참조
    • https://velog.io/@stampid/REST-API%EC%99%80-RESTful-API

TDD란 무엇이며 어떤 장점이 있는가?

  • Test Driven Development. 테스트 코드 작성 -> 코드 개발 -> 리팩토링 순으로 짧은 개발을 반복하는 것.
  • 장점
    • 실시간으로 오류 상황을 파악하여 시스템 결함을 방지할 수 있다
    • 짧은 개발 주기로 고객의 요구사항을 빠르게 수용할 수 있음
    • 코드의 모듈화가 자연스럽게 이루어짐
    • 유지보수가 쉬워짐
  • 단점
    • 기존의 개발 프로세스에 테스트 코드까지 더해져 코드 생산 비용이 높아짐
    • 어떻게 테스트를 할지, 무슨 프레임워크를 선택할지 등 여러 고려가 필요
    • 모든 상황에 대해 테스트 코드를 작성하기 어려움
  • 참조
    • https://velog.io/@velopert/TDD%EC%9D%98-%EC%86%8C%EA%B0%9C
    • https://m.blog.naver.com/PostView.nhn?blogId=suresofttech&logNo=221039173819&proxyReferer=https:%2F%2Fwww.google.com%2F

함수형 프로그래밍이란 무엇인가?

  • 함수형 프로그래밍
    • 계산을 수학적 함수의 조합으로 생각하는 방식
    • 일반적인 프로그램 언어에서 함수가 특정 동작을 수행하는 역할을 담당하는 것과 반대. 함수를 수행해도 함수 외부의 값이 변경될 수 없다.
  • 함수형 프로그래밍 언어의 특징
    • 불변성(Immutability)
      • 변경 가능한 상태를 최대한 제거
      • 함수 내부에 상태가 존재하지 않아 같은 입력에는 항상 같은 출력값이 보장
      • 부작용(side effect)가 없는 함수
    • First-class, higher-ordered functions
      • 함수는 일등 시민. 함수를 변수에 할당할 수 있고, 다른 함수의 인자로 전달할 수도, 다른 함수의 결과값으로 반환할 수도 있음.
    • Lazy evaluation
  • 참조
    • https://velog.io/@kyusung/%ED%95%A8%EC%88%98%ED%98%95-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%EC%9A%94%EC%95%BD
    • https://medium.com/@lazysoul/%ED%95%A8%EC%88%98%ED%98%95-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%EC%9D%B4%EB%9E%80-d881230f2a5e

MVC 패턴이란 무엇인가?

  • MVC 패턴
    • 소프트웨어 디자인 패턴 중 하나.
      • 디자인 패턴: 소프트웨어 디자인에서 특정 문맥에서 공통적으로 발생하는 문제에 대해 재사용 가능한 해결책
  • 구성요소
    • Controller
      • 클라이언트의 요청을 받았을 때, 그 요청에 대해 실제 업무를 수행하는 모델 컴포넌트를 호출, 혹은 모델에 전달하기 쉽도록 데이터 가공. 모델이 업무를 마치면 결과를 뷰에게 전달.
    • Model
      • 애플리케이션의 데이터.
      • 모델의 상태에 변화가 있을 때 컨트롤러와 뷰에 이를 통보.
    • View - 컨트롤러에게 받은 모델의 결과값을 가지고 사용자에게 보여줄 화면을 만듦. 만들어진 화면을 웹브라우저에 전송해 출력하게 함.
  • 장점
    • 서로 분리되어 각자의 역할에 집중 => 애플리케이션의 유지보수성, 확장성, 유연성 증가
  • 참조
    • https://ko.wikipedia.org/wiki/%EB%AA%A8%EB%8D%B8-%EB%B7%B0-%EC%BB%A8%ED%8A%B8%EB%A1%A4%EB%9F%AC
    • https://m.blog.naver.com/jhc9639/220967034588
    • https://asfirstalways.tistory.com/180

[프로그래머스] LV3 : 불량 사용자 (카카오 겨울 인턴십)

문제: https://programmers.co.kr/learn/courses/30/lessons/64064#

풀이

여러번 풀어보려 시도했으나 풀지 못했던 문제.
다음과 같은 과정으로 해결했다.

  1. 불량 사용자가 될 수 있는 후보를 골라낸다. (정규식 사용)
  2. 1에서 구한 것을 바탕으로 모든 가능한 경우의 수를 구한다. (product 사용)
  3. 2에서 구한 경우에서 중복을 제거한다. 3-1. len(candidate_tuple) == len(set(candidate_tuple))으로 튜플 내에 겹치는 원소가 있는지 판단 3-2. 튜플을 리스트로 바꾸고 정렬, 다시 튜플로 변환한 뒤 set에 넣어 튜플끼리 중복을 없앤다.
  4. 해당 set의 length를 구하면 정답.

소스코드

import re
from itertools import product

def solution(user_id, banned_id):
    candidates_id = []

    for ban in banned_id:
        candidates = []
        ban_re = re.compile(ban.replace("*", "\w"))

        for user in user_id:
            if len(user) == len(ban) and ban_re.match(user) is not None:
                candidates.append(user)

        candidates_id.append(candidates)

    candidates_product = list(product(*candidates_id))
    new_candidates = []

    for candidate_tuple in candidates_product:
        if len(candidate_tuple) == len(set(candidate_tuple)):
            new_candidates.append(candidate_tuple)

    answer_set = set()
    for candidate in new_candidates:
        candidate_list = sorted(list(candidate))
        answer.add(tuple(candidate_list))
        
    return len(answer_set)

[BOJ] 3986 : 좋은 단어 (Python3)

문제: https://www.acmicpc.net/problem/3986

풀이

스택을 이용해 풀이했다.
스택에 원소가 없으면 단어의 알파벳을 넣고, 있으면 현재 알파벳과 스택의 마지막 원소를 비교했다.
마지막 원소가 같으면 쌍이 지어지므로 stack의 원소를 pop했다.
원소가 다르면 알파벳을 stack에 append하고 다음 알파벳으로 넘어간다.
이 과정을 끝내고 stack에 원소가 있으면 쌍이 지어지지 않은 알파벳이 있는 것이므로 좋은 단어가 아니다.
좋은 단어일 경우만 카운트해 출력한다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
words = [input().strip() for _ in range(n)]
cnt = 0

for word in words:
    fixed_word = ""

    stack = []
    for alphabet in word:
        if not stack:
            stack.append(alphabet)
        else:
            if stack[-1] == alphabet:
                stack.pop()
            else:
                stack.append(alphabet)
    else:
        if not stack:
            cnt += 1

print(cnt)

[BOJ] 14502 : 연구소 (Python3)

문제: https://www.acmicpc.net/problem/14502

풀이

완전탐색과 dfs로 해결했다.
지도에서 0에 해당하는 인덱스를 리스트에 넣어두고, 이 리스트에서 3개 조합을 만들었다.
조합으로 뽑은 세 개의 인덱스를 1로 만든 후 이때 바이러스가 얼마나 퍼지는지를 dfs로 계산했다.
그 후 안전영역 후보를 리스트에 넣어둔다.
이 작업을 모든 조합에 실시하고 이 중 가장 큰 안전영역 값을 출력한다.

소스코드

from itertools import combinations
import sys
input = sys.stdin.readline

def spreadable(next_x, next_y, n, m, VISITED):
    return 0 <= next_x < n and 0 <= next_y < m and new_map[next_x][next_y] == 0 and VISITED[next_x][next_y] == True


def dfs(n, m, new_map, VISITED):
    stack = []
    stack.append((i, j))

    while stack:
        x, y = stack.pop()
        VISITED[x][y] = False

        DELTAS = ((1, 0), (-1, 0), (0, 1), (0, -1))
        for dx, dy in DELTAS:
            next_x, next_y = x + dx, y + dy
            if spreadable(next_x, next_y, n, m, VISITED):
                new_map[next_x][next_y] = 2
                stack.append((next_x, next_y))


if __name__ == "__main__":
    n, m = map(int, input().strip().split())
    maps = [list(map(int, input().strip().split())) for _ in range(n)]
    blanks = []
    safe_section = []

    for i in range(n):
        for j in range(m):
            if maps[i][j] == 0:
                blanks.append((i, j))

    blank_combi = list(combinations(blanks, 3))

    for combi in blank_combi:
        new_map = list(map(list, maps))
        VISITED = [[True] * m for _ in range(n)]

        for x, y in combi:
            new_map[x][y] = 1

        for i in range(n):
            for j in range(m):
                if new_map[i][j] == 2 and VISITED[i][j] == True:
                    dfs(n, m, new_map, VISITED)

        zero_cnt = 0
        for row in new_map:
            zero_cnt += row.count(0)

        safe_section.append(zero_cnt)

    print(max(safe_section))


<프로그래머스가 직접! 이끌어주는 코딩테스트 대비반(Python)> 참여 후기

지난 2월, <프로그래머스가 직접! 이끌어주는 코딩테스트 대비반(Python)>에 5기로 참여했다.
상반기 취직을 목표로 하고 있던 터라 알고리즘 풀이 실력을 늘려야 한다는 생각을 하고 있었고, 마침 이 스터디를 발견해 신청했다.
참여 가격은 원가는 40만원 정도였는데 할인이 있어 32만원에 참여할 수 있었다.
이것처럼 프로그래머스에서 진행하는 온라인 스터디는 거의 초반에 할인을 하는 듯하다.

진행

스터디의 첫 세션은 2월 12일이었다.
세션이란 스터디 진행 동안 일주일에 한번 리더와 스터디 멤버들이 화상으로 모이는 자리이다.
이번엔 매주 수요일 8시부터 9시 쯤까지 진행했다.
이때 풀어야 했던 문제 중에 어려웠던 문제를 1~2문제 정도 설명해주시고, 큐엔에이를 받는다.
세션 외에는 매주 올라오는 문제를 푼다.
문제는 6~8문제 정도로, 프로그래머스 기준 LV1~LV3이 섞여서 나오고 가끔 LV4문제도 나오긴 한다.
프로그래머스에 올라와있는 문제가 많이 나오기 때문에, 이미 프로그래머스 문제를 많이 풀었다면 겹칠 수도 있겠다.

전체적인 문제 난이도는 쉽지는 않았던 것 같다.
LV3 문제가 꽤 나오기도 하고 LV2 문제들도 아주 쉽지는 않았다.
다만 난이도가 쉬웠다면 배우는 의미가 크지 않으므로 적절한 난이도였다고 생각한다.
문제를 풀면 코드를 깃허브에 커밋하고, 리더가 코드 리뷰를 해준다. 코드에서 pythonic 하지 않거나 효율적이지 않은 부분, 이상한 변수명 등을 지적해주시기 때문에 참고할 수 있다.
또한 이 과정에서 모르는 부분을 질문하거나 추정 시간 복잡도를 쓰면 여기에 답변을 해주시기도 한다.

한 주차가 끝나면 세션을 하기 전 날 매번 모의고사를 본다.
모의고사는 2시간 정도로 2~3문제가 출제된다. (거의 2문제였던 것 같다)
모의고사 난이도는 한 번 빼고는 그렇게 어렵지 않았던 것 같다.
그것도 내가 BFS/DFS를 어떻게 푸는지 몰랐기 때문에 더 어렵게 느꼈던 것 같다.
모의고사 문제도 코드리뷰를 해주신다.

이렇게 네 번 정도를 반복하면 한 달이 지나고, 스터디가 끝난다.

기대했던 점

저렴하지는 않은 가격인 만큼, 기대하는 점이 확실히 있기에 참여를 했다고 할 수 있다.
그 중 몇 가지를 말해보자면,

  1. pythonic한 코드를 짜고 싶다
  2. 전반적인 알고리즘 풀이 실력을 높이고 싶다
  3. 코드 리뷰를 경험하고 싶다
  4. 코딩 테스트에 익숙해지고 싶다
  5. 시간 복잡도 계산을 잘하고 싶다

이 정도였다.
기대했던 점이 얼마나 충족되었는지를 생각해 보면,

  1. 확실히 도움이 되었다. 사실 난 pythonic한 코드를 짜야 한다는 자각도 별로 없었기에, 첫 코드 리뷰에서 내 코드가 다른 언어의 색채가 짙다는 지적을 받았다. 그 뒤로 for문에서 range 사용을 줄이거나 변수명을 주의해서 작성
  2. 한 달은 알고리즘 풀이 실력이 급성장할만한 시간은 아니라고 생각한다. 따라서 실력 성장을 크게 체감하진 못했지만, 스터디가 끝난 뒤 알고리즘 문제를 풀면서 ‘늘긴 했다’고 확실히 느낄 수 있었다. 이전엔 풀지 못했던 BFS/DFS 문제를 어렵지 않게 풀거나 dictionary나 set을 편하게 쓸 때가 그랬다.
  3. 코드 리뷰는 잘 참여하지 못했다. 다른 사람의 풀이에 얼마든지 코드 리뷰를 할 수 있고 나도 받아보기도 했다. 하지만 남의 코드를 리뷰한다는 것은 내가 그 문제를 먼저 풀어봐야 한다는 말인데, 항상 문제를 늦게 풀었기에 참여가 어려웠다. 일찍 풀었어도 남 코드 읽는 것이 익숙하지 않았고 무슨 말을 해야할지도 모르겠는 상황이 이어지다 스터디가 끝났다.

이와 같은 점이 충족되었고, 전반적으로 만족한 스터디였다. 저렴한 가격은 아니지만 코드의 질을 높이고 싶다면 참여해볼만 하다.

[프로그래머스] LV2 : 짝지어 제거하기

문제: https://programmers.co.kr/learn/courses/30/lessons/12973

풀이

스택으로 풀이.
스택에 원소가 있고 s의 현재 알파벳과 스택 마지막 원소가 같다면 스택에서 pop을 해 짝지어 제거한다.
스택에 원소가 없거나 현재 알파벳과 스택 마지막 원소가 다르면 현재 알파벳을 스택에 집어 넣는다.
반복문이 끝나고 스택에 원소가 있다면 짝지어 제거하기가 실패했으므로 0을 반환, 아니면 1을 반환한다.

소스코드

def solution(s):
    stack = []
    
    for alphabet in s:
        if stack and alphabet == stack[-1]:
            stack.pop()
        else:
            stack.append(alphabet)
    
    if stack:
        return 0
    return 1

[프로그래머스] LV2 : 탑

문제: https://programmers.co.kr/learn/courses/30/lessons/42588

풀이

스택으로 풀이했다.
스택의 가장 위 원소가 heights 반복문에서 현재 높이보다 작거나 같으면 pop을 한다.
크다면 신호를 수신하는 탑일 것이므로 answer[i] 값을 스택 가장 위 원소의 인덱스로 바꾼다.
마지막으로는 매번 현재의 height와 인덱스를 stack에 append 해준다.

소스코드

def solution(heights):
    stack = []
    answer = [0 for _ in range(len(heights))]
    
    for i, height in enumerate(heights):
        while stack and height >= stack[-1][0]:
            stack.pop()
        
        if stack:
            answer[i] = stack[-1][1]

        stack.append((height, i + 1))
        
    return answer

[BOJ] 2178 : 미로 탐색 (Python3)

문제: https://www.acmicpc.net/problem/2178

풀이

bfs로 해결한 문제.
항상 도착위치로 이동할 수 있는 경우만 입력으로 주어지기 때문에 이중 반복문을 사용하지 않고 시작점((0, 0))만 큐에 넣어두고 시작했다.
또한 이동하는 다음 좌표의 값 (maze[next_x][next_y])을 바로 이전 좌표의 값(maze[x][y])에 1을 더한 값으로 바꾸게 해 바로 이동 칸 수를 알 수 있도록 했다.
다만 시작점(maze[0][0])이 다시 큐에 들어가는 상황을 막기 위해 movable 함수에 예외를 두게 했다.

소스코드

from collections import deque
import sys
input = sys.stdin.readline

def movable(x, y, n, m, maze):
    if x != 0 or y != 0:
        return 0 <= x < n and 0 <= y < m and maze[x][y] == 1
    return False

def bfs(maze, queue, n, m):
    while queue:
        x, y = queue.popleft()

        DELTAS = ((1, 0), (-1, 0), (0, 1), (0, -1))
        for dx, dy in DELTAS:
            next_x, next_y = x + dx, y + dy
            if movable(next_x, next_y, n, m, maze):
                queue.append((next_x, next_y))
                maze[next_x][next_y] = maze[x][y] + 1


n, m = map(int, input().strip().split())
maze = [[int(x) for x in input().strip()] for _ in range(n)]
queue = deque()
queue.append((0, 0))

bfs(maze, queue, n, m)
print(maze[n-1][m-1])

[BOJ] 2667 : 단지번호 붙이기 (Python3)

문제: https://www.acmicpc.net/problem/2667

풀이

  1. 입력값을 homes 배열에 받고, 이 배열을 이중 반복문을 이용해 [0][0]부터 [n][n] 까지 검사한다.
  2. 만약 해당 값 (homes[i][j])가 1이라면 그 값을 queue에 넣고 이미 방문했다는 의미에서 1(VISITED로 상수처리)을 더한다.
  3. queue에서 가장 앞에 있는 값을 뽑고 그 값의 상하좌우 값을 is_there_neighbor 함수로 검사한다.
  4. 단지를 이룰 수 있는 집이면 이미 방문했다는 의미로 1을 더하고 queue에 넣는다. cnt도 1 추가한다.
  5. 이런 식으로 한 단지의 검사가 끝나면 지금까지 계산한 cnt를 answers에 append 하고 새로운 단지를 찾는다.

소스코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
homes = [[int(x) for x in input().strip()] for _ in range(n)]

def is_there_neighbor(x, y, homes):
    return 0 <= x < n and 0 <= y < n and homes[x][y] == 1

def bfs(homes, queue, answers):
    cnt = 1
    while queue:
        x, y = queue.popleft()
        
        DELTAS = ((1, 0), (-1, 0), (0, 1), (0, -1))
        for dx, dy in DELTAS:
            next_x, next_y = dx + x, dy + y
            if is_there_neighbor(next_x, next_y, homes):
                homes[next_x][next_y] += VISITED
                cnt += 1
                queue.append((next_x, next_y))

    answers.append(cnt)

queue = deque()
answers = []
VISITED = 1

for i in range(n):
    for j in range(n):
        if homes[i][j] == 1:
            queue.append((i, j))
            homes[i][j] += VISITED
            bfs(homes, queue, answers)

print(len(answers))

answers.sort()
for answer in answers:
    print(answer)


[BOJ] 2108 : 통계학 (Python3)

문제: https://www.acmicpc.net/problem/2108

최빈값을 구하는 부분에서 가장 애를 먹었다.
처음에는 most_common 함수가 dict 형태를 return 하는 줄 알아서 두 번째로 작은 값을 어떻게 찾나 싶었는데, 알고보니 리스트 형태를 반환한다고 한다.
또한 같은 빈도를 갖는 경우 첫 번째 원소를 기준으로 알아서 정렬이 되는 것 같다.
그래서 어렵지 않게 답을 찾을 수 있었다.

(참고: 파이썬 공식 레퍼런스 문서)

소스코드

from collections import Counter
import sys

input = sys.stdin.readline

def mean(n, numbers):
    return round(sum(numbers) / n)

def median(n, numbers):
    return numbers[n // 2]

def mode(n, numbers):
    numbers_counter = Counter(numbers).most_common()
    if n > 1:
        if numbers_counter[0][1] == numbers_counter[1][1]:
            return numbers_counter[1][0]
    return numbers_counter[0][0]

def min_max(n, numbers):
    return numbers[-1] - numbers[0]

n = int(input())
numbers = [int(input()) for _ in range(n)]
numbers.sort()

print(mean(n, numbers))
print(median(n, numbers))
print(mode(n, numbers))
print(min_max(n, numbers))

[BOJ] 1181 : 단어 정렬 (Python3)

문제: https://www.acmicpc.net/problem/1181

풀이

풀면서 두 가지를 배웠다.

  1. 리스트에서 중복을 제거하려면 list(set(리스트 이름))을 하면 된다.
    (set에서 중복이 제거되기 때문. 이 문제에서는 정렬을 위해 리스트 형태가 필요하므로 다시 리스트로 만든다)
  2. 정렬시 길이순으로 먼저 정렬하고, 그 안에서 사전순으로 정렬하고 싶다면 key 함수의 return 값을 (len(x), x)로 주면 된다.

소스코드

import sys, collections
input = sys.stdin.readline

n = int(input())

vocas = list(set([input().strip() for _ in range(n)]))
vocas.sort(key=lambda x: (len(x), x))

for voca in vocas:
    print(voca)

[BOJ] 1931 : 회의실배정 (Python3)

문제: https://www.acmicpc.net/problem/1931

풀이

회의시간을 배열로 받아 끝나는 시간이 이른 것부터 정렬한다.
일찍 끝날수록 다른 회의를 많이 할 수 있기 때문이다.
다만 끝나는 시간이 같은 경우를 위해 시작 시간도 오름차순으로 정렬해야 한다.
(2, 2)
(1, 2)
처럼 회의가 배정되어있을 경우, 해당 순서로는 답이 1로 나오지만 순서가 바뀌면 2개 회의를 모두 열 수 있다.
이처럼 정렬한 뒤, 시작 시간이 채택한 회의 시간의 끝 시간보다 크거나 같은 경우 cnt += 1을 한다.
반복문이 끝나면 cnt를 출력한다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
times = [list((map(int, input().strip().split()))) for _ in range(n)]
times.sort(key=lambda x: [x[1], x[0]])

end_time = 0
cnt = 0

for x, y in times:
    if x >= end_time:
        cnt += 1
        end_time = y

print(cnt)

[BOJ] 11399 : ATM (Python3)

문제: https://www.acmicpc.net/problem/11399

풀이

작은 수가 앞쪽에 와야 뒷 사람들이 기다리는 시간이 적어지므로 작은 수부터 정렬한다.
반복문을 이용해 한 사람당 돈을 인출하는 시간과 전체 합을 구한다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
p = list(map(int, input().strip().split()))

p.sort()

waitng_time = 0
sum_time = 0

for i in range(n):
    waitng_time += p[i]
    sum_time += wating_time     

print(sum_time)

[BOJ] 11047 : 동전 0 (Python3)

문제: https://www.acmicpc.net/problem/11047

풀이

arr은 오름차순으로 나열되었으므로 뒤에 있는 수에서 반복문을 시작한다.
해당 원소가 k보다 작거나 같다면, 이 동전을 사용할 수 있다.
k원을 해당 원소로 나눈 몫을 구한다. 그것이 동전 개수가 되기에 cnt에 더한다.
k에서 동전 개수와 해당 원소(가격)를 곱한 값을 뺀다.

k가 0이 되면 더이상 계산할 필요가 없으므로 반복문을 중지한다.

소스코드

import sys
input = sys.stdin.readline

n, k = map(int, input().strip().split())
arr = [int(input()) for _ in range(n)]
cnt = 0

for i in range(1, n+1):
    if arr[n-i] <= k:
        cnt += k // arr[n-i]
        k -= arr[n-i] * (k // arr[n-i])

    if k == 0:
        break

print(cnt)


[BOJ] 1912 : 연속합 (Python3)

문제: https://www.acmicpc.net/problem/1912

풀이

dp 배열을 만들어 i번째 원소에 해당 원소를 마지막으로 하는 가장 큰 연속합을 저장한다.
dp의 가장 최근 원소와 순서가 되는 lst[i] 원소를 더하면 새로운 연속합이 만들어진다. (lst[0]은 dp에 원소가 없으므로 미리 추가해둠)
그러나 이것이 가장 큰 연속합이 되지 않는 경우가 있다.
dp[-1] + lst[i]가 음수일 경우, 자기 자신이 더 큰 연속합이 된다.

때문에 dp에는 dp[-1] + lst[i]와 lst[i] 중 최댓값을 추가한다.
dp 배열에 있는 수 중 max 값을 찾으면 가장 큰 연속합을 구할 수 있다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
lst = list(map(int, input().strip().split()))
dp = [lst[0]]

for i in range(1, n):
    dp.append(max(dp[-1] + lst[i], lst[i]))

print(max(dp))

[BOJ] 2565 : 전깃줄 (Python3)

문제: https://www.acmicpc.net/problem/2565

풀이

A1과 B1이 연결되고 A2와 B2가 연결되었다고 가정할 때, 전깃줄이 교차하는 경우는 A1 > B1 and A2 < B2 혹은 A1 < B1 and A2 > B2 일 경우이다.
즉, A를 1에서 10으로 순서대로 놓을 때 B가 순서대로 위치하지 않으면 전깃줄이 교차된다.
반대로 B가 순서대로 위치한다면 전깃줄이 교차되지 않을 것이다.
교차되지 않을 전깃줄의 최대 개수를 구하면, 없애야 하는 전깃줄의 최소 개수를 쉽게 구할 수 있다. n에서 전자를 빼면 된다.

그렇다면 교차되지 않는 전깃줄의 최대 개수를 어떻게 구해야 할까?
전깃줄의 위치를 2차원 배열로 받은 뒤, A 순서에 따라 정렬한다.
그리고 B 원소 각각의 가장 긴 증가하는 부분 수열 개수를 구한다.

n에서 가장 큰 부분 수열 개수를 뺀 값이 답이 된다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
line = [list(map(int, input().strip().split())) for _ in range(n)]
line.sort(key = lambda x:x[0])

dp = [0]*n

for i in range(n):
    for j in range(i):
        if line[i][1] > line[j][1]:
            dp[i] = max(dp[i], dp[j])
    dp[i] += 1

print(n - max(dp))

[BOJ] 11054 : 가장 긴 바이토닉 부분 수열 (Python3)

문제: https://www.acmicpc.net/problem/11054

풀이

바이토닉 수열은 ‘증가하는 부분 + 기준점 + 감소하는 부분’으로 나뉠 수 있다.
그렇다면 dp1 배열에는 i까지 증가하는 부분 수열의 길이를 담고, dp2 배열에는 뒤에서부터 i까지 감소하는 부분 수열의 길이를 담는다.
이 두 수열의 원소를 더하면 증가하는 부분 수열과 감소하는 부분 수열이 더해진 바이토닉 수열의 길이를 알 수 있다.
다만 기준점이 각각 포함되어 두 번 더해졌으므로 -1을 한다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().strip().split()))
dp1 = [0 for i in range(n)] # 증가하는 부분 수열
dp2 = [0 for i in range(n)] # 감소하는 부분 수열
ans = [0 for i in range(n)] # dp1 + dp2를 저장할 배열

for i in range(n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp1[i] = max(dp1[j], dp1[i])
    dp1[i] += 1

for i in range(n-1, -1, -1):
    for j in range(n-1, i, -1):
        if arr[i] > arr[j]:
            dp2[i] = max(dp2[j], dp2[i])
    dp2[i] += 1

for i in range(n):
    ans[i] = dp1[i] + dp2[i] -1

print(max(ans))

[BOJ] 11053 : 가장 긴 증가하는 부분 수열 (Python3)

문제: https://www.acmicpc.net/problem/11053

풀이

dp 배열에 dp[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 원소 개수를 저장한다.
이중 반복문에서 arr[i]가 arr[j]보다 클 때, dp[j] 값 역시 dp[i] 값보다 더 크다면 dp[i]를 dp[j]로 바꿔준다. j 반복문이 끝나고 dp[i] 값이 확정되었다면 부분 수열에 추가 되었으므로 1을 더해준다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().strip().split()))
dp = [0 for i in range(n)]

for i in range(n):
    for j in range(i):
        if arr[j] < arr[i] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

print(max(dp))

[BOJ] 2579 : 계단 오르기 (Python3)

문제: https://www.acmicpc.net/problem/2579

풀이

stair 배열에는 계단의 점수를 받는다.
dp 배열에는 i번째 계단까지 왔을 때 최대가 되는 점수의 합을 저장한다.

조건 3에 따라 마지막 계단(=i번째)을 반드시 밟아야하므로, i번째 계단을 밟았다고 가정해보자.
그렇다면 i-1 계단 혹은 i-2 계단을 밟았을 것이다. (조건2에 따라 둘을 한번에 밟을 수는 없다)
그런데 i-1 계단을 밟았다면 i-3 계단도 반드시 밟아야 한다. i-3을 밟지 않으면 조건1에 위반되기 때문이다.
때문에 dp[i]에 올 값은 stair[i] + dp[i-2]와 stair[i] + stair[i-1] + dp[i-3] 중 최댓값이다.
즉, (현재 계단의 점수 + 두 칸 이전 계단까지의 점수 최댓값)과 (현재 계단의 점수 + 바로 전 계단의 점수 + 세 칸 이전 계단까지의 점수 최댓값) 중 더 큰 값이다.

다만 i < 3 일 때는 위의 계산이 성립하지 않으므로 따로 값을 넣어둔다.
0번 계단은 하나 뿐이므로 stair[0]이고, 1번 계단은 stair[0]+stair[1]일 것이다. 2번 계단은 3칸 연속 밟을 수 없으므로 stair[0]과 stair[2]를 더한 값, stair[1]과 stair[2]를 더한 값 중 최댓값이 들어가야 한다.

이렇게 계단의 개수만큼 dp 배열을 다 채웠으면 그 중 가장 마지막 원소가 최종적인 최댓값이 된다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
stair = [int(input()) for _ in range(n)]
dp = []

dp.append(stair[0])
dp.append(stair[0] + stair[1])
dp.append(max(stair[0] + stair[2], stair[1] + stair[2]))

for i in range(3, n):
    dp.append(max(stair[i] + dp[i-2], stair[i] + stair[i-1] + dp[i-3]))

print(dp[-1])

[BOJ] 1932 : 정수 삼각형 (Python3)

문제: https://www.acmicpc.net/problem/1932

풀이

삼각형을 2차원 배열로 입력받은 뒤, 2번째 행부터 그 전 행의 숫자를 축적하며 더한다.
수의 합이 최대가 되어야하므로, 대각선 왼쪽 또는 오른쪽에 있는 수 중에 최댓값만 더하면 된다.
다만 첫번째 열과 마지막 열은 대각선에 있는 수가 하나밖에 없으므로 예외처리를 해준다.
모두 계산했으면 배열의 마지막 행에서 최댓값을 출력해준다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
tri = []

for _ in range(n):
    tri.append(list(map(int, input().strip().split())))

for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            tri[i][0] += tri[i-1][0]
        elif j == i:
            tri[i][j] += tri[i-1][j-1]
        else:
            tri[i][j] += max(tri[i-1][j], tri[i-1][j-1])

print(max(tri[n-1]))

[BOJ] 1149 : RGB거리 (Python3)

문제: https://www.acmicpc.net/problem/1149

풀이

입력을 arr에 2차원 배열로 받는다.
arr[1] 행의 각 열에 arr[0] 행의 최솟값을 더한다. (자신의 열은 제외)
arr[2] 행의 각 열에 arr[1] 행의 최솟값을 더한다. arr[1]은 이미 두 값이 더해져있으므로 arr[2]에는 최솟값 후보가 되는 세 값이 모두 더해져 있을 것이다.
이런 식으로 arr[n-1] 행까지 값을 모두 더한 후, arr[n-1] 행의 세 값 중 최솟값을 구하면 된다.

이전 행의 값을 저장해두었다가 다시 사용한다는 점에서 다이나믹 프로그래밍으로 해결하는 문제라고 할 수 있다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int, input().strip().split())))

for i in range(1, n):
    arr[i][0] += min(arr[i-1][1], arr[i-1][2])
    arr[i][1] += min(arr[i-1][0], arr[i-1][2])
    arr[i][2] += min(arr[i-1][0], arr[i-1][1])

print(min(arr[n-1][0], arr[n-1][1], arr[n-1][2]))

[BOJ] 1904 : 01타일 (Python3)

문제: https://www.acmicpc.net/problem/1904

풀이

N=1, (1) - 1개
N=2, (00, 11) - 2개
N=3, (001, 100, 111) - 3개
N=4, (0011, 0000, 1001, 1100, 1111) - 5개

이전에 만들어둔 타일에 00을 붙이거나 1을 붙임으로써 새 타일을 만들 수 있다.
그러나 i번째 타일을 만든다고 하면, i-1번째 타일에 00을 붙일 수는 없다.
그러므로 i-2번째 타일에 00을 붙이고, i-1번째에는 1을 붙여야 한다.
00과 1을 붙여도 개수는 변함이 없다.
따라서 i번째 타일의 가짓수 = (i-2번째 타일의 가짓수) + (i-1번째 타일의 가짓수) 라는 식이 나온다.

dp[i] = dp[i-2] + dp[i-1]

문제에서 요구한 것처럼 개수를 15746으로 나눈 나머지를 출력해야 하는데, 주의할 점은 결과값만을 나누어줘선 안된다.
n=1000000일 경우 많은 메모리를 차지하기 때문에 반복문 안에서 미리 나머지 연산을 해주는 것이 필요하다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 1000001
dp[1], dp[2] = 1, 2

for i in range(3, n+1):
	dp[i] = (dp[i-1] + dp[i-2]) % 15746

print(dp[n])

[BOJ] 1003 : 피보나치 함수 (Python3)

출처: https://www.acmicpc.net/problem/1003

문제

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

  • fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
  • fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
  • 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
  • fibonacci(0)은 0을 출력하고, 0을 리턴한다.
  • fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
  • 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
  • fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다. 1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

풀이

N=0일 때 0이 1번 출력된다.
N=1일 때 1이 1번 출력된다.
N=2일 때 fibonacci(0) 호출회수 + fibonacci(1)이 호출회수, 0이 1번, 1이 1번 출력된다.
N=3일 때 fibonacci(1) 호출회수 + fibonacci(2)가 호출회수, 0이 1번, 1이 2번 출력된다.

여기서 알 수 있는 것은, 피보나치 함수의 호출 회수도 피보나치 수열을 따르고 있다는 것이다.
그러므로 이를 해결하기 위해서는 0과 1의 호출 회수를 따로 배열에 저장한 뒤, 반복문으로 피보나치 수열을 만들어야 한다.

소스코드

import sys
input = sys.stdin.readline

t = int(input())
f0 = [1, 0]  # f0[n] 은 fibonacci(n)에서 0이 출력된 횟수
f1 = [0, 1]

def cal(n):
	length = len(f0)
	if n >= length:
		for i in range(length, n+1):
			f0.append(f0[i-1] + f0[i-2])
			f1.append(f1[i-1] + f1[i-2])
	print(f0[n], f1[n])

for i in range(t):
	n = int(input())
	cal(n)

[BOJ] 2748 : 피보나치 수 2 (Python3)

문제: https://www.acmicpc.net/problem/2748

풀이

다이나믹 프로그래밍으로 해결한 피보나치 수열 문제.
DP는 큰 문제를 작은 문제로 쪼개어 해결하는 방법이다. 작은 문제를 풀다보면 반복하는 풀이가 생기는데, 그것을 매번 재계산하지 않고 값을 저장해두었다가 사용하는 방법이다.
때문에 재귀에 비해 시간 복잡도가 낮다.

소스코드

n = int(input())
arr = [0 for i in range(n+1)]
arr[1] = 1

for i in range(2, n+1):
	arr[i] = arr[i-1] + arr[i-2]

print(arr[n])

'생활코딩 웹브라우저와 자바스크립트' 공부하면서 정리

생활코딩 웹브라우저와 자바스크립트 강의를 들으며 정리한 내용입니다.

웹브라우저와 JavaScript

html이 무엇이냐? 정보 자체. 인터넷의 역사를 놓고 봤을 때 웹이 등장했을 때 초창기의 모습. 웹 브라우저가 있고 웹서버가 있었음. 웹서버가 하는 역할은 정보를 저장하고 있다 브라우저의 요청에 따라 정보를 전달.

html: 정보 css: 디자인 JavaScript: 웹브라우저, html을 프로그래밍적으로 제어

Object Model

자바스크립트로 브라우저를 제어하려면 자바스크립트로 제어할 수 있는 것이 있어야 함. 그것이 바로 object. 자바스크립트로 제어할 수 있도록 브라우저의 여러 구성요소를 객체로 제공.
object 모델은 테두리 같은 역할. 자바스크립트로 브라우저를 제어하기 위해 객체를 만드는 것은 무슨 의미?

이미지가 있는 문서. 프로그래밍적으로 이것을 제어하려면 이미지 태그가 자바스크립트로 제어 가능한 형태, object여야 한다. 이 object를 누가 만듦? 브라우저에서 각각의 태그들마다 미리 객체를 만들어놓고 준비. 그 태그에 해당되는 객체를 찾아 메소드 값 등을 가져옴.

이미지 태그를 제어하고 싶다면 이미지 태그에 해당하는 객체를 가져와야 함.
브라우저가 갖고 있는 객체에는 document가 있음. 이건 getElemetsByTagName이라는 메소드가 있다.
여기에 인자로 img를 가져와 return.
배열로 return된다. 이를 가져오기 위해서는 imgs[0] 이미지 태그를 의미하는 객체를 가져옴.
imgs[0].style 이 객체가 가지고 있는 style이라는 property를 의미.

window 객체는 크게 전역객체, 또는 window나 frame과 같은 제어하기 위한 객체. 이 window 객체가 가지고 있는 property 중 중요한 것이 document.
앞에 window를 쓰는 것과 쓰지 않는 것은 같은 의미.
window.document

BOM은 Brower Object Model. 현재 웹페이지가 가리키는 url을 알아낸다거나 경고창을 띄우거나 하는 것을 담당. window 객체의 property에 저장되어 있다. document처럼 window 객체의 property. document는 문서를 제어하는 중요한 역할을 하는 객체가 담겨있기에 이 property는 별도로 dom이라는 분류를 씀.

또 다른 property로 javascript core가 있음. js는 이것으로 브라우저나 node.js와 같은 서버측 자바스크립트를 제어할 수 있음. 이것들은 바로 브라우저라는 호스트 환경에서는 존재하는 객체들. 그런데 각각의 언어를 제어하는 공통적인 언어는 자바스크립트. js가 자체적으로 가지고 있는 객체가 존재. array, function, date 등. js core에 해당하는 객체들은 호스트 환경이 무엇이건 공통적으로 가지고 있음.

BOM

Browser Object Model. 웹브라우저를 제어하기 위해 브라우저가 제공하는 객체들. 자바스크립트를 통해 브라우저의 새 창을 열거나 현재 창의 url을 알아내는 등을 할 수 있게 도와줌.

전역객체 window

브라우저의 내장함수는 사실 앞에 window.이 붙어있는 것과 같음.

사용자와 커뮤니케이션 하기

  • alert 경고창은 사용자에게 정보를 제공하거나 경고, 변수에 담겨있는 값 등을 확인할 때 사용. 경고창을 한번 실행하면 확인을 누르기 전까지 다음 로직이 실행되지 않음.
    경고창을 디버깅 용도로 많이 썼지만 요즘 디버깅을 할 때는 개발자 도구가 있고 console.log를 많이 씀.

  • confirm 컨펌창을 띄워줌. 확인을 누르면 true 리턴, 취소하면 false 리턴.

  • prompt 사용자가 입력한 값을 받아 JS가 얻어낼 수 있는 기능.

Location 객체

현재 브라우저 창의 열려있는 문서의 url을 알려주는 객체.
url을 알아내는 방법은 크게 두 가지
console.log(location.toString(), location.href);
첫번째 출력된 것은 toString이라 했을 때 출력된 결과. 두번째는 href라는 property에 접근했을 때 출력한 결과.
console.log(location);
로케이션 객체에 대한 정보를 보여줌.

url의 정보를 의미에 따라 조각내야 하는 경우가 있음. console.log(location.protocol);
http:가 출력됨. 통신규약.
console.log(locaiton.protocol) 을 입력하면 https:가 출력됨. https라는 프로토콜을 사용하고 있기 때문.
console.log(location.host): 호스트가 출력됨.
console.log(location.port): 소프트웨어를 식별하는 번호인 포트가 출력됨.
console.log(location.pathname): 웹서버가 가진 정보 중 구체적인 정보를 요청.
console.log(location.search)

  • url 변경하기 location.href = "http://egoing.net";
    현재 문서를 다른 문서로 이동.
    location.reload() : 웹페이지 리로드

cross browsing.
세상엔 다양한 브라우저가 있음. 이들의 동작방식은 w3c에서 나온 표준화 기구의 스펙에 따라 만들어짐. 업체마다 스펙에 나온 것은 비슷하게 하지만 디테일한 것은 각자의 전략에 맞춰 구현. 브라우저마다 코드가 다르게 구현될 가능성. 이것을 가능하게 해주는 것이 navigator라는 객체.
브라우저 전쟁이 일어나게 됨. Netscape에서는 .addEventListener를 ㅆ는데 ie에서는 attachEvent를 씀. 그래서 웹표준이 생긴다. 그 중심에 navigator라는 객체가 있다.

Navigator 객체가 갖고 있는 property 중 appName

  • console.dir(navigator.appName);
    파이어폭스는 Netscape가 나옴 (계승했기 때문). 크롬도 Netscape가 나옴.
  • console.dir(navigator.appVersion); AppleWebkit - 크롬이 사용하고 있는 레이아웃 엔진.

기능 테스트

Navigator는 브라우저 호환서으 ㄹ위해 주로 사용되지만 모든 브라우저에 대응하는 것은 쉽지 않음. 그래서 기능 테스트를 사용하는 것이 더 선호되는 방법이다.
과거에 만들어진 브라우저는 Object.keys라는 메소드가 존재하지 않음. 그래서 이것을 알려면

if (!Object.keys) {
  Object.keys = (function () {

이런 식으로 코드를 작성해 호환성을 맞춘다.

창 제어

window.open 메소드는 새 창을 생성함.

  • 첫번째 인자는 새 창에 로드할 문서의 url window.open('demo2.html');
  • 두 번째 인자는 새 창의 이름. _self는 스크립트가 실행되는 창 window.open('demo2.html', '_self');
  • _blank는 새 창을 의미 window.open('demo2.html', '_blank');
  • 세 번째 인자는 새 창의 모양과 관련된 속성이 옴
    window.open('demo2.html', '_blank', 'width=200, resizable=yes'); 보안상 옵션은 제한하는 경우가 있음.

HTML Element

<script>
    var li = document.getElementById('active');
    console.log(li.constructor.name);
    var lis = document.getElementsByTagName('li');
    console.log(lis.constructor.name);
</script>

실행결과

HTMLLIElement 
HTMLCollection
  • document.getElementById : 리턴 데이터 타입은 HTMLElement
  • document.getElementsByTagName : 리턴 데이터 타입은 HTMLCollection

Dom tree

모든 엘리먼트는 HTMLElement의 자식.
HYMLElement는 Element의 자식이고 Element는 Node의 자식. Node는 Object의 자식. 이러한 관계를 DOM Tree라고 함.

HTML Collection

리턴 결과가 복수인 경우 사용하게 되는 객체.
그 객체를 제거하게 되면 html에서는 제거한 순간 반영이 된다.

[BOJ] 12015 : 가장 긴 증가하는 부분 수열 2 (Python3)

문제: https://www.acmicpc.net/problem/12015

풀이

가장 긴 증가하는 부분 수열이 뭔지, 그리고 그것을 어떻게 이진탐색으로 풀어야할지 이해가 되지 않아 풀기 힘들었던 문제이다.

결국 다른 풀이를 참고해 아래와 같이 소스코드를 작성했다.

  1. 해당 수열을 넣어둘 ans 배열에 미리 최솟값 0을 넣어둔다. (arr의 원소보다 작은 수)
  2. 반복문으로 arr[i]가 ans의 가장 마지막 값보다 크다면 ans에 그 값을 넣어준다.
  3. 만약 작다면, bisect_left로 나오는 자리를 arr[i]로 바꿔준다.
  4. 반복문이 다 끝나면 ans의 길이에서 -1 한 값을 return한다. (처음에 0을 추가했으므로)

소스코드

import sys, bisect
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().strip().split()))
ans = [0]

def solution():
    for i in range(n):
        if arr[i] > ans[-1]:
            ans.append(arr[i])
        elif arr[i] < ans[-1]:
            num = bisect.bisect_left(ans, arr[i])
            ans[num] = arr[i]
    return len(ans)-1

print(solution())

참고

https://jason9319.tistory.com/113 https://shoark7.github.io/programming/algorithm/3-LIS-algorithms#5

[BOJ] 1654 : 랜선 자르기 (Python3)

출처: https://www.acmicpc.net/problem/2805

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

소스코드

import sys
input = sys.stdin.readline

k, n = map(int, input().strip().split())
arr = [int(input()) for _ in range(k)]

# 랜선의 길이를 받아 만들 수 있는 랜선의 개수를 return하는 함수
def lanCount(mid):
    cnt = 0
    for i in range(k):
        cnt += (arr[i] // mid)
    return cnt

def binarySearch(n):
    start = 1
    end = arr[-1]
    while start <= end:
        mid = (start + end) // 2
        cnt = lanCount(mid)
        if cnt < n: # 만약 만들 수 있는 개수가 만들어야 하는 개수보다 적으면
            end = mid - 1 # 랜선의 길이를 줄여 더 많이 만들어야 함
        elif cnt >= n: # 더 크면 정답 후보이므로
            ans = mid # 정답 저장
            start = mid + 1 # 랜선의 길이를 늘일 여지가 있으므로
    return ans

arr.sort()
print(binarySearch(n))

풀이

역시 파라메트릭 서치를 이용해서 해결한 문제.

2805번 문제와 비슷하게 end를 arr[-1] - 1로 두고 풀었더니 ‘틀렸습니다’가 떴다.
생각해보니 랜선의 최대 길이가 arr에서 가장 큰 수일 때 k=1이 나오므로 이또한 정답 범위에 포함되어야 했다.
이 부분을 수정하니 정답이 되었다.

[BOJ] 1300 : K번째 수 (Python3)

출처: https://www.acmicpc.net/problem/1300

문제

세준이는 N*N크기의 배열을 만들었다. (배열의 방 번호는 1부터 시작한다.)

그 배열을 A라고 했을 때, 배열에 들어가는 수는 A[i][j] = i*j 이다.

세준이는 이 수를 일차원 배열 B에 넣으려고 한다. 그렇게 되면, B의 크기는 N*N이 될 것이다. 그러고 난 후에, B를 오름차순 정렬해서 k번째 원소를 구하려고 한다.

N이 주어졌을 때, k번째 원소를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(109, n2)보다 작거나 같은 자연수이다.

출력

k번째 원소를 출력한다.

풀이

N*N 배열을 일차원 배열로 정렬했을 때, k번째 수를 구하는 문제.
임의의 숫자 x를 두고 x보다 작거나 같은 수의 개수가 k와 비슷할 때까지 이진 탐색을 한다.
그러면 x보다 작거나 같은 수의 개수를 어떻게 구하는가?
배열에 수가 i*j 로 들어있으므로 i행에 속한 숫자들은 모두 i의 배수.
때문에 x를 i로 나누어주고 그 몫이 i 행에서 x보다 작은 수의 개수가 된다.
다만 한 행에서 나올 수 있는 개수가 n보다 클 수 없기 때문에 x//i와 n 중 최솟값을 취해야 한다.

이렇게 x가 몇 번째 수인지를 구해 k보다 크고 가장 가까운 수를 답으로 한다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())

# mid 보다 작은 수의 개수를 return하는 함수
def numCount(mid):
    cnt = 0
    for i in range(1, n+1):
        cnt += min(mid//i, n)
    return cnt

def binarySearch(k):
    start = 1
    end = k
    while start <= end:
        mid = (start + end) // 2
        num = numCount(mid)
        if num < k:
            start = mid + 1
        elif num >= k:
            ans = mid
            end = mid - 1
    return ans

print(binarySearch(k))

[BOJ] 2805 : 나무 자르기 (Python3)

출처: https://www.acmicpc.net/problem/2805

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다)

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 넘기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

소스코드

import sys
input = sys.stdin.readline

n, m = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))

# 절단기 높이를 h라 했을 때 가져갈 수 있는 총 나무의 길이를 return하는 함수
def treeLenghth(h):
    ans = 0
    for i in range(n):
        if arr[i] > h:
            ans += arr[i] - h
    return ans

# 절단기 높이의 최댓값을 구하는 함수
def BinarySearch(m):
    start = 0
    end = arr[-1] - 1
    while start <= end:
        mid = (start + end) // 2 # mid가 절단기의 높이가 된다
        tree = treeLenghth(mid)
        if tree < m: # 만약 가져갈 수 있는 나무 길이가 m보다 작으면 (나무길이가 부족하면)
            end = mid - 1  # 절단기의 높이를 줄여 나무를 더 가져갈 수 있게 한다
        else: # 가져갈 수 있는 나무 길이가 m보다 크거나 같다면 정답 후보이므로
            start = mid + 1
            ans = mid
    return ans

arr.sort()
print(BinarySearch(m))

풀이

2110번과 비슷하게 파라메트릭 서치를 이용해서 해결한 문제.

아래와 같은 흐름으로 문제를 해결했다.

  1. 절단기의 최소 높이는 0이고, 최대 높이는 가장 큰 나무 길이 - 1 이다. (m이 1 이상이므로)
  2. 1번을 통해 중간값(mid)을 구한다. 이를 이용해 이진 탐색을 진행한다.
  3. 해당 mid 값에서 구할 수 있는 나무의 길이를 tree 변수에 저장한다.
  4. tree가 m보다 작으면 절단기의 높이를 줄인다. m보다 같거나 크면 정답이 될 수 있으므로 ans 변수에 저장하고 절단기의 높이를 키워본다.
  5. 가장 적절한 ans 값을 return 한다.

[BOJ] 2110 : 공유기 (Python3)

출처: https://www.acmicpc.net/problem/2110

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, …, xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

소스코드

import sys
input = sys.stdin.readline

n, c = map(int, input().strip().split())
arr = [int(input()) for _ in range(n)]

# 간격에 따라 설치 가능한 공유기의 개수를 return하는 함수
def routerCnt(mid):
    baseCase = arr[0]
    cnt = 1 # 설치할 공유기 수를 담는 변수. 기본적으로 baseCase에 먼저 설치하므로 1에서 시작한다
    for i in range(1, n):
        if arr[i] - baseCase >= mid: # arr[i] 의 간격이 더 넓으면 설치 가능
            cnt += 1
            baseCase = arr[i]
    return cnt

# 가장 인접한 공유기 사이 최대 거리를 return하는 함수
def BinarySearch(c):
    start = 1
    end = arr[-1] - arr[0] # 최대 간격은 가장 큰 좌표에서 가장 작은 좌표를 뺀 것
    while start <= end:
        mid = (start + end) // 2 # mid가 간격이 된다
        router = routerCnt(mid)
        if router < c: # 이 간격에서 설치되는 공유기의 수가 c보다 작다면
            end = mid - 1 # 간격을 좁혀야 한다
        elif router >= c: # 크거나 같다면
            ans = mid  # 정답 후보이므로 ans에 값을 저장해두고
            start = mid + 1 # 간격을 넓혀야 한다.
    return ans

arr.sort()
print(BinarySearch(c))

풀이

이진 탐색을 응용한 파라메트릭 서치를 이용해서 해결한 문제.
배열의 특정한 값을 찾는 이진 탐색과는 다르게 내가 원하는 조건을 만족하는 알맞은 값을 찾는 것이 파라메트릭 서치이다.

BinarySearch 함수 끝 부분에 router == c 인 경우를 따로 뺐다가 자꾸 런타임 에러가 나서 고민했다.
다른 케이스를 적용해보니 항상 router가 c와 같은 수가 되었을 때 반복문이 끝나는 것이 아니었다.
설치할 수 있는 공유기 개수가 c보다 많더라도 여기서 몇 개를 설치하지 않으면 되기에, router > c 일 때도 답이 될 수 있었고 위와 같은 형태로 풀이를 작성했다.

[BOJ] 1920 : 수 찾기 (Python3)

출처: https://www.acmicpc.net/problem/1920

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
numN = list(map(int, input().strip().split()))
m = int(input())
numM = list(map(int, input().strip().split()))

def BinarySearch(target, list):
    lower = 0
    upper = len(list) - 1
    while lower <= upper:
        mid = (lower + upper) // 2
        if list[mid] < target:
            lower = mid + 1
        elif list[mid] > target:
            upper = mid - 1
        else:
            return True
    return False

numN.sort()
for i in range(m):
    if BinarySearch(numM[i], numN):
        print(1)
    else:
        print(0)

풀이

이분 탐색으로 해결한 문제.
처음에는 index를 두고 target의 index를 가리킬 때 True를 return하도록 코드를 짰지만 필요 없다는 것을 알고 지웠다.

'브라우저는 어떻게 동작하는가?' 공부하면서 정리

Naver D2에 올라온 번역글 ‘브라우저는 어떻게 동작하는가?’를 읽으면서 정리한 내용입니다.
출처: https://d2.naver.com/helloworld/59361

크롬, 파이어폭스, 사파리와 같은 오픈소스 브라우저의 예

브라우저의 주요 기능

  • 사용자가 선택한 자원을 서버에 요청하고 브라우저에 표시하는 것
  • 자원은 보통 html 문서이지만 pdf나 이미지일 수도 있다
  • 자원의 주소는 URI(Uniform Resource Identifier)에 의해 정해진다
  • 브라우저는 html과 css 명세에 따라 html을 해석해 표현. 예전에는 브라우저들이 독자적인 방법으로 해석해 호환성 문제가 있었지만, 최근에는 대부분 브라우저가 표준 명세를 따름.
  • 브라우저의 사용자 인터페이스는 서로 비슷

브라우저의 기본 구조

  • 사용자 인터페이스: 주소 표시줄, 이전/다음 버튼 등. 요청한 페이지를 보여주는 부분 외 전부
  • 브라우저 엔진: 사용자 인터페이스와 렌더링 엔진 사이 동작 제어
  • 렌더링 엔진: 요청한 컨텐츠를 표시
  • 통신: HTTP 요청과 같은 네트워크 호출에 사용
  • UI 백엔드: 콤보 박스와 창 같은 기본적인 장치를 그림
  • 자바스크립트 해석기: 자바스크립트 코드를 해석하고 실행
  • 자료 저장소: 자료를 저장하는 계층. HTML5 명세에는 브라우저가 지원하는 ‘웹 데이터 베이스’가 정의됨

렌더링 엔진

렌더링 엔진들

파이어폭스와 크롬, 사파리는 두 종류의 렌더링 엔진으로 제작됨. 파이어폭스는 모질라에서 만든 Gecko 엔진을 사용하고 크롬은 Webkit 엔진을 사용함.

동작 과정

렌더링 엔진은 통신으로부터 요청한 문서의 내용을 얻는 것으로 시작. 렌더링 엔진의 기본 동작 과정

  • DOM 트리 구축 위한 HTML 파싱
  • 렌더 트리 구축
  • 렌더 트리 배치
  • 렌더 트리 그리기

렌더링 엔진은 html 문서를 파싱하고 “콘텐츠 트리” 내부에서 태그를 dom 노드로 변환. 그 다음 외부 css 파일과 함께 포함된 스타일 요소도 파싱. 스타일 정보와 html 표시 규칙은 “렌더 트리”라 불리는 또 다른 트리 생성

렌더 트리는 색상 또는 면적과 같은 시각적 속성이 있는 사각형을 포함하고 있는데 정해진 순서대로 화면에 표시된다.

렌더 트리 생성이 끝나면 배치 시작. 노드가 화면의 정확한 위치에 표시됨.

파싱과 DOM 트리 구축

파싱 일반

문서 파싱은 브라우저가 코드를 이해하고 사용할 수 있는 구조로 변환하는 것. 파싱 결과는 보통 문서 구조를 나타내는 노드 트리. parsing tree, syntax tree라고도 함.

문법

파싱할 수 있는 모든 형식은 정해진 용어와 구문 규칙에 따라야 한다. 이것을 문맥 자유 문법이라고 함.

파서-어휘 분석기 조합

파싱은 어휘 분석과 구문 분석 두 가지로 구분할 수 있다.
어휘 분석은 자료를 토큰으로 분해하는 과정. 토큰은 유효하게 구성된 단위의 집합체.
구문 분석은 언어의 구문 규칙을 적용하는 과정.
파서는 보통 두 가지 일을 함. 자료를 유효한 토큰으로 분해하는 어휘 분석기와 언어 규칙에 따라 문서 구조를 분석함으로써 파싱 트리를 생성하는 파서. 어휘 분석기는 공백과 줄 바꿈 같은 의미 없는 문자를 제거.
파싱 과정은 반복됨.
규칙에 맞지 않으면 파서는 토큰을 내부적으로 저장하고 토큰과 일치하는 규칙이 발견될 때까지 요청. 맞는 규칙이 없는 경우 예외로 처리하는데 이는 문서가 구문 오류를 포함하고 있다는 것.

변환

파싱은 보통 문서를 다른 양식으로 변환하는데 컴파일이 하나의 예. 컴파일러는 파싱 트리 생성 후 이를 기계 코드 문서로 변환한다.

파서의 종류

하향식 파서와 상향식 파서. 하향식은 구문의 상위 구조로부터 일치하는 부분을 찾기 시작하고 상향식 파서는 낮은 수준에서 점차 높은 수준으로 찾는다.

파서 자동 생성

파서를 생성해주는 도구가 파서 생성기.
웹킷은 두 개의 파서 생성기 - 어휘 생성을 위한 Flex와 파서 생성을 위한 Bison 사용. 플렉스는 토큰의 정규 표현식 정의를 포함하는 파일을 입력받고 바이슨은 BNF 형식의 언어 구문 규칙을 입력 받음.

HTML 파서

HTML 마크업을 파싱 트리로 변환
모든 전통적인 파서는 HTML에 적용할 수 없음. 다만 파싱은 css와 자바스크립트를 파싱하는데 사용됨.
HTML 정의를 위한 공식적인 형식으로 DTD(문서 형식 정의)가 있지만 이것은 문맥 자유 문법이 아님.

HTML DTD

HTML의 정의는 SGML 계열 언어의 정의를 이용한 것.
DTD는 여러 변종이 있다. 엄격한 형식은 명세만을 따르지만 다른 형식은 낡은 브라우저에서 사용된 마크업을 지원.

DOM

“파싱 트리”는 DOM 요소와 속성 노드의 트리로서 출력 트리가 된다. DOM은 문서 객체 모델(Document Object Model)의 준말.

DOM은 마크업과 1:1 관계를 맺는다.

파싱 알고리즘

html은 일반적인 상향식 또는 하향식 파서로 파싱이 안된다. 그 이유는

  1. 언어의 너그러운 속성
  2. 잘 알려져있는 html 오류에 대한 브라우저의 관용
  3. 변경에 의한 재파싱. 일반적으로 소스는 파싱하는 동안 변하지 않지만 html에서 document.write을 포함하고 있는 스크립트 태그는 토큰을 추가할 수 있기 때문에 실제로는 입력 과정에서 파싱이 수정된다

때문에 브라우저는 html 파싱을 위한 별도의 파서를 생성한다.
파싱 알고리즘은 토큰화와 트리 구축 두 단계로 되어있다.

토큰화 알고리즘

알고리즘의 결과물은 html 토큰이다. 알고리즘은 상태 기계이다. 각 상태는 하나 이상의 연속된 문자를 입력받아 이 문자에 다음 상태를 갱신한다.

<html>
   <body>
      Hello world
   </body>
</html>  

초기 상태는 “자료 상태”. < 문자를 만나면 “태그 열림 상태”로 변함. a-z 문자를 만나면 “시작 태그 토큰”을 생성하고 상태는 “태그 이름 상태”로 변하는데 > 문자를 만날 때까지 유지. 각 문자에는 새로운 토큰 이름이 붙는데 이 경우 생성된 토큰은 html 토큰.
> 문자에 도달하면 현재 토큰이 발행되고 상태는 “자료 상태”로 바뀜. 이렇게 html 태그와 body 태그를 발행, Hello world의 H 문자를 만나면 문자 토큰이 발행될 것. 종료 태그의 < 문자를 만날 때까지 진행됨.
다시 태그 열림 상태가 됨. /문자는 종료 태그 토큰을 생성하고 “태그 이름 상태”로 변경됨. 이 상태는 > 문자를 만날 때까지 유지됨.

트리 구축 알고리즘.

파서가 생성되면 문서 객체가 생성됨. 트리 구축이 진행되는 동안 문서 최상단에는 DOM 트리가 수정되고 요소가 추가됨. 토큰화에 의해 발행된 각 노드는 트리 생성자에 의해 처리됨. 각 토큰을 위한 DOM 요소의 명세는 정의됨. DOM 트리에 요소를 추가하는 것이 아니라면 열린 요소는 스택에 추가된다.

<html>
   <body>
      Hello world
   </body>
</html>

트리 구축 단계의 입력 값은 토큰화 단계에서 만들어지는 일련의 토큰. 받은 html 토큰은 html 이전 모드가 되고 토큰은 이 모드에서 처리됨. 이것은 HTMLHtmlElement 요소를 생성하고 문서 객체의 최상단에 추가됨.
상태는 “head 이전”모드로 바뀌고 “body” 토큰을 받았다. “head” 토큰이 없더라도 HTMLHtmlElement는 묵시적으로 생성되어 트리에 추가될 것이다.
다음은 “head 다음” 모드. body 토큰이 처리되고 HTMLBodyElement가 생성되어 추가되었으며 “body 안쪽” 모드가 되었다.
“Hello world” 문자열의 문자 토큰을 받음. 첫 번째 토큰이 생성되고 “본문” 노드가 추가되면서 다른 문자들이 그 노드에 추가될 것.
body 종료 토큰을 받으면 “body 다음” 모드가 된다. html 종료 태그를 만나면 “body 다음 다음” 모드로 바뀐다. 마지막 파일 토큰을 받으면 파싱을 종료한다.

파싱이 끝난 이후의 동작

문서 상태는 “완료”가 되고 “로드” 이벤트가 발생.

브라우저의 오류 처리

“유효하지 않은 구문” 이라는 오류. 이는 브라우저가 모든 오류 구문을 교정하기 때문.

<html>  
   <mytag></mytag>
   <div>
     <p>
   </div>
   Really lousy HTML
   </p>

여러 규칙을 위반했지만 브라우저는 올바르게 표시. 파서가 실수를 수정했기 때문.
파서는 토큰화된 입력 값을 파싱하여 문서를 만들고 문서 트리를 생성. 규칙에 맞게 작성된 문서라면 파싱이 수월하겠지만 형식에 맞지 않은 많은 html 문서를 다뤄야 하기에 파서는 오류에 대한 아량이 있어야 한다.
파서는 다음과 같은 오류를 처리해야됨

  1. 어떤 태그의 안쪽에 추가하려는 태그가 금지된 것일 때 일단 허용된 태그를 먼저 닫고 금지된 태그는 외부에 추가한다
  2. 파서가 직접 요소를 추가해서는 안된다. html, head, body, tbody, tr, td, li 태그가 이런 경우에 해당.
  3. 인라인 요소 안쪽에 블록 요소가 있는 경우 부모 블록 요소를 만날 때까지 모든 인라인 태그를 닫는다
  4. 이런 방법이 도움이 되지 않으면 태그를 추가하거나 무시할 수 있는 상태가 될 때까지 요소를 닫는다.

웹킷이 오류를 처리하는 예

<br> 대신 </br>

어떤 사이트는 <br> 대신 </br> 사용. 익스플로러, 파이어폭스와 호환성을 갖기 위해 웹킷은 이를 <br>로 간주

어긋난 표

표 안에 또다른 표가 th 또는 td 셀 내부에 있지 않은 것

<table>

    <table>

    <tr><td>inner table</td></tr>

    </table>

    <tr><td>outer table</td></tr>

</table>  

이 경우 웹킷은 중첩을 분해하여 형제 요소가 되게 함

<table>

    <tr><td>outer table</td></tr>

</table>

<table>

    <tr><td>inner table</td></tr>

</table>  

웹킷은 이런 처리를 할 때 스택 사용. 안쪽 표는 바깥쪽 표의 외부로 옮겨져 형제 요소가 됨.

중첩된 폼 요소

폼 안에 또다른 폼을 넣는 경우 안쪽 폼은 무시됨

태그 중첩이 너무 깊을 때

최대 20개의 중첩만 허용하고 나머지는 무시한다.

잘못 닫힌 html 또는 body 태그

문서가 끝나기 전 body 태그를 닫은 경우 브라우저는 body 태그를 닫지 않는다.
대신 종료를 위해 end()를 호출한다.

css 파싱

css는 문맥 자유 문법이고 소개 글에서 설명했던 파서 유형을 이용하여 파싱이 가능하다.

웹킷 CSS 파서

css 문법 파일로부터 자동으로 파서를 생성하기 위해 플렉스와 바이슨 파서 생성기를 사용. 바이슨은 상향식 이동 감소 파서를 생성. 파이어폭소는 하향식 파서 사용. 각 css 파일은 스타일 시트 객체로 파싱, 각 객체는 css 규칙을 포함. css 규칙 객체는 선택자와 선언 객체, 그리고 css 문법과 일치하는 다른 객체를 포함.

스크립트와 스타일 시트의 진행 순서

스크립트

웹은 파싱과 실행이 동시에 수행되는 동기화(synchronous) 모델. 제작자는 파서가

예측 파싱

웹킷과 파이어폭스는 예측 파싱과 같은 최적화를 지원. 스크립트를 실행하는 동안 다른 스레드는 네트워크로부터 다른 자원을 찾아 내려받고 문서의 나머지 부분을 파싱. 이렇게 하면 자원을 병렬로 연결해 받을 수 있고 전체적인 속도 개선. 예측 파서는 외부 스크립트, 외부 스타일 시트 등 참조된 외부 자원을 파싱.

스타일 시트

스타일 시트는 DOM 트리를 변경하지 않기 때문에 문서 파싱을 기다리거나 중단하지 않음. 그러나 스크립트가 문서를 파싱하는 동안 스타일 시트를 요청하는 경우라면 문제가 됨. 스타일이 파싱되지 않은 상태라면 스크립트는 잘못된 결과를 내놓기 때문에 많은 문제를 야기함.

렌더 트리 구축

DOM 트리가 구축되는 동안 브라우저는 렌더 트리 구축. 표시해야 할 순서와 문서의 시각적 구성 요소로써 올바른 순서로 내용을 그려내기 위함.
파이어폭스는 이를 형상(frames)이라 부르고 웹킷은 렌더러(renderer) 또는 render object라는 용어 사용.
렌더러는 자신과 자식 요소를 어떻게 배치해야 하는지 알고 있음.
RenderObject class

class RenderObject { virtual  
    void layout(); virtual
    void paint(PaintInfo); virtual
    void rect repaintRect();
    Node * node; //the DOM node
    RenderStyle * style; // the computed style
    RenderLayer * containgLayer; //the containing z-index layer
}

각 렌더러는 css2 명세에 따라 노드의 css 박스에 부합하는 사각형을 표시. 렌더러는 너비, 높이, 위치 등의 기하학적인 정보 포함.

DOM 트리와 렌더 트리의 관계

둘은 1:1로 대응하는 관계는 아님. head 요소 같은 비시각적 DOM 요소는 렌더 트리에 추가되지 않음. display: none 은 트리에 나타나지 않음.
여러 개의 시각 객체와 대응하는 DOM 요소도 있음. “select” 요소는 ‘표시 영역, 드롭다운 목록, 버튼’ 표시를 위한 3개의 렌더러가 있음. 한 줄에 충분히 표시할 수 없는 문자가 여러 줄로 바뀔 때 별도의 렌더러로 추가됨. 또한 깨진 html. 인라인과 블록 박스가 섞인 경우 인라인 박스를 감싸기 위한 익명의 블록 렌더러가 생성됨.

트리를 구축하는 과정

웹킷에서는 스타일을 결정하고 렌더러를 만드는 과정을 attachment라고 부른다. 모든 DOM 노드에는 attach 메서드가 있다. 어태치먼트는 동기적인데 DOM 트리에 노드를 추가하면 새 노드의 attach 메서드를 호출한다.
html과 body 태그를 처리함으로써 렌더 트리 루트를 구성. 루트 렌더 객체는 css 명세에서 포함 블록과 일치. 파이어폭스는 이것을 ViewPortFrame 이라 부르고, 웹킷은 RenderView라 부름. 이것이 문서가 가리키는 렌더 객체이고 트리의 나머지 부분은 DOM 노드를 추가함으로써 구축됨.

스타일 계산

렌더 트리를 구축하려면 각 렌더 객체의 시각적 속성에 대한 계산이 필요한데, 이것은 각 요소의 스타일 속성을 계산함으로써 처리됨.
스타일은 인라인 스타일 요소와 html의 시각적 속성과 같은 다양한 스타일 시트를 포함. html의 시각적 속성은 대응하는 css 스타일 속성으로 변환됨.

스타일을 계산할 때 어려움

  1. 스타일 데이터는 구성이 매우 광범위. 많은 스타일 속성을 수용하면서 메모리 문제를 야기할 수 있음
  2. 최적화되어 있지 않다면 각 요소에 할당된 규칙을 찾는 것이 성능 문제 야기할 수 있음. 맞는 규칙을 찾는 과정이 실상 쓸모가 없거나 다른 길을 찾아야 하는 복잡한 구조가 될 수 있음.
    예를 들어 ` div div div div {…}` 이 선택자는 3번째 자손<div>에 규칙을 적용한다는 뜻. 규칙을 적용할 div 요소를 확인하려면 트리로부터 임의의 줄기를 선택하고 탐색하는 과정에서 규칙에 맞지 않는 줄기를 선택했다면 또 다른 줄기를 선택해야 함.
  3. 규칙을 적용하는 것은 계층 구조를 파악해야 하는 꽤나 복잡한 다단계 규칙을 수반한다.

스타일 정보 공유

웹킷 노드는 스타일 객체(RenderStyle)를 참조하는데 이 객체는 일정 조건 아래 공유할 수 있음. 노드가 형제이거나 또는 사촌일 때 공유, 다음과 같은 조건일 때 공유.

  1. 동일한 마우스 반응 상태를 가진 요소여야 함. 예를 들어 한 요소가 :hover 상태가 될 수 없는데 다른 요소는 :hover가 될 수 있다면 동일한 마우스 상태가 아님.
  2. 아이디가 없는 요소
  3. 태그 이름이 일치해야 함
  4. 클래스 속성이 일치해야 함
  5. 지정된 속성이 일치해야 함
  6. link 상태가 일치해야 함
  7. focus 상태가 일치해야 함
  8. 문서 전체에서 속성 선택자의 영향을 받는 요소가 없어야 함.
  9. 요소에 인라인 스타일 속성이 없어야 함
  10. 문서 전체에서 형제 선택자를 사용하지 않아야 함. 웹 코어는 형제 선택자를 만나면 전역 스위치를 열고 전체 문서의 스타일 공유를 중단함. 형제 선택자는 + 선택자와 :first-child 그리고 :last-child를 포함.

파이어 폭스 규칙 트리

파이어 폭스는 스타일 계산을 쉽게 처리하기 위해 규칙 트리와 스타일 문맥 트리라고 하는 두 개의 트리를 더 가지고 있다. 웹킷도 스타일 객체를 가지고 있지만 스타일 문맥 트리처럼 저장되지 않고 오직 DOM 노드로 관련 스타일을 처리.
스타일 문맥에는 최종 값이 저장되어 있음. 값은 올바른 순서 안에서 규칙을 적용하고 구체적인 값으로 변환하면서 계산됨. 논리적인 값이 화면의 백문율이라면 이 값은 절대적인 단위(px)로 변환됨. 부합하는 모든 규칙은 트리에 저장하는데 경로의 하위 노드가 높은 우선순위를 갖는다. 규칙 저장은 느리게 처리됨. 트리는 처음부터 모든 노드를 계산하지 않지만 노드 스타일이 계산될 필요가 있을 때 계산된 경로를 트리에 추가한다.
트리가 작업량을 줄이는 방법을 살펴보자.

구조체로 분리

스타일 문맥은 구조체로 나뉘는데 선 또는 색상과 같은 종류의 스타일 정보를 포함. 구조체의 속성들은 상속되거나 상속되지 않음. 속성들은 요소에 따라 한 부모로부터 상속됨. 상속되지 않은 속성들은 reset 속성이라 부르는데 상속을 받지 않는 것으로 정해져 있다면 기본 값을 사용.
트리는 최종으로 계산된 값을 포함하여 전체 구조체를 저장하는 방법으로 도움을 줌. 하위 노드에 구조체를 위한 속성 선언이 없다면 저장된 상위 노드의 구조체 속성을 그대로 받아서 사용.

규칙 트리를 사용하여 스타일 문맥을 계산

어떤 요소의 스타일 문맥을 계산할 때 가장 먼저 규칙 트리의 경로를 계산하거나 이미 존재하는 경로를 사용. 그리고 새로운 스타일 문맥으로 채우기 위해 경로 안에서 규칙 적용. 가장 높은 우선순위를 가진 경로의 하위 노드에서 시작하여 구조체가 가득 찰 때까지 트리의 상단으로 거슬러 올라감. 규칙 노드 안에서 구조체를 위한 특별한 선언이 없다면 상당한 최적화를 할 수 있음. 선언이 가득 채워질 때까지 노드 트리의 상위로 찾아 올라가 적용하면 최상의 최적하가 되고 모든 구조체는 공유됨. 이것은 최종 값과 메모리 계산을 절약한다.
선언이 완전하지 않으면 구조체가 채워질 때까지 트리의 상단으로 거슬러 올라간다. 구조체에서 어떤 선언도 발견할 수 없는 경우 구조체는 상속(inherit) 타입인데 문맥 트리에서 부모 구조체를 향하면서 성공적으로 구조체를 공유. 재설정 구조체라면 기본 값들이 사용됨.
가장 구체적인 노드에 값을 추가하면 실제 값으로 변환하기 위해 약간의 추가적인 계산을 해야함. 트리 노드에서 결과를 저장하기 때문에 자식에게도 사용 가능.
같은 트리 노드를 가리키는 형제 요소가 있는 경우 전체 스타일 문맥이 이들 사이에서 공유됨.
이런 html이 있다고 가정

<div class="err" id="div1">  
    <p>
    this is a <span class="big"> big error </span>
    this is also a <span class="big"> very big error</span> error
    </p>
</div>  
<div class="err" id="div2">another error</div>  

그리고 다음과 같은 규칙이 있음

  1. div { margin:5px; color:black }
  2. .err { color:red }
  3. .big { margin-top:3px }
  4. div span { margin-bottom:4px }
  5. #div1 { color:blue }
  6. #div2 { color:green }

색상과 여백 두 개의 구조체를 채울 필요가 있다고 치자. 색상 구조체는 색상 값만을 포함하고 여백 구조채는 네 개의 면에 대한 값을 포함
html을 파싱하여 두 번째 <div> 태그인 <div class="err" id="div2">에 이르렀다고 가정. 이 노드에 필요한 스타일 문맥을 생성하고 스타일 구조체를 채워야 함.
두 번째 <div> 규칙에 맞는 것을 찾으면 1,2,6이 된다. 이것은 요소가 사용할 수 있는 트리 경로가 이미 존재한다는 것을 의미하고 규칙6에 이르는 또 다른 노드를 문맥 트리에 추가하면 된다. 스타일 문맥을 생성하고 문맥 트리에 추가하면 새로운 스타일 문맥이 규칙 트리의 F:6 노드를 가리킨다.
스타일 구조체를 채우는데 여백 구조체를 채우는 것부터 시작. 마지막 규칙 노드 F:6이 여백 구조체를 포함하지 않기 때문에 거슬러 올라가 계산된 값을 사용. 여백 규칙이 선언된 최상위 노드의 구조체를 규칙 노드 B:1에서 찾았다.
색상 구조체 정의에는 저장된 구조체를 사용할 수 없음. 색상은 이미 하나의 속성 값을 가지고 있기 때문에 다른 값을 채우기 위해 규칙 트리 상단으로 거슬러 올라갈 필요가 없음. 최종 값을 계산하고 계산된 값을 이 노드에 저장할 것이다.
두 번째 요소는 보다 수월하게 진행된다. 맞는 규칙을 찾다 보면 이전 span과 같이 규칙 트리의 G:3를 가리킨다는 결론에 이르는데 동일한 노드를 가리키는 형제가 있기 때문에 전체 스타일 문맥을 공유하고 이전 span 문맥을 취한다.
부모로부터 상속된 규칙을 포함하고 있는 구조체의 저장은 문맥 트리에서 처리된다. 색상 속성은 실제로 상속된다. 그러나 파이어폭스는 재설정으로 처리해서 규칙 트리에 저장한다.
규칙 트리가 없는 웹킷은 선언이 일치하는 규칙이 4번 탐색된다. 우선 중요하지 않은 상위속성이 적용되고, 그 다음 중요한 상위 속성이 적용된다. 그리고 중요하지 않은 일반 속성, 마지막으로 중요한 일반 속성이 적용된다. 이것은 여러 번 나타나는 속성들이 정확한 다단계 순서에 따라 결정된다는 것을 의미하고 가장 마지막 값이 적용된다.

쉬운 선택을 위한 규칙 다루기

스타일 규칙을 위한 몇 가지 소스

  • css 규칙을 외부 스타일 시트에서 선언하거나 style 요소에서 선언 p {color:blue}
  • 인라인 스타일 속성 ` <p style="color:blue"></p> `
  • html의 시각적 속성 <p bgcolor="blue"></p> 마지막 두가지는 자신이 스타일 속성을 가지고 있거나 html 속성을 이용하여 연결할 수 있기에 요소에 쉽게 연결됨.
    위에 언급한 문제 2번에 따라 css 규칙은 연결하는 것은 까다로울 수 있음. 그래서 이를 해결하려면 쉽게 접근할 수 있도록 규칙을 교묘하게 처리해야함.
    스타일시트 파싱 후 규칙은 선택자에 따라 여러 해시맵 중 하나에 추가됨. 아이디, 클래스 이름, 태그 이름을 사용한 맵이 있고 이런 분류에 맞지 않는 것을 위한 일반적인 맵이 있음. 선택자가 아이디인 경우 규칙은 아이디 맵에 추가되고 선택자가 클래스인 경우 규칙은 클래스 맵에 추가됨.
    이런 처리 작업으로 규칙을 찾는 일은 쉬워짐. 맵에서 특정 요소와 관련 있는 규칙을 추출할 수 있기 때문에 모든 선언을 찾아볼 필요가 없음. 이런 최적화는 찾아야 할 규칙의 95% 이상을 제거하기 때문에 규칙을 찾는 동안 모든 선언을 고려할 필요 없음.
    p.error {color:red}  
    #messageDiv {height:50px}
    div {margin:5px}  
    

    첫번째 규칙은 클래스 맵에 추가됨. 두번째는 아이디 맵에, 세 번째는 태그 맵에 추가됨.
    ```

an error occurred

this is a message
위와 관련된 html 코드.  
p 요소의 규칙. 클래스 맵은 "p.error"를 위한 규칙 하부의 "error" 키를 찾음. div 요소는 아이디 맵과 태그 맵에 관련 규칙이 있음. 그러므로 이제 남은 작업은 키를 사용하여 추출한 규칙 중 실제로 일치하는 규칙을 찾는 것.  
div에 해당하는 다음과 같은 규칙이 있다고 가정하자.  

table div {margin:5px}
``` 이 예제는 여전히 태그 맵에서 규칙을 추출할 것. 가장 우측에 있는 선택자가 키이기 때문. 그러나 앞서 작성한 div 요소와는 일치하지 않음. 상위에 table이 없기 때문.

다단계 순서에 따라 규칙 적용하기

스타일 객체는 모든 css 속성을 포함하고 있다. 어떤 규칙과도 일치하지 않는 일부 속성은 부모 요소의 스타일 객체로부터 상속받는다. 그 외 다른 속성들은 기본 값으로 설정된다.
문제는 하나 이상의 속성이 정의될 때 시작되고 다단계 순서가 이 문제를 해결하게 됨.

스타일 시트 다단계 순서

스타일 속성 선언은 여러 스타일 시트에서 나타날 수 있고 하나의 스타일 시트 안에서도 여러 번 나타날 수 있는데 이것은 규칙을 적용하는 순서가 매우 중요하다는 것을 의미. 이것을 다단계(cascade) 순서라고 한다. css2 명세에 따른 다단계 순서 (우선 순위가 낮은 것에서 높은 순서)

  1. 브라우저 선언
  2. 사용자 일반 선언
  3. 저작자 일반 선언
  4. 저작자 중요 선언
  5. 사용자 중요 선언

브라우저 선언의 중요도가 가장 낮으며 사용자가 저작자의 선언을 덮어 쓸 수 있는 것은 선언이 중요하다고 표시한 경우뿐. 같은 순서 안에서 동일한 속성 선언은 특정성에 의해 정렬이 되고 이 순서는 곧 특정성이 됨. html 시각 속성은 css 속성 선언으로 변환되고 변환된 속성들은 저작자 일반 선언 규칙으로 간주됨.

특정성

  • 선택자 없이 ‘style’ 속성이 선언된 것이면 1을 센다. 그렇지 않으면 0을 센다 (a)
  • 선택자에 포함된 아이디 선택자 개수를 센다 (b)
  • 선택자에 포함된 속성 선택자와 가상 클래스 선택자의 숫자를 센다. (c)
  • 선택자에 포함된 요소 선택자와 가상 요소 선택자의 숫자를 센다. (d)

네 개의 연결된 숫자 a-b-c-d를 연결하면 특정성의 값이 됨.
사용할 진법은 분류 중에 가장 높은 숫자에 의해 정의됨. a=14이면 16 진수를 사용할 것.

규칙 정렬

맞는 규칙을 찾으면 다단계 규칙에 따라 정렬된다. 웹킷은 목록이 적으면 버블 정렬을 사용하고 목록이 많을 때는 병합 정렬을 사용한다. 웹킷은 규칙에 “>” 연산자를 덮어쓰는 방식으로 정렬을 실행한다.

점진적 처리

웹킷은 @import를 포함한 최상위 수준의 스타일 시트가 로드되었는지 표시하기 위해 플래그를 사용. DOM 노드와 시각정보를 연결하는 과정에서 스타일이 완전히 로드되지 않았다면 문서에 자리 표시자를 사용하고 스타일 시트가 로드됐을 때 다시 계산.

배치

렌더러가 생성되어 트리에 추가될 때 크기와 위치 정보는 없는데 이런 값을 계산하는 것을 배치 또는 리플로라고 부름.
html은 흐름 기반의 배치 모델을 사용하는데 이것은 보통 단일 경로를 통해 크기와 위치 정보를 계산할 수 있다는 것을 의미. 배치는 왼쪽에서 오른쪽, 또는 위에서 아래로 흐른다. 단, 표는 크기와 위치를 계산하기 위해 하나 이상의 경로를 필요로 하기에 예외가 됨.
좌표계는 기준점으로부터 상대의 위치를 결정하는데 X축과 Y축 좌표를 사용한다.
배치는 반복되며 HTML 문서의 <html> 요소에 해당하는 최상위 렌더러에서 시작한다. 배치는 프레임 계층의 일부 또는 전부를 통해 반복되고 각 렌더러에 필요한 크기와 위치 정보를 계산한다.
최상위 렌더러의 위치는 0,0이고 브라우저 창의 보이는 영역에 해당하는 뷰포트 만큼의 면적을 갖는다.
모든 렌더러는 “배치” 또는 “리플로” 메서드를 갖는데 각 렌더러는 배치해야 할 자식의 배치 메소드를 불러온다.

더티 비트 체제

소소한 변경 때문에 전체를 다시 배치하지 않기 위해 브라우저는 “더티 비트” 체제를 사용한다. 렌더러는 다시 배치할 필요가 있는 변경 요소 또는 추가된 것과 그 자식을 “더티”라고 표시한다.
“더티”와 “자식이 더티” 두 가지 플래그가 있음. 자식이 더티하다는 것은 본인은 괜찮지만 자식 중 적어도 하나를 다시 배치할 필요가 있다는 의미.

전역 배치와 점증 배치

배치는 렌더러 트리 전체에서 일어날 수 있는데 이것을 “전역” 배치라 하고 다음과 같은 경우에 발생

  1. 글꼴 크기 변경과 같이 모든 렌더러에 영향을 주는 전역 스타일 변경
  2. 화면 크기 변경에 의한 결과

배치는 더티 렌더러가 배치되는 경우에만 점증되는데 추가적인 배치가 필요하기 때문에 약간의 손실이 발생할 수 있다.
점증 배치는 렌더러가 더티일 때 비동기적으로 일어남. 예를 들어 네트워크로부터 추가 내용을 받아서 DOM 트리에 더해진 다음 새로운 렌더러가 렌더 트리에 붙을 때.

비동기 배치와 동기 배치

점증 배치는 비동기로 실행됨. 파이어폭스는 점증 배치를 위해 “리플로 명령”을 쌓아 놓고 스케줄러는 이 명령을 한꺼번에 실행함. 웹킷도 점증 배치를 실행하는 타이머가 있는데 트리를 탐색하여 “더티” 렌더러를 배치함.
“offsetHeight” 같은 스타일 정보를 요청하는 스크립트는 동기적으로 점증 배치를 실행한다.
전역 배치는 보통 동기적으로 실행됨.

최적화

배치가 “크기 변경” 또는 렌더러 위치 변화 때문에 실행되는 경우 렌더러의 크기는 다시 계산하지 않고 캐시로부터 가져온다.
어떤 경우는 하위트리만 수정되고 최상위로부터 배치가 시작되지 않는 경우도 있음. 이런 경우는 입력 필드에 텍스트를 입력하는 경우와 같이 변화 범위가 한정적이어서 주변에 영향을 미치지 않을 때 발생. 만약 입력 필드 바깥쪽에 텍스트가 입력되는 경우라면 배치는 최상단으로부터 시작이 될 것.

배치 과정

배치는 보통 다음과 같은 형태로 진행됨

  1. 부모 렌더러가 자신의 너비를 결정
  2. 부모가 자식을 검토
    1. 자식 렌더러를 배치 (자식의 x와 y를 설정)
    2. (부모와 자식이 더티하거나 전역 배치 상태이거나 또는 다른 이유로) 필요하다면 자식 배치를 호출하여 자식의 높이를 계산함.
  3. 부모는 자신의 누적된 높이와 여백, 패딩을 사용하여 자신의 높이를 설정함. 이 값은 부모 렌더러의 부모가 사용하게 됨.
  4. 더티 비트 플래그를 제거한다.

파이어폭스는 “상태” 객체를 배치를 위한 매개변수로 사용하는데 상태는 부모의 너비를 포함한다.
파이어폭스 배치의 결과는 매트릭스 객체인데 높이가 계산된 렌더러를 포함한다.

너비 계산

렌더러의 너비는 포함하는 블록의 너비, 그리고 렌더러의 너비와 여백, 테두리를 이용하여 계산됨
예를 들어 ` <div style="width:30%"></div> `
웹킷은 다음과 같이 계산할 것.

  • 컨테이너의 너비는 컨테이너 availableWidth와 0 사이의 최대값. 이 경우 availableWidth는 다음과 같이 계산된 contentWidth이다.
    clientWidth() - paddingLeft() - paddingRight()
    clientWidth와 clientHeight는 객체의 테두리와 스크롤바를 제외한 내부 영역을 의미한다.
  • 요소의 너비는 “width” 스타일 속성의 값이다. 이 컨테이너 너비의 백분률 값은 절대 값으로 변환될 것이다
  • 좌우측 테두리와 패딩 값이 추가된다.

줄 바꿈

렌더러가 배치되는 동안 줄을 바꿀 필요가 있을 때 배치는 중단되고 줄 바꿀 필요가 있음을 부모에게 전달한다. 부모는 추가 렌더러를 생성하고 배치를 호출한다.

그리기

그리기 단계에서는 화면에 내용을 표시하기 위한 렌더 트리가 탐색되고 렌더러의 “paint” 메서드가 호출된다. 그리기는 UI 기반의 구성 요소를 사용한다.

전역과 점증

그리기는 배치와 마찬가지로 전역 또는 점증 방식으로 수행된다. 점증 그리기에서 일부 렌더라는 전체 트리에 영향을 주지 않는 방식으로 변경된다. 변경된 렌더러는 화면 위의 사각형을 무효화 하는데 OS는 이것을 “더티 영역”으로 보고 “paint” 이벤트를 발생시킨다. OS는 몇 개의 영역을 하나로 합치는 방법으로 효과적으로 처리한다. 크롬은 렌더러가 별도의 처리 과정이기 때문에 더 복잡. 크롬은 OS의 동작을 어느 정도 모방. 프레젠테이션은 이런 이벤트에 귀 기울이고 렌더 최상위로 메시지를 전달. 그러면 트리는 적절한 렌더러에 이를 때까지 탐색되고 스스로 다시 그려짐.

그리기 순서

실제로 요소가 stacking contents에 쌓이는 순서.

  1. 배경색
  2. 배경 이미지
  3. 테두리
  4. 자식
  5. 아웃라인

파이어폭스 표시 목록

파이어폭스는 렌더 트리를 검토하고 그려진 사각형을 위한 표시 목록을 구성. 목록은 올바른 그리기 순서에 따라 사각형을 위한 적절한 렌더러를 포함. 이런 방법으로 트리는 여러 번 리페인팅을 실행하는 대신 한 번만 탐색하면서 배경색, 배경 이미지, 테두리, 나머지 순으로 그려냄.
파이어폭스는 다른 불투명 요소 뒤에 완전히 가려진 요소는 추가하지 않는 방법으로 최적화를 진행한다.

웹킷 사각형 저장소

리페인팅 전에 웹킷은 기존의 사각형을 비트맵으로 저장, 새로운 사각형과 비교하고 차이가 있는 부분만 다시 그림.

동적 변경

브라우저는 변경에 가능한 한 최소한의 동작으로 반응하려고 노력. 그렇기에 요소의 색깔이 바뀌면 해당 요소의 리페인팅만 발생. 요소의 위치가 바뀌면 요소와 자식 그리고 형제의 리페인팅과 재배치가 발생. DOM 노드를 추가하면 노드의 리페인팅과 재배치가 발생. “html” 요소의 글꼴 크기를 변경하는 것과 같은 큰 변경은 캐시를 무효화하고 트리 전체의 배치와 리페인팅이 발생.

렌더링 엔진의 스레드

렌더링 엔진은 통신을 제외한 거의 모든 경우에 단일 스레드로 동작. 파이어폭스와 사파리의 경우 렌더링 엔진의 스레드는 브라우저의 주요한 스레드에 해당. 크롬에서는 이것이 탭 프로세서의 주요 스레드.
(스레드: 어떠한 프로그램 내에서 실행되는 흐름의 단위)

이벤트 순환

브라우저의 주요 스레드는 이벤트 순환으로 처리 과정을 유지하기 위해 무한 순환. 배치와 그리기 같은 이벤트를 위해 대기하고 이벤트를 처리한다.

CSS2 시각 모델

캔버스

CSS2 명세는 캔버스를 “서식 구조가 표현되는 공간”이라고 설명. 브라우저가 내용을 그리는 곳. 캔버스 공간 각각의 면적은 무한하지만 브라우저는 뷰포트의 크기를 기초로 초기 너비를 결정.
캔버스는 기본적으로 투명하기에 다른 캔버스와 겹치는 경우 비쳐 보이고, 투명하지 않을 경우에는 브라우저에서 정의한 색이 지정됨.

CSS 박스 모델

CSS 박스 모델은 문서 트리에 있는 요소를 위해 생성되고 시각적 서식 모델에 따라 배치된 사각형 박스를 설명.
각 박스는 콘텐츠 영역과 선택적인 패딩, 테두리, 여백이 있다.
모든 요소는 만들어질 박스의 유형을 결정하는 “display” 속성을 갖는데 이 속성의 유형은 다음과 같다.

  • block - 블록 상자를 만든다
  • inline - 하나 또는 그 이상의 인라인 상자를 만든다
  • none - 박스를 만들지 않는다

기본 값은 인라인이지만 브라우저의 스타일 시트는 다른 기본 값을 설정. “div” 요소의 display 속성 기본 값은 block이다.

위치 결정 방법

  1. Normal - 객체는 문서 안의 자리에 따라 위치가 결정됨. 이것은 렌더 트리에서 객체의 자리가 DOM 트리의 자리와 같고 박스 유형과 면적에 따라 배치됨을 의미.
  2. Float - 객체는 일반적인 흐름에 따라 배치된 다음 왼쪽이나 오른쪽으로 흘러 이동한다.
  3. Absolute - 객체는 DOM 트리 자리와는 다른 렌더 트리에 놓인다.

위치는 “position” 속성과 “float” 속성에 의해 결정됨

  • static과 relative로 설정하면 일반적인 흐름에 따라 위치가 결정된다
  • absolute와 fixed로 설정하면 절대적인 위치가 된다

position 속성을 정의하지 않으면 static이 기본 값이 되며 일반적인 흐름에 따라 위치가 결정됨. static이 아닌 다른 속성 값을 사용하면 top, bottom, left, right 속성으로 위치를 결정할 수 있음.

박스가 배치되는 방법은 다음과 같은 방법으로 결정됨

  • 박스 유형 (display, inline…)
  • 박스 크기 (width, height…)
  • 위치 결정 방법 (position, float)
  • 추가적인 정보 - 이미지 크기와 화면 크기 등

박스 유형

  • 블록 박스: 브라우저 창에서 사각형 블록을 형성
  • 인라인 박스: 블록이 되지 않고 블록 내부에 포함된다 블록은 다른 블록 아래 수직으로 배치되고 인라인은 수평으로 배치된다.
    inlineBlock 인라인 박스는 라인 또는 라인 박스 안쪽에 놓임. 라인은 적어도 가장 큰 박스만큼 크지만 “baseline”정렬일 때 더 커질 수 있다. 이것은 요소의 하단이 다른 상자의 하단이 아닌 곳에 배치된 경우를 의미한다. 포함하는 너비가 충분하지 않으면 인라인은 몇 줄의 라인으로 배치되는데 이것은 보통 문단 안에서 발생한다.

위치 잡기

상대적인 위치

상대적인 위치 잡기는 일반적인 흐름에 따라 위치를 결정한 다음 필요한 만큼 이동한다.
image

플로트

플로트 박스는 라인의 왼쪽 또는 오른쪽으로 이동. 흥미로운 점은 다른 박스가 이 주변을 흐른다는 것.

absolute 위치와 fixed 위치

절대와 고정 배치는 일반적인 흐름과 무관하게 결정되고, 일반적인 흐름에 관여하지 않으며, 면적은 부모에 따라 상대적이다. 고정인 경우 뷰포트로부터 위치를 결정한다.

층 표현

css의 z-index 속성에 의해 명시됨. 층은 박스의 3차원 표현이고 “z축”을 따라 위치를 정함.
박스는 스택으로 구분됨. 각 스택에서 뒤쪽 요소가 먼저 그려지고 앞쪽 요소는 사용자에게 가까운 쪽으로 나중에 그려짐. 가장 앞쪽에 위치한 요소는 겹치는 이전 요소를 가린다.
스택은 z-index 속성에 따라 순서를 결정. z-index 속성이 있는 박스는 local stack을 형성. 뷰포트는 바깥쪽의 스택이다.


읽다가 중간에 이해 안되는 내용도 있었지만, 일단 훑어보자는 생각으로 다 정리했다.
몇 번 더 읽어봐서 다 이해할 수 있게 해야겠다.

[BOJ] 9663 : N-Queen (Python3)

출처: https://www.acmicpc.net/problem/9663

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

소스코드

n = int(input())
ans = 0
# 세로, 대각선(/), 대각선(\)
arr1, arr2, arr3 = [0]*n, [0]*(2*n-1), [0]*(2*n-1)

def nqueen(x): # x는 현재 행
    global ans
    if x == n: # n개의 행에 퀸을 하나씩 둬야 하므로, x가 n이 되었다면 퀸을 다 둔 것
        ans += 1
        return
    for i in range(n):
        if arr1[i] or arr2[x+i] or arr3[x-i+n-1]: # 열이나 대각선에 이미 퀸이 놓아져있다면 그 경우는 생략
            continue
        arr1[i] = arr2[x+i] = arr3[x-i+n-1] = 1
        nqueen(x+1)
        arr1[i] = arr2[x+i] = arr3[x-i+n-1] = 0

nqueen(0)
print(ans)

풀이

n*n개의 체스판 위에 퀸 n개를 놓아두므로 퀸은 한 행에 하나씩 있어야 한다.
때문에 배열 arr1으로 각 행에 퀸이 어디있는지 나타낼 수 있음.
퀸은 대각선으로도 이동하므로, arr2와 arr3으로 어느 대각선에 퀸이 있는지 나타낸다.

그런데 대각선 배열을 어떻게 만들어야 할지 엄청 헷갈렸는데 제목 없음 이런 식으로 하면 되는 거였음. (arr2의 경우)
예를 들어 arr2 = [0, 1, 0 , 0, 0, 0, 0, 0] 이라면 저 1번 대각선에 퀸이 있는 것.
arr3은 맨 오른쪽 위가 0번이다.

MDN JavaScript 첫걸음 공부하면서 정리

MDN의 JavaScript 첫걸음에서 ‘JavaScript가 뭔가요?’ 부분을 혼자 공부하면서 정리한 내용입니다.
출처: https://developer.mozilla.org/ko/docs/Learn/JavaScript/First_steps

  • html: 웹 컨텐츠를 문단, 제목, 표 등으로 정의하고 부여하는 마크업 언어 (마크업 언어란? 태그 등을 이용하여 언어나 데이터의 구조를 명시하는 언어)
  • css: html 컨텐츠를 꾸며주는 스타일 규칙 언어
  • Javascript: 동적으로 컨텐츠를 바꾸는 스크립트 언어 (스크립트 언어란? 기존에 이미 존재하는 소프트웨어를 제어하기 위한 언어)

코어 자바스크립트 언어 기반의 기능성

  • Application Programming Interfaces (APIs)
  • API는 이미 만들어진 코드의 집합체

  • Browser API는 웹 브라우저에 설치된 API.
    • DOM (Document Object Model) API :HTML과 CSS를 알맞게 조정
    • Geolocation API : 지리적인 정보 검색
    • Canvas, WebGL: 2D와 3D 그래픽을 만들 수 있게 함
  • Third party API: 브라우저에 기본적으로 설치된 API가 아닌 인터넷에서 개인적으로 프로그래밍한 것
    • Twitter API: 웹사이트에 가장 최근의 트윗을 보여줌
    • Google Maps API, OpenStreetMap API: 웹사이트에 원하는 지도를 넣어주고 추가기능 지원

웹 페이지에서 JavaScript는 어떤 일을 하는가?

  • 브라우저에서 웹페이지를 불러올 때, 브라우저 안에서 HTML, CSS, Javascript 코드가 실행됨
  • html과 css가 결합되고 웹페이지 상에 올려진 후, 브라우저의 스크립트 엔진에 의해 자바스크립트가 실행됨
  • 자바스크립트는 해석형 언어이다. 코드가 순차적으로 실행되고 그 결과가 즉시 반환. 브라우저에서 동작하기 전에 코드를 변환할 필요가 없음.

인라인 JavaScript 처리기

<button onclick="createParagraph()">Click me!</button>
  • 이 방법은 효율적이지 않음. html 소스를 복잡하게 하고 모든 버튼마다 onclick 속성을 포함해야 함.

스크립트의 로딩 방법

  • 자바스크립트가 html 요소보다 먼저 실행된다면 조작할 요소가 존재하지 않기에 작동하지 않을 것.
  • 내부 자바스크립트 예제 해결 방법
    document.addEventListener("DOMContentLoaded", function() {
    ...
    });
    

    “DOMContentLoad” 이벤트가 발생했을 때 function()을 실행한다는 의미.

  • 외부 자바스크립트 해결 방법 <script src="script.js" async></script> async 속성 사용. 비동기방식으로

(웹 개발시 실제로 겪었던 에러이고, async 속성을 통해 해결했었다.)

async & defer

위 문제를 해결하기 위한 두 가지 방법.

  • async는 페이지 렌더링 중단 없이 스크립트를 다운로드 하고, 다운로드가 끝나자마자 이를 실행시킴. async는 각각의 스크립트가 독립적으로, 서로에게 의존하지 않는 관계일 때 적절.
<script async src="js/vendor/jquery.js"></script>

<script async src="js/script2.js"></script>

<script async src="js/script3.js"></script>

3개의 스크립트를 로딩하지만 이들의 순서는 보장할 수 없다.

  • defer는 이와 다르게 순서대로 다운로드 한 후 모든 스크립트와 내용이 다운로드 되었을 때 실행됨.

[BOJ] 15652 : N과 M (4) (Python3)

출처: https://www.acmicpc.net/problem/15652

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 같은 수를 여러 번 골라도 된다.
  • 고른 수열은 비내림차순이어야 한다.
    • 길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

소스코드

n, m = map(int, input().split())
nums = [i+1 for i in range(n)]
outs = []

def dfs(cnt, idx):
    if cnt == m:
        print(*outs)
        return
    for i in range(idx, n):
        outs.append(i+1)
        dfs(cnt+1, i)
        outs.pop()

dfs(0, 0)

풀이

15650과 15651이 짬뽕된 문제.
15650 문제처럼 index를 넘겨주어 비내림차순이 만들어지게 했고, 같은 수를 여러번 고를 수 있게 하기 위해 재귀시 i+1이 아닌 i를 넘겨줌.

[BOJ] 15651 : N과 M (3) (Python3)

출처: https://www.acmicpc.net/problem/15651

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

소스코드

n, m = map(int, input().split())
nums = [i+1 for i in range(n)]
outs = []

def dfs(cnt):
    if cnt == m:
        print(*outs)
        return
    for i in range(n):
        outs.append(i+1)
        dfs(cnt+1)
        outs.pop()

dfs(0)

풀이

15649 문제에서 같은 수를 여러번 골라도 된다는 조건 하나가 추가된 문제이다.
때문에 중복을 검사하던 checked 리스트를 없앴고, 그에 대한 조건문 등도 전부 삭제했다.

[BOJ] 15650 : N과 M (2) (Python3)

출처: https://www.acmicpc.net/problem/15650

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

소스코드

n, m = map(int, input().split())
nums = [i+1 for i in range(n)]
checked = [0]*n
outs = []

def dfs(cnt, idx):
    if cnt == m:
        print(*outs)
        return
    for i in range(idx, n):
        if checked[i] == 1:
            continue
        checked[i] = 1
        outs.append(i+1)
        dfs(cnt+1, i+1)
        outs.pop()
        checked[i] = 0

dfs(0, 0)

풀이

15649 문제에서 조건 하나만 추가된 문제.
함수 인자로 idx를 추가해 이전 idx 이하는 진행하지 않도록 풀이했다.

[BOJ] 15649 : N과 M (1) (Python3)

출처: https://www.acmicpc.net/problem/15649

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

  • 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

소스코드

n, m = map(int, input().split())
nums = [i+1 for i in range(n)]
checked = [0]*n  # 탐사했는지 여부
outs = []  # 출력할 내용

def dfs(cnt):
    if cnt == m:  # m의 개수만큼 채워지면 출력
        print(*outs)
        return
    for i in range(n):
        if checked[i] == 1: # 이미 탐색했으면 생략
            continue
        checked[i] = 1 # 이제 탐색하므로
        outs.append(i+1) # 수열 원소 추가
        dfs(cnt+1)
        outs.pop() # 탐색이 끝났으므로 원소 삭제
        checked[i] = 0 

dfs(0)

풀이

백트래킹을 처음 접해봐서 알고리즘을 이해하는데 시간이 꽤 오래 걸렸다.

백트래킹은 특정 조건이 있을 때 해를 얻을 때까지 모든 가능성을 시도하는 알고리즘이다. 가능성은 트리처럼 구현할 수 있으며 검사하기 위해 깊이 우선 탐색(DFS)를 이용한다. 보통 재귀 함수로 구현한다. (출처: 위키백과)

DFS로 구현하는 이유는 BFS를 사용하면 더 많은 메모리가 필요하기 때문이라 한다.

[Python] 이진 탐색 트리 (Binary Search Trees)

프로그래머스 자료구조 강의와 각종 인터넷 자료를 참고하여 재구성한 내용입니다.

이진 탐색 트리

  • 모든 노드에 대하여
    • 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
    • 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 크고
    • 왼쪽과 오른쪽 서브트리 각각 역시 이진 탐색 트리여야 한다

목적

  • 이진 탐색 트리는 이진 탐색(binary search)과 연결 리스트(linked lists)를 결합한 자료 구조의 일종
  • 이진 탐색은 탐색에 소요되는 계산 복잡성이 O(logn)으로 빠르지만 자료 입력, 삭제가 불가능하다
  • 연결 리스트는 자료 입력, 삭제에 필요한 계산 복잡성이 O(1)로 효율적이지만 탐색을 하는데는 O(n)의 계산 복잡성이 요구된다
  • 이진 탐색 트리의 핵심 연산인 탐색, 삽입, 삭제의 계산 복잡성은 트리의 높이가 h일 때 O(h)이다
  • 그러나 배열을 이용한 이진 탐색과 비교했을 때 공간 소요가 크다는 단점이 있다

코드 구현 - 초기화

class Node:
	def __init__(self, key, data):
    	self.key = key
        self.data = data
        self.left = None
        self.right = None
        
class BinSearchTree:
	def __init__(self):
    	self.root = None

원소 탐색 연산 구현 (lookup)

찾으려는 대상의 key를 입력 받아, 찾은 노드와 그 부모 노드를 return 한다.

class BinSearchTree:
	def lookup(self, key):
    	if self.root:
        	return self.root.lookup(key)
        else:
        	return None, None
            
class Node:
	def lookup(self, key, parent=None):
    	if key < self.key:
        	if self.left:
            	return self.left.lookup(key, self)
            else:
            	return None, None
        elif key > self.key:
        	if self.right:
            	return self.right.loopup(key, self)
            else:
            	return None, None
        else:
        	return self, parent

원소 삽입 연산 구현 (insert)

  • 입력: key, 데이터 원소
  • return: 없음
class BinSearchTree:
	def insert(self, key, data):
    	if self.root:
        	self.root.insert(key, data)
        else:
        	self.root = Node(key, data)

class Node:
	def insert(self, key, data):
    	if key < self.key:
        	if self.left:
				self.left.insert(key, data)
            else:
            	self.left = Node(key, data)
        elif key > self.key:
        	if self.right:
        		self.right.insert(key, data)
            else:
            	self.right = Node(key, data)
        else:
        	raise KeyError

원소 삭제 연산 구현 (remove)

  • 지우려는 값이 leaf node에 있으면 그냥 삭제
  • internal node일 경우
    • child node가 1개일 경우: 삭제되는 노드 자리에 그 자식을 배치
    • child node가 2개일 경우: 삭제되는 노드보다 바로 다음으로 큰 키를 가지는 노드를 찾아 그 노드를 대신 배치
# 자식의 개수를 알아야하므로 countChildren 메소드 생성
class Node:
	def countChildren(self):
    	count = 0
        if self.left:
        	count += 1
        if self.right:
        	count += 1
        return count

class BinSearchTree:
	def remove(self, key):
    	node, parent = self.lookup(key)
        if node:
        	nChldren = node.countChildren()
            if nChildren == 0:
            	if parent:
                	if node == parent.left:
                    	parent.left = None
                    else:
                    	parent.right = None
                else:
                	self.root = None
            elif nChildren == 1:
            	if node.left:
                	var = node.left
                else:
                	var = node.right
            	if parent:
                	if parent.left == node:
                    	parent.left = var
                    else:
                    	parent.right = var
                else:
                	self.root = var
            else:
            	parent = node
                successor = node.right
                while successor.left:
                	parent = successor
                    successor = successor.left
                node.key = successor.key
                node.data = successor.data
            	if successor == parent.left:
                	parent.left = successor.right
                else:
                	parent.right = successor.right
            return True
        else:
        	return False
            

참조

[Python] 트리 - 이진 트리 (Trees)

프로그래머스 자료구조 강의와 각종 인터넷 자료를 참고하여 재구성한 내용입니다.

트리 (Trees)

  • 비선형적 자료 구조 (배열, linked lists, stacks, queues는 선형적 구조)
  • 트리는 root와 leaf로 이루어진다
  • 더 이상 가지를 칠 수 없는 node를 leaf라고 한다
  • 둘 다 아닌 노드를 internal node라고 한다
  • 트리는 비어있거나 root 원소 하나일 수도 있음
  • 노드가 거쳐야 하는 간선의 수를 Level이라고 한다.
  • 트리의 높이 (Height) = level + 1
  • 노드의 차수 (Degree) = 자식의 수 (leaf node는 degree가 0)

tree

이진 트리 (Binary Tree)

  • 모든 노드의 차수가 2 이하인 트리

포화 이진 트리 (Full Binary Tree)

  • 모든 레벨에서 노드들이 모두 채워져있는 이진 트리

완전 이진 트리 (Complete Binary Tree)

  • 마지막 레벨을 제외하고는 모든 노드가 자식 노드를 2개 가진 이진 트리
  • 높이가 k일때 레벨 k-2까지는 모든 노드가 2개의 자식을 가지고 레벨 k-1부터는 왼쪽부터 노드가 순차적으로 채워짐

trees

이진 트리의 구현

노드

class Node:
	def __init__(self, item):
    	self.data = item
        self.left = None
        self.right = None

트리

class BinaryTree:
	def __init__(self, r):
    	self.root = r

size

class Node: 
    def size(self):
        l = self.left.size if self.left else 0
        r = self.right.size if self.right else 0
        return l + r + 1

class BinaryTree:
	def size(self):
    	if self.root:
        	return self.root.size()
        else:
        	return 0

depth

class Node:
	def depth(self):
    	l = self.left.depth() if self.left else 0
        r = self.right.depth() if self.right else 0
        return l+1 if l>r else r+1
        
class BinaryTree:
	def depth(self):
    	if self.root:
        	return self.root.depth()
        else:
        	return 0

이진 트리의 순회 (Traversal)

깊이 우선 순회

  1. in-order (중위 순회): 왼쪽 자식노드(L), 내 노드(P), 오른쪽 자식노드(R) 순서로 방문한다.
  2. pre-order (전위 순회): 내 노드(P), 왼쪽 자식노드(L), 오른쪽 자식노드(R) 순서로 방문한다.
  3. post-order (후위 순회): 왼쪽 자식노드(L), 오른쪽 자식노드(R), 내 노드(P) 순서로 방문한다.

넓이 우선 순회

  • level이 낮은 노드를 우선 방문
  • 같은 수준의 노드들 사이에서는
    • 부모 노드의 방문 순서에 따라 방문
    • 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문

참조

SWIM, SWIM! 웹사이트 개발일지 2

SWIM, SWIM! 웹사이트 개발일지 1

디자인

screencapture-127-0-0-1-8080-2019-10-10-05_52_53

screencapture-127-0-0-1-8080-2019-10-10-05_53_13

결국 구글링과 장고 문서 정독을 통해 원하는 틀을 만드는 데까지 성공한다.
그 후 어울리는 배경 사진도 찾아보고, 포토샵으로 로고도 뚝딱 만들어보는 등 디자인적 요소를 가미했다.
그러나 문제점은 디자인이 구리다는 것이었다.
나름 열심히 했으나 글씨는 잘 보이지도 않았고 어떻게 고쳐야할지 감이 오지도 않았다.
디자이너가 있으면 좋겠다는 생각이 들었다.
주변 사람들을 열심히 생각해보다, 지인 중 한 사람이 웹 디자인을 한 적 있다는 사실이 떠올랐다.
고민 끝에 연락을 해보았고 긍정적인 대답을 들을 수 있었다.
처음으로 협업을 할 수 있는 기회가 생긴 것이다.

협업

그러나 처음이기에 어떻게 해야 할지 전혀 감이 오지 않았다.
디자인을 어떻게 받아야 하며 그 디자인을 어떻게 개발에 적용할 수 있는가.
혼자서는 답을 내릴 수 없는 문제라 다른 사람에게 물어보았더니 ‘제플린’을 사용해보란 답을 들었다.
뭔가 하고 살펴보니 개발자와 디자이너가 협업을 할 수 있는 프로그램인듯 했다. 디자인을 올리면 그것을 코드로 확인할 수 있다고.
zeplin

(이런 식으로 특정 요소의 세부적인 크기, 코드 등이 뜬다.)

마침 적절한 서비스다 싶어, 이를 통한 협업을 디자이너 님에게 부탁드렸다.
그렇게 디자인을 받아 적용하자 현재의 디자인이 갖춰졌다.

screencapture-swimswim-pythonanywhere-2019-11-10-16_00_23크기수정 screencapture-127-0-0-1-8080-2019-11-10-16_03_38크기수정

(글씨도 잘 보이고 훨씬 예뻐졌다 역시 갓디자인)

물론 내가 원하는 기능과 디자인이 표현하는 바가 다른 부분이나, 구현하기 힘든 부분 등은 상의 하에 조정해야 했다.
그러나 디자이너 님이 워낙 잘 해주셔서 크게 어려운 부분은 없던 것 같다.

자바스크립트

각 수영장마다 수영 시간이 나오고 그 밑에 자세히 버튼을 클릭하면 수영장 정보와 안내사항이 나온다.
이 부분 구현을 위해서 자바스크립트를 사용해야 했다.
이 전에 자바스크립트를 제대로 써본 적은 없지만 기초를 배운 적은 있기에 별 어려울 것 없다고 생각했다.
그러나 막상 쓰려고 보니 내가 배운 것은 문법 수준의 정말 쌩기초였다.
결국 자바스크립트 문서를 찾아보며 새롭게 공부해야 했다.
다행히 구현하려는 내용이 크게 어렵지는 않아 코드를 짜는 데 시간이 엄청 걸리지는 않았다.
다만 프론트엔드 쪽으로 갈 생각도 하고 있는 취준생으로서 자바스크립트를 더욱 더 파야겠다는 결심이 들었다.

느낀 점

대략적인 개발 과정을 다 적은 것 같다. 다만 작년 11월에 마무리 한 프로젝트이기 때문에 세세한 내용은 잘 기억나지 않아 적지 못했다.
처음으로 혼자 주도해 끝까지 진행해 본 프로젝트라 감명 깊기도 하면서 보완되었으면 하는 점 또한 있었다.

  • 프로젝트의 기한을 정확히 정해두자
    • 사실 7월에 시작에 8월까지 끝내려 했던 프로젝트였다. 다만 어렵기도 하고, 바쁘기도, 나태해지기도 하면서 예상보다 훨씬 길어졌다. 이는 나 개인이 늘어지는 문제가 있을 뿐만 아니라 다른 분과 협업을 할 때도 중요한 점이 있다고 느꼈다. 거의 완성을 하고 마무리로 수정했으면 하는 부분이 있었는데, 그때 디자이너 님이 인터넷을 사용하지 못하는 환경에 있어 수정이 어려웠기 때문이다. 때문에 같이 준비하는 사람들과 협의 후 기한을 정확히 정하고 그것을 향해 함께 달려나가는 것이 좋다고 느꼈다.
  • 모르는 내용이 있을 때는 공식 문서를 꼼꼼히
    • 개발일지1에서 쿼리셋 필터링 하는 것이 어렵다고 썼는데, 이때 느낀 점이다. 처음에는 구글링에 의존해서 필요한 내용을 찾으려 했는데 (사실 영어라서 공식 문서 읽기 귀찮았다) 그보다는 공식 문서를 먼저 꼼꼼히 읽는 것이 좋다고 깨달았다. 난 장고에 그렇게 익숙한 편이 아니었기에 장고 자체에서 어떤 기능이 있는지를 잘 몰랐다. 이럴 때는 구글링을 많이 해도 더 헷갈릴 때가 생기더라. 그렇기에 공식문서로 기본적인 내용을 먼저 익히는 것이 중요했다.

더 쓰고싶은 바가 생각나면 그때 적기로 하고, 일단은 이쯤에서 마무리한다.

[BOJ] 10866 : 덱 (Python3)

출처: https://www.acmicpc.net/problem/10866

문제

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

  • push_front X: 정수 X를 덱의 앞에 넣는다.
  • push_back X: 정수 X를 덱의 뒤에 넣는다.
  • pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 덱에 들어있는 정수의 개수를 출력한다.
  • empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
  • front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘쨰 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

소스코드

import sys

class Deque:

    def __init__(self):
        self.data = []

    def push_front(self, X):
        self.data.insert(0, X)

    def push_back(self, X):
        self.data.append(X)

    def pop_front(self):
        return self.data.pop(0) if not self.empty() else -1

    def pop_back(self):
        return self.data.pop() if not self.empty() else -1

    def size(self):
        return len(self.data)

    def empty(self):
        return 1 if self.size() == 0 else 0

    def front(self):
        return self.data[0] if not self.empty() else -1

    def back(self):
        return self.data[-1] if not self.empty() else -1

input = sys.stdin.readline
deque = Deque()

for _ in range(int(input())):
    cmd = input().split()
    if cmd[0] == 'push_front':
        deque.push_front(cmd[1])
    elif cmd[0] == 'push_back':
        deque.push_back(cmd[1])
    elif cmd[0] == 'pop_front':
        print(deque.pop_front())
    elif cmd[0] == 'pop_back':
        print(deque.pop_back())
    elif cmd[0] == 'size':
        print(deque.size())
    elif cmd[0] == 'empty':
        print(deque.empty())
    elif cmd[0] == 'front':
        print(deque.front())
    elif cmd[0] == 'back':
        print(deque.back())

[BOJ] 1021 : 회전하는 큐 (Python3)

출처: https://www.acmicpc.net/problem/1021

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

  1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, …, ak이었던 것이 a2, …, ak와 같이 된다.
  2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, …, ak가 a2, …, ak, a1이 된다.
  3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, …, ak가 ak, a1, …, ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

소스코드

import sys

n, m = map(int, sys.stdin.readline().strip().split())
que = [i+1 for i in range(n)]
num = list(map(int, sys.stdin.readline().strip().split()))
cnt = 0

while num:
    if num[0] == que[0]:
        del que[0]
        del num[0]
    elif que.index(num[0]) <= len(que) / 2:
        while num[0] != que[0]:
            que.append(que.pop(0))
            cnt += 1
    elif que.index(num[0]) > len(que) / 2:
        while num[0] != que[0]:
            que.insert(0, que.pop())
            cnt += 1

print(cnt)

풀이

que에 n으로 받은 만큼의 원소를 넣어둔다.
num에 뽑아내려 한 수의 위치를 넣는다.
num의 원소 수가 없어질 때까지 연산 1, 2, 3을 수행한다.

  1. num[0] 과 que[0]이 같을 때 연산 1을 수행한다. 이미 뽑아냈으므로 num 리스트의 원소도 delete 한다.
  2. left 연산. 현재 뽑아내려는 수의 위치가 len(que)/2 보다 작거나 같을 때 시행한다. 현재 뽑아내려는 수가 맨 앞으로 오기 전까지 que.append(que.pop(0))을 해준다. 연산을 한 번 할 때마다 cnt += 1을 해준다.
  3. right 연산. left와 동일.

num의 원소가 없어지면 수를 모두 뽑은 것이므로 cnt를 출력해준다.

SWIM, SWIM! 웹사이트 개발일지 1

소개

제작기간: 2019년 7월~11월
지역과 시간을 선택하면 해당 시간 내에 자유수영을 할 수 있는 수영장 정보를 보여주는 간단한 웹 페이지이다.
screencapture-swimswim-pythonanywhere-2019-11-10-16_00_23크기수정

screencapture-127-0-0-1-8080-2019-11-10-16_03_38크기수정 사이트 주소: http://swimswim.pythonanywhere.com/

제작 동기

때는 2019년 7월.

웹 개발을 여러모로 깔짝대보긴 했으나 제대로 웹 하나를 만들어보지는 못했다.
실력 향상겸 개인 프로젝트로 웹을 처음부터 끝까지 개발해보자는 생각이 들었고, 주제 선정을 고심했다.
당시 수영을 종종 즐기곤 했다. 당시 상황에 맞게 여러 수영장을 돌아다니며 일일입장으로 자유수영을 했는데, 이게 꽤 귀찮았다.
어떤 수영장은 주말에 문을 열지 않고, 어떤 수영장은 특정 요일에는 일일입장을 받지 않는 등 수영장마다 차이가 컸다.

그래서 여러 수영장의 시간 정보를 모아 현재 시간에 맞게 필터링해주는 서비스가 있으면 좋겠다는 생각이 들었다.
이를 바탕으로 SWIM, SWIM 을 제작하게 된다.

준비

‘무엇을’ 만들 것인가 정했으니, 다음은 ‘어떻게’ 만들 것인가를 결정해야 했다.
주변에 웹 개발을 하는 사람이 없기 때문에 혼자 백엔드와 프론트엔드를 다 맡아서 해야 했다.
이전에 웹 퍼블리싱을 공부한 적이 있어 프론트엔드는 어찌 될 것 같은데 백엔드가 고민이었다.
그러던 와중 작년에 혼자 따라해본 장고걸스 튜토리얼이 생각났다.
당시엔 웹에 대해 아는 것이 별로 없어 공부하다 힘들었던 기억이 있지만, 한번 해봤으니 더 괜찮을 것 같았다.
어떻게 만들지를 대충 결정했으니 개발에 돌입할 시간이었다.

난관

역시 한번 해본 적이 있어서 그런지 백엔드 구현은 생각보다 어렵진 않았다.
다만 몇 가지 난관이 있었는데, 데이터베이스를 구현하는 것과 queryset으로 시간, 장소를 필터링하는 것이었다. 특히 후자가 꽤 까다로웠다.

내가 원하는 것은

  1. 1페이지에서 시간(몇 시간 내인지)과 장소(도시 이름)를 받는다.
  2. Pool 모델에서 1페이지에 받은 도시에 해당하는 것을 필터링한다.
  3. 2번에서 필터된 Pool의 Timetable에서 현재 시간과 1번에서 받은 시간 내에 start time과 end time이 있는 queryset을 찾는다.

여기까지는 괜찮았지만, 더욱 어려운 문제가 있었다.
현재 시간에 사용자에게 받은 시간을 더했을 때 24시간이 넘어가는 경우였다. 거기다 일요일에서 월요일로 넘어가는 경우는 또다시 예외처리를 해줘야했다.
복잡했기에 진전이 잘 되지 않았다. Django QuerySet API 공식 문서를 몇 번 정독하고 구글링을 끊임없이 하며 어떻게든 비슷한 부분을 찾으려 노력했다.
결국 원하는 대로 필터링을 해낼 수 있었고, 기본적인 틀을 잡는데 성공한다.

screencapture-127-0-0-1-8080-2019-10-10-05_52_53

screencapture-127-0-0-1-8080-2019-10-10-05_53_13

[BOJ] 1966 : 프린터 큐 (Python3)

출처: https://www.acmicpc.net/problem/1966

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

  1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
  2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음줄에 N개 문서의 중요도가 주어지는데, 중요도는 1 이상 9 이하이다. 중요도가 같은 문서가 여러 개 있을 수도 있다. 위의 예는 N=4, M=0(A문서가 궁금하다면), 중요도는 2 1 4 3이 된다.

출력

각 test case에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

소스코드

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    que = list(map(int, input().split()))
    ans = [0]*n
    ans[m] = 'T'
    cnt = 0
    while True:
        if que[0] == max(que):
            cnt += 1
            if ans[0] == 'T':
                break
            else:
                que.pop(0)
                ans.pop(0)
        else:
            que.append(que.pop(0))
            ans.append(ans.pop(0))
    print(cnt)

풀이

que 리스트에 사용자가 입력한 중요도를 저장한다.
ans 리스트를 n개 만큼 0으로 원소를 채우고, 중요도가 궁금한 m번째 원소만 ‘T’로 원소를 바꾼다. m번째 원소가 몇 번째로 인쇄되는지 알기 위함이다.
그 후 반복문을 통해

  1. que[0]이 max라면 cnt+=1을 하고,
    1-1. 현재 ans[0] == ‘T’이면, 즉 찾고 있던 원소이면 break를 하고 cnt를 출력한다. 1-2. 찾고 있는 원소가 아니면 max를 그냥 pop한다. ans[0]도 함께 pop한다.
  2. que[0]이 max 값이 아니라면 que.apend(que.pop(0))을 하여 배열의 맨 뒤로 보낸다. ans도 똑같이 한다.

[BOJ] 11866 : 요세푸스 문제 0 (Python3)

출처: https://www.acmicpc.net/problem/11866

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

소스코드

import sys

class circularQueue():

	def __init__(self, n):
		self.maxCount = n
		self.data = [''] * n
		self.count = 0
		self.front = -1
		self.rear = -1

	def size(self):
		return self.count

	def isEmpty(self):
		return self.count == 0

	def enqueue(self, item):
		if self.count == self.maxCount:
			raise IndexError('Queue Full')
		self.rear = (self.rear + 1) % self.maxCount
		self.data[self.rear] = item
		self.count += 1

	def dequeue(self):
		if self.isEmpty():
			raise IndexError('Queue Empty')
		self.front = (self.front + 1) % self.maxCount
		self.count -= 1
		return self.data[self.front]

n, k = map(int, sys.stdin.readline().strip().split())
circle = circularQueue(n)

for i in range(n):
	circle.enqueue(i+1)

outputs= "<"

while True:
	# k번째 수의 전까지 deque를 한 후 enqueue를 해 큐의 뒤쪽으로 가게 한다. 그 후 k번째 수를 outputs에 집어넣고 dequeue한다.  
	for i in range(k-1):
		circle.enqueue(circle.dequeue())
	outputs += str(circle.dequeue())
	if circle.isEmpty():
		break
	else:
		outputs += ", "

sys.stdout.write(outputs+">")

원형큐를 사용해서 풀이했다.
정답률은 높은데 원형큐의 front 개념이 헷갈려서 초반에 꽤 헤맸다.
그럼에도 코드를 작성했는데 답이 계속 틀리게 나와 의문이었지만, k와 n을 입력받는 순서를 반대로 해서 그런 것이었다.
쉬운 실수를 하지 않도록 주의하자.

[BOJ] 2164 : 카드2 (Python3)

출처: https://www.acmicpc.net/problem/2164

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1≤N≤500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

소스코드

import sys, collections

n = int(sys.stdin.readline())
card = collections.deque(int(i+1) for i in range(n))

while len(card) > 1:
	card.popleft()
	card.append(card[0])
	card.popleft()

print(card[0])


[BOJ] 10845 : 큐 (Python3)

출처: https://www.acmicpc.net/problem/10845

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

  • push X: 정수 X를 큐에 넣는 연산이다.
  • pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 큐에 들어있는 정수의 개수를 출력한다.
  • empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
  • front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

소스코드

import sys

class Queue:

	def __init__(self):
		self.data = []

	def push(self, x):
		self.data.append(x)

	def pop(self):
		return self.data.pop(0) if self.size() != 0 else -1

	def size(self):
		return len(self.data)

	def empty(self):
		return 1 if self.size() == 0 else 0

	def front(self):
		return self.data[0] if self.size() != 0 else -1

	def back(self):
		return self.data[self.size()-1] if self.size() != 0 else -1

input = sys.stdin.readline
n = int(input())
q = Queue()

for i in range(n):
	cmd = input().split()
	if cmd[0] == 'push':
		q.push(cmd[1])
	elif cmd[0] == 'pop':
		print(q.pop())
	elif cmd[0] == 'size':
		print(q.size())
	elif cmd[0] == 'empty':
		print(q.empty())
	elif cmd[0] == 'front':
		print(q.front())
	elif cmd[0] == 'back':
		print(q.back())

[Python] 환형 큐 (Priority Queues) (2)

프로그래머스 자료구조 강의와 각종 인터넷 자료를 참고하여 재구성한 내용입니다.

Circular Queue

  • Linear queue에서는 큐가 꽉 차면 dequeu를 하더라도 새 element를 넣을 수 없다.
    • queue의 front를 옮기고 rear는 큐의 맨 뒤에 있기 때문에
  • 이를 해결하기 위해서는 새롭게 시작하기 위해 queue를 reset해야 함
  • Circular queue는 마지막에 큐를 끝내는 대신 새 포지션을 시작한다 queue
(출처: studytonight)

Circular Queue의 기본 특징

  1. head는 큐의 맨 앞을 가리키고, tail은 큐의 맨 끝을 가리킨다.
  2. 처음 큐가 비었을 때 head와 tail은 같은 곳을 가리킨다
  3. 새로 추가된 데이터는 tail이 가리켰던 위치로 추가된다. tail은 다음 위치를 가리킨다.
  4. 환형 큐에서 데이터는 실질적으로 삭제되지 않는다. dequeue가 실행될 때 head 포인터만 한 칸 증가한다. 큐 데이터는 head와 tail 사이에 있는 것만 포함되므로 그 바깥에 있는 데이터는 더이상 큐의 일부분이 되지 않는다.
  5. head와 tail은 큐의 맨 끝에 다다를 때 0으로 초기화된다.
  6. head와 tail은 서로 cross할 수 있다. 즉, head pointer가 tail보다 커질 수 있다. 이는 dequeue를 몇 회 시행하고 tail이 다시 초기화 될 때 일어난다.

Circular Queue 구현

python list를 이용한 구현

class CircularQueue:

	def __init__(self, n):
        self.maxCount = n
        self.data = [None] * n
        self.count = 0
        self.front = -1
        self.rear = -1

    def size(self):
    	return self.count

    def isEmpty(self):
    	return self.count == 0

    def isFull(self):
    	return self.count == self.maxCount

    def enqueue(self, x):
    	if self.isFull():
        	raise IndexError('Queue full')
        self.rear = (self.rear + 1) % self.maxCount
        self.data[self.rear] = x
        self.count += 1

    def dequeue(self):
    	if self.isEmpty():
            raise IndexError('Queue empty')
        self.front = (self.front + 1) % self.maxCount
        x = self.data[self.front]
        self.count -= 1
        return x

    def peek(self):
    	if self.isEmpty():
        	raise IndexError('Queue empty')
        return self.data[(self.front+1) % self.maxCount]

참조

[Python] 큐 (Queue) (1)

프로그래머스 자료구조 강의와 각종 인터넷 자료를 참고하여 재구성한 내용입니다.

Queue

  • 컴퓨터의 기본적인 자료구조 중 하나

  • 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조

  • LIFO의 구조를 가지는 스택과 정반대

큐의 추상적 자료구조 구현

  • array를 이용하여 구현

    • python list와 method 이용
  • linked list를 이용하여 구현

    • 양방향 연결리스트 이용

큐의 동작

  • 초기 상태: empty queue

  • 데이터 원소 A를 큐에 추가

  • 데이터 원소 B를 큐에 추가

  • 데이터 원소 꺼내기


Q = Queue()

Q.enqueue(A)

Q.enqueue(B)

r1 = Q.dequeue()

r2 = Q.dequeue()

구현(1) - Array

class ArrayQueue:

	def __init__(self):
    	self.data = []

	def size(self):
    	return len(self.data)

    def isEmpty(self):
    	return self.size == 0

    def enqueue(self, item):
		self.data.append(item)

    def dequeue(self):
    	return self.data.pop(0)

    def peek(self):
    	return self.data[0]

문제점

  • dequeue()의 경우 시간복잡도는 O(N)이다.

    • enqueue는 리스트의 맨 끝에서만 일어나지만 dequeue는 두번째 원소~마지막 원소를 모두 한 칸씩 앞당겨야하기 때문이다.

구현(2) - Doubly Linked List

class Node:

	def __init__(self, data):
    	self.data = data
        self.next = None
        self.prev = None

class LinkedListQueue:

	def __init__(self):
    	self.head = None
        self.tail = None

	def isEmpty(self):
    	if not self.head:
        	return True
        return False

    def enqueue(self, data):
    	if self.tail == None:
        	self.head = Node(data)
            self.tail = self.head
        else:
        	self.tail.next = Node(data)
            self.tail.next.prev = self.tail
            self.tail = self.tail.next

    def dequeue(self):
    	if self.head == None:
        	return None
        else:
        	temp = self.head.data
            self.head = self.head.next
            self.head.prev = None
            return temp

    def peek(self):
    	return self.head.data

    def size(self):
    	temp = self.head
        cnt = 0
        while temp != None:
        	cnt += 1
            temp = temp.next
        return cnt

참조

[BOJ] 17298 : 오큰수 (Python3)

출처: https://www.acmicpc.net/problem/17298

문제

크기가 N인 수열 A = A1, A2, …, AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, …, AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), …, NGE(N)을 공백으로 구분해 출력한다.

소스코드

import sys
input = sys.stdin.readline

n = int(input())
 # 수열을 받아두는 리스트
inputs = list(map(int, input().split()))
 # 오큰수를 찾지 못한 inputs의 index를 모아두는 리스트
stack = [0]
 # 출력할 오큰수를 모아두는 리스트. 미리 -1로 설정해두고 오큰수를 찾은 값만 바꿔준다.
outputs = [-1 for _ in range(n)]

for i in range(1, n):
     # 오큰수를 찾기 위한 반복문
    while stack and inputs[stack[-1]] < inputs[i]:
        outputs[stack[-1]] = inputs[i]
        stack.pop()
    stack.append(i)
    i += 1

for i in outputs:
    print(i, end=' ')

풀이

쉽게 생각하면 이중 반복문을 쓰게되는데 시간복잡도가 O(N^2), N의 범위가 1 ≤ N ≤ 1,000,000 이므로 시간초과가 뜬다.
때문에 스택을 사용해서 풀어야 한다.
주의할 점은 스택에 결과값이 아니라 아직 오큰수를 찾지 못한 inputs의 index를 넣어둬야 한다.

그래서 inputs[i] 값이 inputs[stack[-1]] (오큰수를 찾지 못한 수 중 가장 위에 있는 것) 보다 크다면, 즉 오큰수를 찾았다면
outputs의 i 자리에 있는 값을 inputs에 있는 값으로 바꿔준다. 그 인덱스는 오큰수를 찾았으므로 stack에서 pop해준다.
stack에 있는 다른 인덱스 또한 inputs[i] 보다 작다면 오큰수를 찾은 것이므로 반복해준다.

오큰수를 다 찾았거나 없다면 다음 인덱스로 넘어가야하므로 stack에 i를 추가해주고 i += 1을 해준다.

[BOJ] 1874 : 스택 수열 (Python3)

출처: https://www.acmicpc.net/problem/1874

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

소스코드

class Stack:
    def __init__(self):
        self.data = []

    def push(self, item):
        self.data.append(item)

    def pop(self):
        if self.size() == 0:
            return -1
        else:
            return self.data.pop()

    def size(self):
        return len(self.data)

    def isEmpty(self):
        return 1 if self.size() == 0 else 0

    def top(self):
        return self.data[-1] if self.size() else -1

import sys
input = sys.stdin.readline

n = int(input())

# user가 input한 수의 리스트. 예제1에서 [4,3,6,8,7,5,2,1]이 해당
inputs = []
# output 할 +와 -를 담아놓는 리스트
outputs = []
# 문제에서 사용할 스택
stack = Stack()
# inputs 리스트에서 위치를 가리키기 위해 사용
count = 0

# user의 input을 리스트에 집어 넣어 줌
for i in range(n):
    inputs.append(int(input()))

for i in range(n):
    stack.push(i+1)
    outputs.append('+')
    # 스택의 가장 마지막 원소와 inputs의 원소가 같으면 pop해야 한다. (lst의 원소 개수를 넘으면 안되므로 count < n)
    while count < n and stack.top() == inputs[count]:
        stack.pop()
        outputs.append('-')
        count += 1

# 스택이 비어있으면 원소가 모두 pop된 것이므로 outputs의 +,-를 보여준다
if stack.isEmpty():
    for i in outputs:
        print(i)
else:
    print('NO')

[BOJ] 9012 : 괄호 (Python3)

출처: https://www.acmicpc.net/problem/9012

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

소스코드

스택을 활용한 풀이

class Stack:
    def __init__(self):
        self.data = []

    def push(self, item):
        self.data.append(item)

    def pop(self):
        if self.size() == 0:
            return -1
        else:
            return self.data.pop()

    def size(self):
        return len(self.data)

    def isEmpty(self):
        if self.size() == 0:
            print('YES')
        else:
            print('NO')

t = int(input())

for i in range(t):
    stack = Stack()
    vps = input()
    flag = True
    for j in vps:
        if j == '(':
            stack.push(j)
        else:
            pop = stack.pop()
            if pop == -1:
                print('NO')
                flag = False
                break
    if flag:
        stack.isEmpty()

풀이

vps에 문자열을 받아 for 적용. ‘(‘가 나오는 경우 스택에 넣어준다. ‘)’가 나오는 경우에는 스택에 있는 ‘(‘을 pop해 없앤다.

여기서 NO가 나오려면

  1. ’)’의 쌍이 되는 ‘(‘이 없거나
  2. ’(‘의 쌍이 되는 ‘)’이 없어야 한다.

1은 pop을 하려는데 스택에 더이상 원소가 없을 때이다. self.size() == 0이 되어 -1을 return. ‘NO’를 출력, flag를 False로 바꿔 for문을 break한다.

2는 스택에 ‘(‘가 남아있지만 vps 반복문이 끝나는 경우. stack.isEmpty()로 비어있지 않으면 ‘NO’를 출력한다.

vps for문이 끝났는데 스택이 비어있으면 모든 쌍이 맞으므로 ‘YES’를 출력한다.

간단한 풀이

t = int(input())

for i in range(t):
    vps = input()
    cnt = 0
    for j in vps:
        if j == '(':
            cnt += 1
        else:
            cnt -= 1

        if cnt < 0:
            print('NO')
            break
    if cnt == 0:
        print('YES')
    elif cnt > 0:
        print('NO')

[BOJ] 4949 : 균형잡힌 세상 (Python3)

출처: https://www.acmicpc.net/problem/4949

문제

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.

정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.

문자열에 포함되는 괄호는 소괄호(“()”) 와 대괄호(“[]”)로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

  • 모든 왼쪽 소괄호(“(“)는 오른쪽 소괄호(“)”)와만 짝을 이룰 수 있다.
  • 모든 왼쪽 대괄호(“[“)는 오른쪽 대괄호(“]”)와만 짝을 이룰 수 있다.
  • 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
  • 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
  • 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호(“( )”) 대괄호(“[ ]”)등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다.

입력의 종료조건으로 맨 마지막에 점 하나(“.”)가 들어온다.

출력

각 줄마다 해당 문자열이 균형을 이루고 있으면 “yes”를, 아니면 “no”를 출력한다.

소스코드

class Stack:
    def __init__(self):
        self.data = []

    def push(self, item):
        self.data.append(item)

    def pop(self):
        if self.size() == 0:
            return -1
        else:
            return self.data.pop()

    def size(self):
        return len(self.data)

    def isEmpty(self):
        if self.size() == 0:
            print('yes')
        else:
            print('no')


while True:
    stack = Stack()
    flag = True
    user_input = input()
    if user_input == '.':
        break
    for c in user_input:
        if c == '(' or c == '[':
            stack.push(c)
        elif c == ')':
            pop = stack.pop()
            if pop != '(':
                print('no')
                flag = False
                break
        elif c == ']':
            pop = stack.pop()
            if pop != '[':
                print('no')
                flag = False
                break
    if flag:
        stack.isEmpty()

풀이

스택을 활용해 풀이했다. 풀이법은 9012 문제와 거의 비슷하므로 생략.

반례가 안나오는데도 계속 ‘틀렸습니다’가 나와서 당황했는데, 알고보니 ‘yes’를 출력해야 할 것을 ‘YES’로 출력해 틀린 것이었다.
문제를 잘 읽자.

[BOJ] 10828 : 스택 (Python3)

출처: https://www.acmicpc.net/problem/10828

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

  • push X: 정수 X를 스택에 넣는 연산이다.
  • pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 스택에 들어있는 정수의 개수를 출력한다.
  • empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
  • top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

소스코드

import sys

class Stack:
    def __init__(self):
        self.data = []

    def push(self, item):
        self.data.append(item)

    def pop(self):
        if self.size() == 0:
            return -1
        else:
            num = self.data.pop()
            return num

    def size(self):
        return len(self.data)

    def empty(self):
        if self.size() == 0:
            return 1
        else:
            return 0

    def top(self):
        if self.size() == 0:
            return -1
        else:
            return self.data[-1]

n = int(input())
stack = Stack()

while n:
    input = sys.stdin.readline
    input_split = input().split()
    cmd = input_split[0]
    if cmd == 'push':
        stack.push(int(input_split[1]))
    elif cmd == 'pop':
        print(stack.pop())
    elif cmd == 'size':
        print(stack.size())
    elif cmd == 'empty':
        print(stack.empty())
    else:
        print(stack.top())
    n -= 1


풀이

input을 이용하면 시간 초과가 발생하므로 sys.stdin.readline을 이용해야 한다.
시간 초과가 발생하는 이유는 https://www.acmicpc.net/problem/15552 참고.

[BOJ] 10773 : 제로 (Python3)

출처: https://www.acmicpc.net/problem/10773

문제

나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.

재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다.

재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다.

재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자!

입력

첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)

이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 “0” 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.

정수가 “0”일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.

출력

재민이가 최종적으로 적어 낸 수의 합을 출력한다.

소스코드

import sys
input = sys.stdin.readline

k = int(input())
lst = []

for i in range(k):
    num = int(input())
    if num == 0:
        lst.pop()
    else:
        lst.append(num)

print(sum(lst))

풀이

시간을 줄이기 위해 sys.stdin.readline() 이용

[Python] 스택 (Stack)

프로그래머스 자료구조 강의와 각종 인터넷 자료를 참고하여 재구성한 내용입니다.

Stack

  • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료구조
  • 후입선출(LIFO - Last In First Out)의 특징
  • Pushdown list라고도 한다

스택의 동작

  • S = Stack() : 초기 상태
  • S.push(A) : 데이터 원소 A를 스택에 추가
  • S.pop() : 스택의 가장 윗 데이터를 return하고 삭제
  • S.isEmpty() : 스택이 비었다면 1 반환, 그렇지 않다면 0 반환
  • S.peek() : 스택의 가장 윗 데이터를 제거하지 않고 반환

스택 구현

  • array를 이용하여 구현
    • python list와 method 이용
class ArrayStack:
	def __init__(self):
    	self.data = []

    def size(Self):
    	return len(self.data)

    def isEmpty(Self):
    	return self.size() == 0

	def push(self, item):
    	return self.data.append(item)

    def pop(self):
    	return self.data.pop()

    def peek(self):
    	return self.data[-1]

참조

[BOJ] 1436 : 영화감독 숌 (Python3)

출처: https://www.acmicpc.net/problem/1436

문제

666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다.

하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다.

종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, …. 과 같다.

따라서, 숌은 첫 번째 영화의 제목은 세상의 종말 666, 두 번째 영화의 제목은 세상의 종말 1666 이렇게 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 숫자) 와 같다.

숌이 만든 N번째 영화의 제목에 들어간 숫자를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.

소스코드

브루트포스를 이용하면 간단하게 풀 수 있는 문제였다.

n = int(input())
cntNum = cnt = 0

while cnt != n:
    cntNum += 1
    if "666" in str(cntNum):
        cnt += 1

print(cntNum)

처음에는 이렇게 풀었고, 밑 방법과 같이 변수를 하나 더 줄일 수 있었다.

n = int(input())
movieNum = 666

while n:
    if "666" in str(movieNum):
        n -= 1
    movieNum += 1

print(movieNum-1)

[BOJ] 1018 : 체스판 다시 칠하기 (Python3)

출처: https://www.acmicpc.net/problem/1018

문제

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

입력 & 출력

첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

소스코드

n, m = map(int, input().split())

board = []

for i in range(n):
    board.append(input())

wMin = bMin = tempMin = 0 #W의 경우 최소값과 B의 경우 최소값, 임시 최소값
min = 64

for i in range(n-7):
    for j in range(m-7):
        for k in range(i, i+8):
            # W의 경우
            for l in range(j, j+8):
                if (k+l-i-j) % 2 == 0: # 이때는 보드판이 W여야 함
                    if board[k][l] != 'W':
                        wMin += 1
                else:
                    if board[k][l] != 'B':
                        wMin += 1
             # B의 경우
            for l in range(j, j+8):
                if (k+l-i-j) % 2 == 0: # 이때는 보드판이 B여야 함
                    if board[k][l] != 'B':
                        bMin += 1
                else:
                    if board[k][l] != 'W':
                        bMin += 1
        tempMin = wMin if wMin < bMin else bMin
        min = tempMin if tempMin < min else min
        wMin = bMin = tempMin = 0

print(min)

풀이

전체 개요

  1. 입력받은 배열에서 우선 맨 위 왼쪽 8*8 개의 최소값을 구한다. 구한 최소값을 min이라는 변수에 저장한다.
  2. 구하는 범위를 한 칸 오른쪽으로 옮겨 해당 범위의 최소값을 구한다. 이때 최소값이 이 전에 구한 최소값보다 작을 경우 min 값을 바꾼다.
  3. m-7 범위까지 모두 계산해 더이상 오른쪽에 남은 범위가 없으면 구하는 범위를 한 칸 밑으로 옮긴다.
  4. n-7 범위까지 구한 후 최종적인 최소값을 구한다.

최소값 구하기

문제에 나왔듯 맨 왼쪽 위쪽 칸이 흰색(W)인 경우와, 검은색(B)인 경우로 나누어 최소값을 구해야 한다.

  1. W의 경우
    • (k+l-i-j) % 2 == 0 일 때, 즉 해당 칸의 k+l의 값이 짝수일 때는 W가 와야 한다. (i와 j는 칸을 옮겼을 경우 더하기 때문에 다시 빼줘야 함)
    • board[k][l] != ‘W’이면 w의 경우의 최소값인 wMin += 1을 한다.
    • k+l 값이 홀수일 때도 != ‘B’이면 wMin += 1을 한다.
  2. B의 경우
    • 마찬가지. 칸에 B 혹은 W가 오지 않으면 bMin += 1을 한다.

[CSS] line-height를 이용한 텍스트 수직 중앙 정렬 (text vertical-align)

swim 웹을 제작할 때 수직정렬 때문에 애를 조금 먹었다.
그 중 밑과 같은 문제가 발생했는데, image 텍스트 background의 height를 조정했더니 수직 중앙 정렬이 안 되는 것. 여러 해결법을 찾긴 했지만, div를 이것저것 추가하고 싶지 않았기 때문에 가장 간단한 방법을 원했다.

그렇게 발견한 것이 line-height를 통한 중앙 정렬. 해결법은 아주 쉬운데, 배경 박스의 높이와 글자의 line height를 똑같이 설정하면 된다.

.time_list h3{
  font-size: 30px;
  color: #ffffff;
  background-color: #0090ff;
  display: inline-block;
  height: 32px;
  line-height: 32px;
}

원리

image

line height에서 font size를 제외한 공간을 leading이라 한다. 여기서 line-height를 증가시키면 이 부분만 위 아래로 똑같이 늘어나게 된다.

[Python] 양방향 연결 리스트 (Doubly Linked Lists)

양방향 연결 리스트 (Doubly linked lists)

  • 단방향 연결 리스트는 역방향 탐색이 쉽지 않다. 또한 단방향(head) 쪽으로만 삽입, 삭제, 조회가 가능.
    • 이를 해결하려면? 양방향 이동 구현
    • 다음 노드와 이전 노드의 이동이 가능하도록 구성

doblylinkedlists

(출처: wikidocs)
  • 단일 연결 리스트보다 손상에 강하다
# 노드 구조 확장
class Node:

    def __init__(self, item):
        self.data = item
        self.next = None
        self.prev = None


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next: # self.tail 에 dummy node를 놓으므로
            curr = curr.next
            result.append(curr.data)
        return result

    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount + 1:
            raise IndexError
        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:  
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while pos > i:
                curr = curr.next
                i += 1
        return curr


    def insertBefore(self, next, newNode):
        prev = next.prev
        newNode.prev = prev
        prev.next = newNode
        newNode.next = next
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAfter(self, prev, newNode):
        next = prev.next
        prev.next = newNode
        newNode.prev = prev
        next.prev = newNode
        newNode.next = next
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        prev = getAt(pos-1)
        return insertAfter(prev, newNode)


    def popAfter(self, prev):
        curr = prev.next
        prev.next = curr.next
        curr.next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popBefore(self, next):
        prev = next.prev
        prev.prev.next = next
        next.prev = prev.prev
        self.nodeCount -= 1
        return prev.data

    def popAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            raise IndexError
        if self.nodeCount == 0:
            raise IndexError
        prev = self.getAt(pos-1)
        return self.popAfter(prev)

[Python] 연결 리스트 (Linked Lists) - 단순 연결, Dummy Node

프로그래머스의 자료구조 강의를 들은 뒤, 인터넷의 여러 자료를 참고해 재구성한 내용입니다.

연결 리스트란?

  • 앞에 있는 것이 뒤에 있는 것을 가리키도록 연결된 자료구조
  • 각각의 아이템을 노드(Node)라고 부른다
    • 노드는 Data와 Link를 담고 있음
    • 노드 내의 데이터는 다른 구조로 이루어질 수 있다

배열과의 차이점

배열 | 연결 리스트 — | — 연속한 저장 공간 위치 | 임의의 위치 특정 원소 지칭 매우 간편 O(1) | 불편. 선형탐색과 유사O(n) 데이터의 추가/삭제가 불편|데이터의 추가/삭제가 용이 크기를 키우기 어려움| 용이 정적인 자료 구조 | 동적인 자료 구조

단순 연결 리스트 (Singly Linked List)

  • 노드를 한 방향으로 연결하는 자료구조

###Node

class Node:
	def __init__(self, item):
    	self.data = item
        self.next = None

class LinkedList:
	def __init__(self):
    	self.nodeCount = 0
        self.head = None
        self.tail = None

특정 원소 참조

def getAt(self, pos):
	if pos <= 0 or pos > self.nodeCount:
    	return None
    i = 1
    curr = self.head
    while i < pos:
    	curr = curr.next
        i += 1
    return curr

원소의 삽입

def insertAt(self, pos, newNode):
	if pos < 1 or pos > self.nodeCount + 1:
    	return False
    if pos == 1:
    	newNode.next = self.head
        self.head  = newNode
    else:
    	prev = self.getAt(pos-1)
       	newNode.next = prev.next
        prev.next = newNode
    if pos == self.nodeCount + 1
        self.tail = newNode
    self.nodeCount += 1
    return True

원소의 삭제

삭제하려는 데이터를 data에 저장해두고, 삭제가 완료되면 True를 return

def popAt(self, pos):
	if pos < 1 or pos > self.nodeCount:
    	return False
    elif pos == 1 and self.nodeCount == 1:
    	data = self.head.data
        self.head = None
        self.tail = None
    else:
    	prev = self.getAt(pos-1)
        data = prev.next.data
        if pos == self.nodeCount:
        	self.tail = prev
            prev.next = None
        else:
        	prev.next = prev.next.next
    self.nodeCount -= 1
    return True

Dummy Node

  • ‘특정 원소’를 삽입/삭제하는 코드가 아니라, ‘특정 원소의 다음’을 삽입/삭제하는 코드를 짠다면?
  • 맨 앞 원소를 삽입하고 제거하기 힘들어짐
    • -> 맨 앞에 더미 노드 추가
    • 더미 노드: 실제로 데이터를 가지지는 않고, 구현의 편의를 위해 두는 무의미한 노드

코드 구현

class Node:

    def __init__(self, item):
        self.data = item
        self.next = None


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail


    def traverse(self):
        result = []
        curr = self.head
        while curr.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount + 1:
            raise IndexError

        i = 0
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1

        return curr


    def insertAfter(self, prev, newNode):
        newNode.next = prev.next
        if prev.next == None:
            self.tail = newNode
        prev.next = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False
        if pos != 1 and pos == self.nodeCount + 1:
            prev = self.tail
        else:
            prev = self.getAt(pos-1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        if prev.next == None:
            return None
        curr = prev.next
        if curr.next == None:
            self.tail = prev

        prev.next = curr.next
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount + 1:
            raise IndexError
        prev = self.getAt(pos-1)
        return self.popAfter(prev)

[BOJ] 7568 : 덩치 (c언어)

출처: https://www.acmicpc.net/problem/7568

문제

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 “더 크다”고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55,173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, “덩치”로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다.

N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 “큰 덩치”의 사람의 수로 정해진다. 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다. 이렇게 등수를 결정하면 같은 덩치 등수를 가진 사람은 여러 명도 가능하다. 아래는 5명으로 이루어진 집단에서 각 사람의 덩치와 그 등수가 표시된 표이다.

위 표에서 C보다 더 큰 덩치의 사람이 없으므로 C는 1등이 된다. 그리고 A, B, D 각각의 덩치보다 큰 사람은 C뿐이므로 이들은 모두 2등이 된다. 그리고 E보다 큰 덩치는 A, B, C, D 이렇게 4명이므로 E의 덩치는 5등이 된다. 위 경우에 3등과 4등은 존재하지 않는다. 여러분은 학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다

소스코드

#include <stdio.h>

int main(void) {
	int n, i, j, a[50][2], b[50] = { 0, };
	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%d %d", &a[i][0], &a[i][1]);
	}

	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (a[i][0] < a[j][0] && a[i][1] < a[j][1]) b[i]++;
		}
	}

	for (i = 0; i < n; i++) printf("%d ", b[i] + 1);
}

풀이

  1. a 배열로 전체 학생의 몸무게와 키를 입력받는다.
  2. a 배열을 for문으로 돌리면서 i번째 학생의 덩치가 j번째 학생의 덩치보 다 작을 경우에 b[i]배열을 ++한다.
  3. 이는 나보다 덩치가 큰 학생의 수를 나타내며, 곧 나의 덩치 순위가 된다.
  4. 0부터 시작했으므로 전체 1을 더해 출력한다.

[BOJ] 2798 : 블랙잭 (c언어)

출처: https://www.acmicpc.net/problem/2798

문제


카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력


첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

소스코드



#include <stdio.h>

#include <stdlib.h>



int main(void) {

	int m, n, i, j, k, temp, max = 0;

	scanf("%d %d", &m, &n);



	int *arr = (int*)malloc(sizeof(int) * m);

	for (i = 0; i < m; i++) {

		scanf("%d", &arr[i]);

	}



	for (i = 0; i <= m - 3; i++) {

		for (j = i + 1; j <= m - 2; j++) {

			for (k = j + 1; k <= m - 1; k++) {

				temp = arr[i] + arr[j] + arr[k];

				if (temp <= n && temp > max) max = temp;

			}

		}

	}



	printf("%d", max);

}

풀이


브루트 포스 개념을 이용하는 문제.

동적할당을 이용해서 풀었지만 굳이 사용하지 않아도 무방할 듯 하다.