문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 접근 대각선상에 집이 있는 경우는 연결된 것이 아니므로, 상하좌우로 탐색하는 dfs다. 코드 n = int(input()) grid = [list(map(int, list(input()))) for _ in range(n)] ..
문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 접근 그림을 보면 위와 같은 규칙을 찾을 수 있다. 피보나치 수를 구해주면 된다. 예전에 피보나치 수를 구하는 문제에서 정직하게 재귀를 사용했다가 시간초과가 나오고, 배열에 저장해도 시간초과가 나왔던 기억이 있다. 그래서 변수만 사용해서 답을 구했다. 코드 n = int(input()) if n < 3: print(n%10007) else: a, b = 1, 2 for _ in range(n-2): a, b = b, a+b print(b%10007)
문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. 주의할 점 ..
링크 programmers.co.kr/learn/courses/30/lessons/17684?language=python3 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 문제 설명 신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다. 어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현하..
1️⃣ 이상 탐지(anomaly detection) 개념 '이상'은 '정상'의 반대 개념이며 개념 정의를 위해서는 '정상'에 대한 개념부터 정의해야 한다. '정상'에 대한 개념은 각 분야 및 문제마다 다르게 정의될 수 있기 때문에 '이상'에 대한 개념 역시 다르게 정의될 수 있다. '이상'은 자료에서 예상과는 다른 패턴을 보이는 개체 또는 자료를 뜻한다. '예상 탐지' 기법은 자료에서 예상과는 다른, 예상 가능하거나 '정상'으로 정의된 것과 다른 패턴을 식별하는 기법이다. 입력 자료는 자료 개체(instance)들의 집합이고, 각 객체는 하나 이상의 속성 또는 변수(attribute)들로 표현된다. 이상 탐지 기법은 관측 값의 집합에서 주변의 다른 자료 개체로부터 현저하게 벗어나는 여러 관측 값을 식별한..
✅ 빅데이터의 정의 빅데이터를 이론으로 공부하면 주로 3V(Volume, Velocity, Variety)라 정의한다. 이는 각각 규모의 증가, 다양성, 처리 속도를 뜻한다. - 규모의 증가(Volume): 기존 데이터 수집, 관리, 처리 소프트웨어의 한계를 넘어선다. - 처리 속도(Velocity): 데이터의 양과 내용이 끊임없이 변화(실시간성 정보가 증가)함에 따라 대규모 데이터의 빠른 처리, 분석이 요구된다. - 다양성(Variety): 비정형 데이터의 종류가 다양해진다. 여기서 규모의 증가에 집중해서, '기존 소프트웨어의 한계를 넘어섰다'의 기존 소프트웨어는 MySQL, Orcale과 같은 관계형데이터베이스를 의마한다. 이러한 소프트웨어는 대부분 분산환경이 아닌 서버 한 대만을 염두에 두고 만들어..
💬 문제 설명 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다. 입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라. 💬 코드 def solution(m, n, board): answer = 0 # 지울거 찾기 def find(board): target = set() for i in range(m-1): for j in range(n-1): if board[i][j] and board[i][j] == board[i][j+1] == board[i+1][j] == board[i+1]..
💬 문제 설명 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. "[닉네임]님이 들어왔습니다." 채팅방에서 누군가 나가면 다음 메시지가 출력된다. "[닉네임]님이 나갔습니다." 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경한다. 닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다. 채팅방에 들어오..
💬 문제 설명 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램의 과거 버전을 모두 담고 있어, 이름 순으로 정렬된 파일 목록은 보기가 불편했다. 파일을 이름 순으로 정렬하면 나중에 만들어진 ver-10.zip이 ver-9.zip보다 먼저 표시되기 때문이다. 버전 번호 외에도 숫자가 포함된 파일 목록은 여러 면에서 관리하기 불편했다. 예컨대 파일 목록이 ["img12.png", "img10.png", "img2.png", "img1.png"]일 경우, 일반적인 정렬은 ["img1.png", "img10.png", "img12.png", "img2.png"] 순이 되지만, 숫자 순으로 ..
링크: programmers.co.kr/learn/courses/30/lessons/17687?language=python3 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr 💬 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0부터 시작해서 차례대로 말한다. 첫 번째 사람은 0, 두 번째 사람은 1, … 열 번째 사람은 9를 말한다. 10 이상의 숫자부터는 ..
코딩테스트를 볼 때 Join을 사용해야 하는 문제가 나와도 Sub-query로 작성하는게 더 편해서 서브쿼리를 작성해왔다. 검색해보니 많은 사람(특히 SQL입문자)들이 서브쿼리가 조인에 비해 작성하기 쉬워 선호한다고 한다. 그런데 작성하기 쉬운건 쉬운거고, 성능이 문제다. 대부분의 경우 조인이 서브쿼리에 비해 성능이 좋다. 가독성: Sub-query>Join 성능: Join>Sub-query 다행히도 MySQL 5.6 버전부터는 서브쿼리가 많이 최적화되었다고 한다. 그러나 최적화가 적용되지 않는 조건들이 다수 존재한다고 하니 웬만하면 조인을 사용하는게 좋다. [조인이 서브쿼리보다 성능이 좋은 이유] In JOINs RDBMS can create an execution plan that is better ..
링크: www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제: 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향..
