난이도 : 골드 5 걸린 시간 : 25분 문제 적록색약 문제 바로가기 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑..

난이도 : 골드 5 걸린 시간 : 1시간 문제 연구소 문제 바로가기 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연..

블록 이동하기 ★★★☆☆ LEVEL 3 문제 블록 이동하기 문제 링크 문제 설명 로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 무지는 0과 1로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 0은 빈칸을 1은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다. 로봇이 움..

여행경로 문제 https://programmers.co.kr/learn/courses/30/lessons/43164 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합..

타겟 넘버 문제 https://programmers.co.kr/learn/courses/30/lessons/43165 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 ..

그래프 탐색 그래프를 탐색하는 기법에는 대표적으로 2가지가 있다. 너비 우선 탐색인 BFS(Breadth-First Search)와 깊이 우선 탐색인 DFS(Depth-First Search)이다. BFS BFS는 큐를 이용하여 구현한다. 설명 트리로 예를 들었지만, 모든 그래프에서 마찬가지로 동작한다. 루트 노드를 queue에 넣는다. queue의 노드를 하나 꺼낸 후, 해당 노드와의 인접 노드를 모두 queue에 넣는다. 위의 방식을 모든 노드가 완료될 때까지 반복한다. stack에 들어간 순서를 보면 다음과 같다. 1=>2=>3=>4=>5=>6=>7=>8 따라서 트리에서 BFS를 실행하여 탐색을 하는 것은 레벨 순회를 하는 것과 같다. DFS DFS는 스택을 이용하여 구현한다. 설명 트리로 예를 들..

재귀호출 재귀함수란 함수 내에서 자기 자신을 다시 호출하는 함수이다. 프로그래밍할 때 반복되는 작업들이 대해서는 반복문을 사용하거나 재귀함수를 이용해서 표현한다. 기저 사례란 더 이상 쪼개지지 않는 가장 작은 작업으로, 이에 도달했을 때는 재귀호출을 멈추고 답을 곧장 반환해야한다. 기저 사례를 정할 때는 모든 사례의 답이 기저 사례를 이용하여 계산될 수 있도록 해야한다. 완전 탐색 (== Brute Force, Exhaustive search) 완전탐색은 컴퓨터의 연산능력을 이용하여 가능한 경우의 수를 모두 나열하면서 답을 찾는 알고리즘이다. 입력의 크기가 작을 때 적절한 알고리즘이며 더 빠른 알고리즘의 기반이 된다. 답을 무조건 찾을 수 있다는 장점이 있지만, 찾는데에 오랜 시간이 걸린다는 단점이 있다..

트리 용도 용어 정리 종류 이진 트리 일반 트리 스레드 이진 트리 구현 배열 표현법 연결리스트 표현법 트리 활용 탐색 집합 표현 허프만 코드 트리 트리란 그래프의 한 종류로 무방향 연결 비순환 그래프(Connected Undirected Acyclic Graph)이다. 루트 노드가 존재하고, 루트 노드를 제외한 모든 노드의 in-degree가 1인 방향그래프라고 말할 수도 있다. 계층적인 구조를 가지며 그래프의 한 종류이므로 비선형 자료구조에 속한다. 용도 계층적인 조직을 표현하기 위해 사용되거나, 컴퓨터의 디렉토리 구조 / 인공지능의 decision tree 등에 이용된다. 또한 자료의 탐색 / 정렬 / DB 구성이나 분자구조식 설계 등에서도 다양하게 이용된다. (결정트리)(이진탐색) 용어 정리 노드 ..