완전탐색 (Brute-Force-Search) 문제 2 - Boardcover

• height(H) * width(W)의 보드가 검은색과 흰색으로 채워져 있다.
• 모든 흰칸을 ‘ㄱ’ 모양의 흰색 블록으로 덮고 싶다.
• 블록은 회전 가능하지만 겹치거나 검은색 블록을 침범하거나 밖으로 이탈되어서는 안된다.
• 보드가 있을 때 이를 덮는 방법의 수를 계산하는 프로그램을 만드시오.
• 알고리즘 문제해결 전략 p.159 게임판 덮기

완전탐색 (Brute-Force-Search) 문제 1 - picnic

• 학교에서 소풍을 가려고 한다.
• 학생들을 두명씩 짝지어 행동하게 하려고 한다.
• 단, 서로 친구인 경우에만 짝을 지어야 한다.
• 서로 친구인 경우의 쌍이 주어질 때, 학생들을 짝지을 수 있는 방법의 수를 구하는 프로그램을 구현하라.
• n(학생 수)은 항상 짝수이다.
• 알고리즘 문제해결 전략 1권 p.157

• 이번에는 사용자가 숙소 업체 플랫폼 사이트에서 특정 검색키워드, 숙박할 인원 조건에 해당하는 숙소를 검색할 때 정규식을 사용하여 조건에 해당되는 숙소를 찾는 방법에 대해 알아볼 것이다.

이진트리(Binary Tree)란?

• 어떤 노드의 자식 노드의 수가 최대 2개인 트리

• 공집합 혹은 루트(root)와 왼쪽 서브 트리, 오른쪽 서브 트리로 이루어진 유한 집합, 각각의 서브 트리는 모두 이진 트리이다.

• 트리는 connected acyclic graph

  • 루트 노드(root)를 반드시 가진다.
  • 트리를 구성하는 노드 간 단순 경로가 존재한다.

• 트리는 1개 이상의 노드로 이루어진 유한 집합

  • 루트 노드(root)를 반드시 가진다.
  • 나머지 노드들은 분리집합 T1, …, Tn으로 분할 가능
    • T1, T2 등은 각각의 하나의 트리(서브 트리)가 된다.

• 이번 포스트에서는 오늘 해결했던 알고리즘 문제에 대한 다양한 해답에 대해 소개해볼 것이다.

문제 : 완주하지 못한 선수

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

Circular Queue 란?

• 원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조이다.
• rear를 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때, 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용 할 수 없다.
• 원형큐에서는 배열의 첫 인덱스부터 다시 데이터 삽입이 가능하다.

• 이번 포스트에서는 python에서 excel 파일에 대한 기본적인 사용 방법을 알아볼 것이다.

• 이번 포스트에서는 python에서 텍스트 파일에 대한 기본적인 사용 방법을 알아볼 것이다.

CSV란? (Comma-separated-Values)

• 몇 가지 필드를 쉼표(,)로 구분한 텍스트 데이터 및 텍스트 파일이다.
• 확장자는 .csv이며 MIME 형식은 text/csv이다.
• 비슷한 포맷으로는 탭으로 구분하는 ‘tab-separated values’(TSV)나, 반각 스페이스로 구분하는 ‘space-separated values’(SSV) 등이 있으며, 이것들을 합쳐서 character-separated values(CSV), delimiter-separated values라고 부르는 경우가 많다.

정규표현식이란?

---

• 특정한 규칙을 가진 문자열의 집합을 표현하는데 사용하는 형식 언어
• 프로그래밍 언어 혹은 텍스트 에디터 등에서 문자열의 검색과 치환을 위한 용도로 사용
• 정규표현식에서 사용하는 기호를 메타 문자라고 한다.
• 메타 문자(meta characters) : 원래 그 문자가 가진 뜻이 아닌 표현식 내부에서 특정한 의미를 갖는 문자
  • ex) . 6 $ * + ? { } [ ] \ | ( )