문제 설명

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

numbers의 길이는 2 이상 100 이하입니다. numbers의 모든 수는 0 이상 100 이하입니다.

입출력 예

입출력 예 설명

입출력 예 #1

2 = 1 + 1 입니다. (1이 numbers에 두 개 있습니다.) 3 = 2 + 1 입니다. 4 = 1 + 3 입니다. 5 = 1 + 4 = 2 + 3 입니다. 6 = 2 + 4 입니다. 7 = 3 + 4 입니다. 따라서 [2,3,4,5,6,7] 을 return 해야 합니다.

입출력 예 #2

2 = 0 + 2 입니다. 5 = 5 + 0 입니다. 7 = 0 + 7 = 5 + 2 입니다. 9 = 2 + 7 입니다. 12 = 5 + 7 입니다. 따라서 [2,5,7,9,12] 를 return 해야 합니다.

Solution

두 개 뽑는다 라는 말을 봤을 때 '아 이건 몇개 중 몇개 뽑는 조합 문제겠구나' 하고 생각했다. 예전에 배웠던 알고리즘에서의 조합 문제를 고민해보니 조합은 재귀로 풀었던 기억이 떠올랐다. 이전에 알고리즘을 처음 시작했을때는 이런 문제를 보면 보통 for문을 두번 반복하며 i, j 를 타는동안 검사하여 합을 구했을텐데... 재귀 이론을 알아두면 알고리즘에서는 굉장히 유용한 것 같다.
아이템 뽑아 selected 배열에 넣어준다. 그런 후 바로 재귀로 다시 한번 함수를 타는데 그때 전달하는 함수의 인자가 중요하다. + 1 한 count와, numbers 배열, 방금 selected에 넣었던 배열의 index를 +1 해서 전달해준다. index에 +1 을 해줘야 같은 인덱스의 아이템을 넣지 않고 다음 인덱스의 아이템을 넣을 수 있다.
나는 재귀의 기저조건(빠져나올 조건) 을 count 가 2일 경우로 만들어 두었다. 2개만 뽑는댔으니 count가 2이면 selected 배열에 넣어놓았던 아이템들을 모두 더해서 다시 result 배열에 넣어둔다.

const COUNT = 2
const selected = []
const result = []

function recursive(count, numbers, index) {
    if (count === COUNT) {
        return result.push(selected.reduce((prev, current) => prev + current))
    }
    for (let i = index; i < numbers.length; i++) {
        selected.push(numbers[i])
        recursive(count + 1, numbers, i + 1)
        selected.pop()
    }
}

function solution(numbers) {
    recursive(0, numbers, 0)
    return [...new Set(result)].sort((a, b) => a - b)
}

문제 설명

게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다. board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다. 0은 빈 칸을 나타냅니다. 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다. moves 배열의 크기는 1 이상 1,000 이하입니다. moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력 예

입출력 예에 대한 설명 입출력 예 #1

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개 입니다.

Solution

먼저 시간복잡도를 생각해봤다.
2차원 배열이 최대 5x5 ~ 30x30 까지 밖에 안되고 moves 배열은 최대 1,000 이하라고 하여 그렇게 많은 반복이 필요하지 않을 수 있겠다고 생각했다.
그리고 중요한점이 2차원 배열에서 모든 배열을 탐색해보는것이 아닌, moves에서 나오는 크레인 위치의 배열만 탐색하면 최대 30 번까지 밖에 안해봐도 문제없이 답을 도출해낼 수 있다. board[i][crainPos] 이런식으로 탐색하여, 변동되는 i의 위치로 인형이 몇층에 있는지만 알아내고, crainPos는 항상 moves에서 나온 값으로 고정되어 탐색 되도록 했다.

function solution(board, moves) {
    const basket = []
    let result = 0

    for (let i = 0; i < moves.length; i++) {
        const crainPos = moves[i] - 1

        for (let j = 0; j < board.length; j++) {
            const doll = board[j][crainPos]
            if (doll !== 0) {
                if (basket[basket.length-1] === doll) {
                    basket.pop()
                    result += 2
                } else {
                    basket.push(doll)
                }
                board[j][crainPos] = 0
                break
            }
        }
    }
    return result
}

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

입출력 예 설명

예제 #1 leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2 vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3 mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

Solution

처음에는 participant 의 아이템 하나 하나씩이 completion 배열에 item으로 있는지 검사 해볼까 생각했다.
그러나 이 방법은 최대 participant, completion 의 곱인 100,000 명 X 99,999 명 의 시간복잡도를 가질 수 있어서 오래 걸린다.
Object 를 만들어 participant, completion 배열을 각각 따로 따로 for 문을 돌아보면 어떨까 생각해봤다.
초기 빈 Object 를 만들어 participant 의 이름대로 Object의 키를 만들고 value로 false 를 넣어줬다. completion 을 for 문을 타면서 Object 의 있는 key들의 value를 하나씩 true 로 바꿔 대입해주기 위해서다. (true 로 바뀐 key 들은 완주를 했다는 말)
그러나 또 이 방법은 동명이인이 나왔을 때 문제가 된다. 앞에서 이미 true로 바꿔준 key들로 인해 완주하지 못한 선수가 제대로 리턴이 안되는 문제가...
그래서 결론은, false/true 대신 숫자를 넣어주는 방법을 생각했다.
participant 배열의 참가자들은 Object에서 value 1을 갖는 key 를 가져 Object에 들어가고 동명이인이라면 2가 된다.
마지막에 completion 배열을 돌며 숫자들을 -1 해주는데 value가 1인 key는 완주하지 못한 선수로 보고 해당 아이템을 반환한다.

function solution(participant, completion) {
    const completed = {}

    participant.forEach(key => {
        if (completed.hasOwnProperty(key)) {
            return completed[key] += 1
        }

        return completed[key] = 1
    })

    completion.forEach(key => {
        completed[key] -= 1
    })

    const result = Object.keys(completed).filter(key => completed[key] === 1)
    return result.toString()
}

1.freeCodeCamp

Star : 319K Github 에서 Javascript topic 을 선택하여 정렬해보면 제일 위에 나오는 오픈소스 레포지토리이다. freeCodeCamp 는 대화 형 학습 웹 플랫폼 으로써 온라인 커뮤니티 포럼, 대화방, 온라인 간행물 및 누구나 웹 개발을 학습하고 경험해볼 수 있도록 하는 비영리 조직이라고 한다. 위 사진처럼 웹 개발과 관련된 다양한 주제가 구성된 포럼 페이지도 볼 수 있고, 들어가보면 약간 Stackoverflow? 처럼 개발이나 학습하는데 겪은 이슈나 에러들을 올리며 도움을 받는듯 했다. 그 외에도 다양한 자료를 통해 학습하는데 도움을 받을 수 있는 웹 플랫폼 같다. 이러한 웹 플랫폼의 Github 레포지토리가 1위를 차지하고 있다!

2.Vue

Star : 179K 이제는 개발자라면 누구나 들었을 만한 Vue 프레임워크가 두번째에 위치해 있다. Vue 3 버전이 출시되어

• Teleport
• 템플릿 표현식 관련 추가 문법
• Suspense
• Reactivity 주입 API
• Composition API 등 크게 바뀌었다고 하는데 나중에 기회가 되면 Vue 를 활용해 웹 개발도 한번 해보고 싶다.

3.React

Star : 163K Vue, angular 와 더불어 웹 개발 프레임워크(라이브러리) 의 3대장 중 하나인 React 가 star 수 179K 를 기록하면서 세번째로 위치해 있다. React 는 현재 17.0 버전까지 릴리즈가 되어 있다. React 17 버전에서는 새롭게 사용할 수 있는 API 를 추가하지 않고, 추후 사용자들의 버전 관리를 용이하게 하기 위해서 내부 동작을 바꾸는데 초점을 두었다고 한다. 그것이 무엇이냐면... 앞으로 새로운 버전의 React가 릴리즈 될 때마다 리액트 팀은 React 프로젝트를 진행할 때 deprecated 된 API 를 사용할 수 있는것처럼 2가지 선택지를 제공하는 것이 좋지 못하다고 판단한 모양이다. 그래서 이번 17을 통해 점진적인 React 업그레이드를 가능하게 한다고 공식문서에 설명해주고 있다. 한번 공식문서 React v17 를 살펴보면 좋을 것 같다.

4.Bootstrap

Star : 148K 네번째는 Bootstrap 이다. 웹 개발을 처음 시작했을 때 Bootstrap 을 활용해서 반응형 개발을 많이 하곤 했는데... 요즘은 더 다양한 style 관련 프레임워크나 라이브러리들이 많아서 Bootstrap을 사용해본지는 오래 된것 같다. 그때는 2버전 or 3버전을 썼던것 같은데... 오랜만에 공식 홈페이지에 들어가보니 최근 v5.0 까지 릴리즈가 되어 있는것 같다. 그래도 가장 유명한 반응형 웹 개발 오픈소스인 만큼 여전히 많은 사람들이 사용중인 것 같다.

5.You-Dont-Know-JS

Star : 133K You-Dont-Know-JS 가 나는 책만 있는줄 알았는데, Github 에 오픈소스 레포지토리로 마련되어 있는줄은 이번에 처음 알게 되었다. 그만큼 Github 에는 단지 프로젝트가 아닌, 다양한 주제의 오픈된 소스들이 많은 것 같다.
issue 항목들을 봐보니 책 내용들에 대한 피드백과 오타, 잘못된 표현, 애매한 표현 정정 요청 등 책 출판에 다양하게 기여할 수 있는 형태로 마련되어 있는 오픈소스 같다.
꼭 라이브러리나 프레임워크가 아닌, 이런 책이나, 가이드 문서 등 다양하게 오픈소스에 기여해보는 방법도 정말 좋은 경험이 될 것 같다.

6.Javascript

Star : 104K airbnb 에서 관리하는 Javascript 레포지토리도 있다. 여기서는 Javascript 를 사용하는데 도움이 되는 다양한 style guide를 알려주고 있다. React 에서 Javascript 를 사용하는데 좋은 style guide, Css & sass 를 사용하는데 좋은 style guide, Javascript 의 아주 기초적인 기본 문법을 사용하는데도 따르면 좋은 guide 등이 보기 쉽게 contents 별로 정리되어 있다. 처음에 Javascript 를 책으로 접하면서 배워 이런 가이드를 지키려 해보진 못했는데, 이 Github 오픈소스를 다양하게 참고해보며 개발 가이드를 실무에 적용해가며 개발해보면 참 좋을 것 같다.

example

4.1 Use the literal syntax for array creation. eslint: no-array-constructor

// bad
const items = new Array();

// good
const items = [];

4.2 Use Array#push instead of direct assignment to add items to an array.

const someStack = [];

// bad
someStack[someStack.length] = 'abracadabra';

// good
someStack.push('abracadabra');

4.3 Use array spreads ... to copy arrays.

// bad
const len = items.length;
const itemsCopy = [];
let i;

for (i = 0; i < len; i += 1) {
  itemsCopy[i] = items[i];
}

// good
const itemsCopy = [...items];

4.4 To convert an iterable object to an array, use spreads ... instead of Array.from.

const foo = document.querySelectorAll('.foo');

// good
const nodes = Array.from(foo);

// best
const nodes = [...foo];

7. Javascript-algorithms

Star : 94K Javascript 기반으로 많이 알려진 알고리즘 및 자료구조가 예제를 담고 있는 저장소이다. 연결리스트, 이중 연결 리스트, 큐, 스택 트리 등 코딩테스트 대비나 자료구조의 학습이 Javascript 언어 기반으로 필요하다면 참고해볼 만한 좋은 저장소이다. Star 수가 많고 유명한 만큼, Javascript 기반의 코딩테스트들이 많이 늘고 있는 만큼, 이 저장소의 있는 코드를 따라 작성해보고 공부해보면 Javascript 를 활용한 코딩 테스트는 문제없이 준비해볼 수 있지 않을까 생각한다.(얼마전에도 프로그래머스에서 진행한 카카오 커머스 채용 코딩테스트에서도 순수 Javascript 만 사용할 수 있었던...😂)

8.Electron

Star : 89K 일렉트론이 89K 의 star 를 기록하여 8위를 하고 있다. 일렉트론은 얘기는 많이 들어봤지만 실제 사용해서 개발해 본 경험은 없다. 간단히 본 바로는... Javascript, HTML, CSS 를 이용해서 데스크탑 앱을 만들 수 있는 크로스 플랫폼 프레임워크이다. 데스크탑 앱을 만들기 위해서는 다른 언어를 배워야 하나... 라는 고민은 이제 필요 없고 웹 개발자라면! 이제 Javascript 만으로 데스크탑 앱을 만들 수 있는 것 이다.
Electron은 Chromium과 Node.js 를 사용해서 Javascript, HTML, CSS 를 윈도우 또는 Mac, 리눅스에 까지 직접 설치할 수 있는 애플리케이션을 만들 수 있도록 도와준다. 추후 실무에서 데스크탑 앱 개발을 위한 니즈가 필요하다면 사용해볼만한 아주 좋은 프레임워크 인것 같다.

9.Axios

Star : 81.2K 아홉번째로 Axios 이다. Axios도 처음 웹 개발을 접했을때 fetch 와 더불어 자주 사용하던 Http 비동기 통신 라이브러리이다. Promise API 를 지원하고 Node.js 환경에서 잘 사용할 수 있는 라이브러리이기도 해서, 웹 개발을 할때 손쉽게 사용할 수 있었던 것 같다.
현재는 0.21.1 버전까지 릴리즈가 되어 있다.

10.Node

Star : 76.4K 이제는 웹 개발과 떼놓을 수 없는 Node.js 가 10번째에 위치해 있다.

번외 Deno

Chrome extension 개발 시 chrome.storage 를 사용하여 사용자 데이터에 대한 변경사항을 저장, 검색 및 추적할 수 있다.

Overview

chrome storage 는 아래처럼 조금 다른점을 제외하고는 localStrage API 와 거의 동일한 기능을 제공

• 사용자 데이터는 storage.sync 를 사용하여 Chrome 과 자동으로 동기화 가능하다.
• 데이터는 객체로 저장할 수 있다. (localStorage API 는 데이터를 문자열로 저장한다.)
• 읽기 및 쓰기 작업을 비동기로 처리하여 빠르다.
• extension 콘텐츠 스크립트는 background page 없이도 사용자 데이터에 직접 접근할 수 있다.
• 시크릿 모드 incognito 사용중에도 user 의 extension settings 는 유지될 수 있다.
• 관리자가 'storage.managed' 로 설정한 데이터도 읽어올 수 있다.

Manifest

무튼..! storage 사용을 위해서 manifest 설정은 아래와 같다.

{
  "name": "My extension",
  ...
  "permissions": [
    "storage"
  ],
  ...
}

permissions 에 "storage" 를 추가!

Usage

storage.sync 를 사용해서 아래와 같이 사용할 수 있다.

chrome.storage.sync.set({key: value}, function() {
  console.log('Value is set to ' + value);
});

chrome.storage.sync.get(['key'], function(result) {
  console.log('Value currently is ' + result.key);
});

storage.local 를 사용해서는 아래와 같이 사용할 수 있다.

chrome.storage.local.set({key: value}, function() {
  console.log('Value is set to ' + value);
});

chrome.storage.local.get(['key'], function(result) {
  console.log('Value currently is ' + result.key);
});

그럼 여기서! sync 와 local 두가지로 set 과 get 을 사용할 수 있는데 뭐가 다를까?! Chrome 이 오프라인 상태일 때 Chrome 은 데이터를 로컬에 저장한다. 다음에 브라우저가 온라인 상태가 되면 Chrome은 데이터를 동기화 한다.
사용자가 동기화를 비활성화 하더라도 저장, 동기화가 계속 작동한다. 이 경우 storage.local과 동일하게 작동한다.
local 은 기본적으로 최대 5MB 까지 저장 가능한데 manifest 파일의 'unlimitedStorage' 를 permission 에 추가해주면 용량 제한 없이 저장이 가능하다. 반면 sync 는

• 전체 용량제한 : 100KB
• 항목당 용량제한 : 8KB
• 항목 수 제한 : 최대 512개
• 1시간 당 set, remove, clear 사용 제한 : 1800회
• 1분 당 set, remove, clear 사용 제한 : 120회

와 같은 제약사항이 있다. 비교적 storage.local 보다 빡빡한 느낌...😭

Warning!! chrome storage 에도 localStorage와 마찬가지로 유저 정보나, 기밀 정보를 저장해서는 안된다. (개발자라면 누구나 다 알겠죠..? 그쵸...?😏)

Examples

아래처럼 데이터 변경 내용을 추적하려는 경우 변경 시 이벤트리스너를 추가할 수 있다. 스토리지에 변화가 있을 때마다 해당 이벤트가 발생하는 것 이다.

chrome.storage.onChanged.addListener(function(changes, namespace) {
  for (var key in changes) {
    var storageChange = changes[key];
    console.log('Storage key "%s" in namespace "%s" changed. ' +
                'Old value was "%s", new value is "%s".',
                key,
                namespace,
                storageChange.oldValue,
                storageChange.newValue);
  }
});

이외에 storage 관련 메소드들은 StorageArea 에서 확인할 수 있다. (remove 도 있다..!)

문제

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다.

출력

첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다.

예제 입력1

5 5
1 3
1 4
4 5
4 3
3 2

예제 출력1

3

문제 풀이

from collections import deque

def bfs(v):
    count = 0
    q = deque([[v, count]])
    while q:
        value = q.popleft()
        v = value[0]
        count = value[1]
        if not visited[v]:
            visited[v] = True
            countList[v] += count
            count += 1
            for e in adj[v]:
                q.append([e, count])

n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
countList = [0] * (n + 1)
for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

for i in range(1, n + 1):
    visited = [False] * (n + 1)
    bfs(i)
print(countList.index(min(countList[1:]))) 

문제가 좀 길어 이해하기 어려울 수 있지만 간단히 생각해보면 자기 자신 정점을 제외한 모든 정점을 탐색하는데 거치게 된 count 수를 다 더해보는것과 마찬가지이다. BFS를 활용해 풀었는데 q에 정점과 count를 같이 넣어주어 countList의 해당 정점인덱스에 값을 누적시켜주면 모든 정점을 탐색하는데 거친 값이 나올 수 있다.

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

풀이

from collections import deque

def bfs(v, visited, adj):
    count = 0
    q = deque([[v, count]])
    while q:
        value = q.popleft()
        v = value[0]
        count = value[1]
        if visited[v] == -1:
            visited[v] = count
            count += 1
            for e in adj[v]:
                q.append([e, count])

def solution(n, edge):
    answer = 0
    visited = [-1] * (n + 1)
    adj = [[] for _ in range(n + 1)]
    for e in edge:
        x = e[0]
        y = e[1]
        adj[x].append(y)
        adj[y].append(x)
    bfs(1, visited, adj)
    for value in visited:
        if value == max(visited):
            answer += 1
    return answer

BFS를 이용해 풀었다. 인접리스트를 이용해서 노드가 각각 누구와 연결되어 있는지 정의해준다. 그리고 1부터 BFS로 탐색하며 노드 방문에 몇번을 거쳐 왔는지 count를 q에 정점과 같이 넣어줌으로써 반복했고 visited라는 리스트에 각 인덱스(노드)에 count를 대입 해줌으로써 방문하기까지 몇번 거쳐왔는지 계산해주는 방식으로 풀었다.

         7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력1

30

문제 풀이

n = int(input())
dp = []
for i in range(n):
    dp.append(list(map(int, input().split())))

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

DP를 활용 해 풀었다. dp 배열의 현재 위치의 저장될 값은 현재 위치의 값 + 왼쪽 위 대각선의 dp값과 오른쪽 위 대각선의 dp값 중 최댓값을 더 해주면 된다. 단, 위치가 제일 첫번째이거나 마지막일 경우 왼쪽위 대각선이나, 오른쪽 위 대각선의 값들이 없으므로 조건 처리 해주어야 한다.

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력1

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

예제 출력1

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

문제 풀이

from itertools import combinations

while True:
    k, *s = list(map(int, input().split()))
    if k == 0:
        break
    combi = list(combinations(s, 6))
    for combiList in combi:
        for value in list(combiList):
            print(value, end=' ')
        print()
    print()

처음에는 BFS로 풀어야되나 싶어 목표의 숫자까지 탐색하는 방법이 몇개가 있는지의 방법으로 풀어보려고 했다. 그런데 복잡하게 생각할 것 없이 기본 조합으로 풀면 쉽게 해결 가능하다. 한가지 새로운 *을 활용한 python 문법을 알게 되었다. first, *rest = [1, 2, 3, 4, 5] 로 작성하면 first => 1 가 되고 rest에 [2, 3, 4, 5]가 들어갈 수 있게 된다.

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

예제 입력1

2
5
50 10 100 20 40
30 50 70 10 60
7
10 30 10 50 100 20 40
20 40 30 50 60 20 80

예제 출력1

260
290

문제 풀이

tc = int(input())
for _ in range(tc):
    n = int(input())
    dp = []
    for _ in range(2):
        dp.append(list(map(int, input().split())))
    dp[0][1] += dp[1][0]
    dp[1][1] += dp[0][0]

    for i in range(2, n):
        dp[0][i] += max(dp[1][i-1], dp[1][i-2])
        dp[1][i] += max(dp[0][i-1], dp[0][i-2])
    print(max(dp[0][n-1], dp[1][n-1]))

Dynamic Programing 방법을 이용한 문제이다. 문제를 보면 스티커 하나를 선택하면 위,아래,왼쪽,오른쪽으로 인접해있는 스티커는 또 뗄 수 없다는 조건이 있다. 그러므로 현재 스티커를 선택한 값의 최댓값은 왼쪽으로 대각선 아래(혹은 왼쪽으로 대각선 위)의 스티커를 선택했을 때의 최댓값, 또는 그 바로 왼쪽의 스티커를 선택했을때의 최댓값이다. 그래서 이 두 값을 다시 최댓값을 계산한 뒤 현재 스티커의 값을 더해주면 현재 위치에서의 스티커 최댓값이 나온다.

문제

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

입력

사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

예제 입력1

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

예제 출력1

3

문제 풀이

from collections import deque

def bfs(v, target):
    count = 0
    q = deque([[v, count]])
    while q:
        value = q.popleft()
        v = value[0]
        count = value[1]
        if v == target:
            return count

        if not visited[v]:
            count += 1
            visited[v] = True
            for e in adj[v]:
                if not visited[e]:
                    q.append([e, count])
    return -1

n = int(input())
q1, q2 = map(int, input().split())
m = int(input())
adj = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

print(bfs(q1, q2))

처음에는 촌수 계산을 트리 형식으로 생각하여 어렵게 접근했지만 그럴 필요 없었던 문제이다. 형식만 다를 뿐, 시작 지점부터 목표 지점까지 가는데 몇번을 거쳐서 가야하는지의 방향으로 접근하면 쉽게 풀 수 있다. 따라서 q에 정점 숫자와 count를 같이 넣어주어 풀이한다.

문제

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

입력

첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

출력

첫째 줄에 좋은 단어의 수를 출력한다.

예제 입력 1

3
ABAB
AABB
ABBA

예제 출력 1

2

풀이

def goodString(string):
    if len(string) % 2 != 0:
        return False
    else:
        stack = [string[0]]
        for i in range(1, len(string)):
            if len(stack) == 0:
                stack.append(string[i])
                continue
            if stack[-1] == string[i]:
                stack.pop()
            else:
                stack.append(string[i])
        if len(stack) == 0:
            return True
        else:
            return False

count = 0
for _ in range(int(input())):
    string = input()
    if goodString(string):
        count += 1
print(count)

스택을 이용해서 풀었다. 먼저 스택에 문자열의 첫번째 문자를 넣고 시작한다. 문자열 끝까지 반복문을 타며 문자와 스택에 있는 문자를 비교한 후 같으면 스택에서 pop하고 같지 않으면 push하는 원리로 코드를 작성했다. 반복문을 다 마치고 스택에 문자가 남아있으면 맞는 짝의 문자가 없는것이니 문제에서 말하는 '좋은단어' 가 아닌것으로 풀었다. 한가지 유의해야 할 점은 계속 문자의 쌍이 맞아 pop이 되어 스택이 비어있는데 비어있는 스택과 문자를 비교하려고 하면 index 에러가 뜨기 때문에 그때는 비교하지 않고 바로 스택에 넣어주고 continue를 통해 다음 반복으로 탈 수 있게 했다.

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 abcdcba이면 7을 return하고 abacde이면 3을 return합니다.

제한사항

문자열 s의 길이 : 2,500 이하의 자연수 문자열 s는 알파벳 소문자로만 구성

입출력 예

입출력 예 설명

입출력 예 #1 4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2 2번째자리 'b'를 기준으로 aba가 팰린드롬이 되므로 3을 return합니다.

풀이

def palindrome(string):
    if len(string) <= 1:
        return True

    if string[0] == string[-1]:
        return palindrome(string[1:-1])
    else:
        return False

def solution(s):
    for cut in range(len(s), 0, -1):
        for start in range(0, len(s)):
            cutStr = s[start:start+cut]
            # 자른 string 전달
            if palindrome(cutStr) == True:
                return len(cutStr)

            if start+cut >= len(s):
                break

재귀와 리스트의 slice를 이용해서 풀었다. 먼저 테스트 케이스로 주어진 문자열 길이부터 1씩 감소하며 문자열 길이가 1일때까지 반복문을 돈다. 문자열 길이부터 먼저 도는 이유는 가장 긴 팰린드롬을 찾는것이기 때문이다. 그리고 잘라낼 길이를 기준으로 string을 적절하게 잘라 palindrome 함수에 파라미터로 전달하며 호출해줬다. palindrome 함수는 재귀로 구성했다. 문자열의 제일 앞부분과 제일 뒷부분을 비교하고 같으면 그 다음의 앞, 뒤 를 다시 파라미터로 전달하며 palindrome을 호출해준다. 팰린드롬이면 문자열 길이가 1일때까지 호출할 것이며 그게 곧 팰린드롬인것이다. 한번이라도 앞, 뒤 문자열이 달랐으면 False를 리턴해준다.

보통 상태관리를 할 때 useState를 사용했었는데, useReducer를 통해서도 상태관리를 할 수 있고 상태 업데이트 로직을 컴포넌트에서 분리시킬 수 있다. 이렇게 함으로써 나중에 context API나 Redux 사용 시 업데이트 로직을 전달해줄 수 있을것 같다.

import React, { useReducer } from 'react';

function reducer(state, action) {
  switch (action.type) {
    case 'INCREMENT':
      return state + 1;
    case 'DECREMENT':
      return state - 1;
    default:
      return state;
  }
}

function Counter() {
  const [number, dispatch] = useReducer(reducer, 0);

  const onIncrease = () => {
    dispatch({ type: 'INCREMENT' });
  };

  const onDecrease = () => {
    dispatch({ type: 'DECREMENT' });
  };

  return (
    <div>
      <h1>{number}</h1>
      <button onClick={onIncrease}>+1</button>
      <button onClick={onDecrease}>-1</button>
    </div>
  );
}

export default Counter;

간단히 Counter 컴포넌트를 구현해봤다. useReducer의 첫번째 인자로 따로 로직을 구현한 reducer를 전달해주고, 두번째 인자로 initial state값을 전달해준다. initial state에사 class형 컴포넌트에서 state = {} 로 정의했던 것 처럼 전달해주면 될 것 같다.

dispatch({ type: 'CHANGE_INPUT', name, value });

만약 위처럼 작성시에 전달한 name, value 값들은 reducer 함수 내에서 action.name, action.value로 받을 수 있다.

function reducer(state, action) {
  switch (action.type) {
    case 'CHANGE_INPUT':
      return {
        ...state,
        inputs: {
          ...state.inputs,
          [action.name]: action.value
        }
      };
    default:
      return state;
  }
}

그런데 무조건 useReducer를 통해 값을 관리하는것이 좋은것만은 아니다. 단일값, 단순한 숫자 등이라면 useState로 관리하는게 낫겠지만 컴포넌트 구조가 복잡해지고 관리해야 할 값도 여러개라면 useReducer로 관리하는것이 더 편할 것 이다.

useContext

useContext 훅으로 context API 를 사용해 전역적으로 사용할 수 있는 값을 관리할 수 있다.

const MyContext = createContext("defaultValue");

위 처럼 context를 생성 후

const text = useContext(MyContext);

방식으로 만들어둔 context를 가져올 수 있다. context를 사용하고자 할 컴포넌트에 MyContext.Provider를 안씌우면 createContext시 전달한 디폴트 값이 넘어가지만, <MyContext.Provider value={"Hello"} /> 처럼 작성하면 컴포넌트에 value를 전달하여 컴포넌트 내에서 사용할 수 있다. 부모, 자식 컴포넌트간에 관계가 필요 없이 바로 전달해 줄 수 있는것이다.

문제

알고리즘 유치원 선생님인 영희는 간식시간이 되자 아이들에게 사탕을 나누어 주려고 하였다. 하지만 욕심 많고 제멋대로인 유치원 아이들은 차례대로 받으라는 선생님의 말을 무시한 채 마구잡이로 사탕을 집어 갔고 많은 사탕을 집어 간 아이가 있는가 하면 사탕을 거의 차지하지 못하고 우는 아이도 있었다.

말로 타일러도 아이들이 말을 듣지 않자 영희는 한 가지 놀이를 제안했다. 일단 모든 아이들이 원으로 둘러 앉는다. 그리고 모든 아이들은 동시에 자기가 가지고 있는 사탕의 절반을 오른쪽 아이에게 준다. 만약 이 결과 홀수개의 사탕을 가지게 된 아이가 있을 경우 선생님이 한 개를 보충해 짝수로 만들어 주기로 했다. 흥미로워 보이는 이 놀이에 아이 들은 참여 했고 이 과정을 몇 번 거치자 자연스럽게 모든 아이들이 같은 수의 사탕을 가지게 되어 소란은 종료되었다.

자기가 가진 사탕의 반을 옆에 오른쪽에 앉은 아이에게 주는 과정과 선생님이 사탕을 보충해 주는 과정을 묶어서 1 순환이라고 할 때 몇 번의 순환을 거치면 모든 아이들이 같은 수의 사탕을 가지게 되는지 계산 해보자. 단, 처음부터 홀수개의 사탕을 가지고 있으면 선생님이 짝수로 보충을 먼저 해주며 이 경우 순환수에 들어가지 않는다. 선생님은 충분한 수의 사탕을 갖고 있다고 가정하자.

입력

입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각각의 테스트 케이스의 첫 줄에는 아이의 인원 N (1 ≤ N ≤ 10)이 주어지고 그 다음 줄에는 각 아이들이 초기에 가지고 있는 사탕의 개수 Ci ( 1 ≤ i ≤ N, 1 ≤ Ci ≤ 30)가 주어진다. 분배 시 C1의 오른쪽에는 C2가, C2의 오른쪽에는 C3가…… 같은 식으로 앉게 되며 CN의 오른쪽에는 C1이 앉게 된다.

출력

출력은 표준출력(standard output)을 통하여 출력한다. 각 테스트 케이스에 대하여 모든 아이가 같은 개수의 사탕을 가질 때까지 몇 순환이 걸리는지 출력하시오.

예제 입력 1

4
5
2 4 7 8 9
1
9
6
10 5 13 2 7 8
4
3 4 4 3

예제 입력 2

6
0
4
0

풀이

def plusOneCandy(candy):
    for i in range(len(candy)):
        if candy[i] % 2 != 0:
            candy[i] += 1

def gameStart(candy):
    cycle = 0
    while len(set(candy)) != 1:
        giveAccount = []
        cycle += 1
        for i in range(len(candy)):
            account = candy[i] // 2
            candy[i] -= account
            giveAccount.append(account)

        for j in range(-1, len(candy) - 1):
            candy[j+1] += giveAccount[j]

        plusOneCandy(candy)
    return cycle


for t in range(int(input())):
    n, candy = int(input()), list(map(int, input().split()))

    plusOneCandy(candy)
    print(gameStart(candy))

어려운 문제는 아니지만 함수별로 모듈화 해서 작성하기 좋은 문제이다. 중요한점은 각 아이들마다 옆 친구에게 줘야하는 캔디의 갯수(candy[i] // 2)를 계산 후 따로 다른 배열의 넣어줘야 한다. 계산하면서 바로 옆친구에게 전해주면 원래 갖고있던 캔디의 절반이 아닌 받은 캔디와 누적되어 계산되기 때문이다. 그래서 따로 giveAccount라는 리스트를 만들었다. 그리고, set메소드를 적절히 이용하면 리스트 내에서 중복된 값을 필터하기 좋다.

# ex. 
myList = [5, 5, 5, 5, 5] 
set(myList)
# output => {5}

문제설명

데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

s의 길이는 1 이상 1,000 이하입니다. s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 abcabcabcabc6de 가 됩니다. 문자열을 3개 단위로 자르면 4abcdededededede 가 됩니다. 문자열을 4개 단위로 자르면 abcabcabcabc3dede 가 됩니다. 문자열을 6개 단위로 자를 경우 2abcabc2dedede가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다. 따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다. 이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

풀이

def solution(s):
    length = []
    result = ""

    if len(s) == 1:
        return 1

    for cut in range(1, len(s) // 2 + 1): 
        count = 1
        tempStr = s[:cut] 
        for i in range(cut, len(s), cut):
            if s[i:i+cut] == tempStr:
                count += 1
            else:
                if count == 1:
                    count = ""
                result += str(count) + tempStr
                tempStr = s[i:i+cut]
                count = 1

        if count == 1:
            count = ""
        result += str(count) + tempStr
        length.append(len(result))
        result = ""

    return min(length)

2020 카카오공채에 출제되었던 문제이다. 먼저 문자열을 몇개 단위로 짜를지에 대해 cut을 이용하는 제일 바깥 for문을 1, len(s) // 2 + 1까지 반복했다. 문자열을 꼭 2로 나누어 문자열 길이보다 더 넘어가는 비교는 할 필요 없도록 한다. 그리고 tempStr에 cut만큼 짤라낸 문자열을 대입해 다음 문자열들과 cut 단위로 비교한다.(s[i:i+cut]) 같으면 count를 +1 해주고, 틀리면 count와 비교했던 tempStr을 result값에 넣어주면 된다. 그리고 중요한 것이 마지막에 한번 더 result에 count + tempStr을 넣어줘야 제일 마지막으로 비교했던 문자열이 들어갈 수 있다.

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력1

6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력1

8

예제 입력2

6 4
0 -1 0 0 0 0
-1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1

예제 출력2

-1

예제 입력3

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

예제 출력3

6

예제 입력4

5 5
-1 1 0 0 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 -1 -1 -1 0
0 0 0 0 0

예제 출력4

14

예제 입력5

2 2
1 -1
-1 1

예제 출력5

0

풀이

from collections import deque

def bfs(q, answer):
    count = answer
    while q:
        v = q.popleft()
        nowX = v[0]
        nowY = v[1]
        count = v[2]
        for i in range(4):
            newX = nowX + dx[i]
            newY = nowY + dy[i]
            if (0 <= newX < N) and (0 <= newY < M):
                if tomato[newX][newY] == 0 and tomato[newX][newY] != -1:
                    tomato[newX][newY] = 1
                    q.append([newX, newY, count + 1])
    return count

def check(answer, tomato):
    for i in range(len(tomato)):
        for j in range(len(tomato[i])):
            if tomato[i][j] == 0:
                return -1
    return answer

M, N = map(int, input().split())
tomato = [list(map(int, input().split())) for _ in range(N)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
answer = 0
q = deque([])

for i in range(len(tomato)):
    for j in range(len(tomato[i])):
        if tomato[i][j] == 1:
            q.append([i, j, answer])
answer = bfs(q, answer)

print(check(answer, tomato))

이번에는 bfs를 이용해 풀어봤다. bfs는 dfs와는 다르게 큐를 활용한다. 이 문제에서 키 포인트는 처음에 익은 토마토가 한군데만이 아니라 다른데도 있을시에 동시에 큐에 넣어줌으로써 동시에 서로 다른 다른 토마토가 다른 위치에서 익히도록 해서 answer라는 일수를 계산한다. 그래서 처음 bfs 시작을 q를 전달 해줌으로써 시작했다. 그리고 answer도 같이 전달해주어 토마토 자신이 몇일째에 익혀졌는지 계산하고 q에 +1 해서 넣어줌으로써 해결했다. dx, dy는 아래, 위, 왼쪽, 오른쪽 4방향을 검사하기 위한 값의 배열이다.

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다). 또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다. 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

예제 입력1

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

예제 출력1

5

풀이

import copy
import sys
sys.setrecursionlimit(100000)

def dfs(x, y, tempMap):
    tempMap[x][y] = 0 #방문표시
    for i in range(4):
        newX = x + dx[i]
        newY = y + dy[i]
        if (0 <= newX < N) and (0 <= newY < N):
            if tempMap[newX][newY] != 0:
                dfs(newX, newY, tempMap)

N = int(input())
myMap = [list(map(int, input().split())) for _ in range(N)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
maxList = []
maxValue = 0
answer = 1

for i in range(len(myMap)):
    maxList.append(max(myMap[i]))
maxValue = max(maxList)

# k는 비가 오는 양 1 ~ 배열 내 최대 높이양까지 잠기게 한다.
for k in range(1, maxValue + 1):
    tempMap = copy.deepcopy(myMap)
    for i in range(len(tempMap)):
        for j in range(len(tempMap[i])):
            if tempMap[i][j] <= k:
                tempMap[i][j] = 0 # 0이면 잠김

    count = 0
    for x in range(len(tempMap)):
        for y in range(len(tempMap[x])):
            if tempMap[x][y] != 0: # 안잠긴 영역이거나 방문 안한 영역
                dfs(x, y, tempMap)
                count += 1

    answer = max(answer, count)

print(answer)

dfs를 이용해 풀었다. 먼저 1부터 현재 배열에서 최대값까지만 for문을 돌리기 위해 maxValue를 구해줬다. 그리고나서 이중 for문으로 반복하며 0으로 대입해 물에 잠기게 한다. 그리고 0이 아닌 영역(안잠겼나 방문 안했거나)을 dfs를 타며 count를 계산해준다. answer = max(answer, count)를 통해 이전 answer보다 큰 값이 나오면 answer를 다시 바꿔 대입하도록 풀었다. 한가지 중요한것이 모든 영역의 높이가 같을때는 잠기는 영역이 없기때문에 1로 처리 해야함을 기억해야 한다.

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

풀이

from collections import deque

def bfs(v):
    count = 0
    q = deque([[v, count]])
    while q:
        v = q.popleft()
        e = v[0]
        count = v[1]
        if not visited[e]:
            visited[e] = True
            if e == K:
                return count
            count += 1
            if (e * 2) <= 100000:
                q.append([e * 2, count])
            if (e + 1) <= 100000:
                q.append([e + 1, count])
            if (e - 1) >= 0:
                q.append([e - 1, count])
    return count

N, K = map(int, input().split())
visited = [False] * 100001
print(bfs(N))

bfs를 이용해 풀었다. 처음 시작점 N에서 갈 수 있는 점 N*2, N+1, N-1 세 점에서 또 각점이 갈 수 있는 세 점씩을 계속 탐색해서 K와 같을 때를 찾으면 된다. 단, count를 +1 해주는 위치와 사용하는 방법이 중요한데, count를 방문 안했을시 방문 할 때마다 +1 해주면 다른 탐색도 거쳐와서 N == K 일때도 생길 수 있기 때문에 count 값이 크게 나온다. 때문에 e라는 점이 큐에 몇번째로 들어갔는지 판단후 +1 해주기 위해 count를 q에 같이 넣어줌으로써 해결했다.

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

풀이

import sys
sys.setrecursionlimit(10000)

def dfs(v):
    visited[v] = True
    for e in adj[v]:
        if not visited[e]:
            dfs(e)

N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)
count = 0

for _ in range(M):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

for j in range(1, N + 1):
    if not visited[j]:
        dfs(j)
        count += 1

print(count)

프로그래머스의 '네트워크' 문제와 비슷한 문제이다. dfs와 인접리스트를 이용해 풀었다. 1 -> 2 로 간선이 연결되면 대칭하여 똑같이 연결된것을 표현하기 위해 adj[u].append(v), adj[v].append(u) 처럼 했다. 또 한가지 중요한것이 python은 재귀제한이 걸려있기 때문에 재귀 허용치가 넘어가면 런타임에러를 일으킨다. 때문에 sys.setrecursionlimit(10000) 처럼 작성해야 한다.