문자열 뒤집기 난이도 ●○○ | 풀이 시간 20분 | 시간 제한 2초 | 메모리 제한 128MB | 기출 핵심 유형 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 ..
곱하기 혹은 더하기 난이도 ●○○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB | 기출 Facebook 인터뷰 각 자리가 숫자(0부터 9)로만 이루어진 문자열을 사용자로부터 입력받아, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 곱하기(x) 혹은 더하기(+) 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, + 보다 x 를 먼저 계산하는 일반적인 방식과 달리 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다. 예를 들어 02984라는 문자열로 만들 수 있는 가장 큰 수는 ((((0 + 2) x 9) x 8) x 4) = 576입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어..
모험가 길드 난이도 ●○○ | 풀이 시간 30분 | 시간 제한 1초 | 메모리 제한 128MB | 기출 핵심 유형 한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했는데, 공포도가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다. 모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다. 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금하다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하시오. 입력 조건 첫째 줄에 모험가의 수 N이 주어진다. (1 ≤ N ≤ ..
그래프 이론(Graph Theory) 그래프 노드(Node)와 노드 사이에 연결된 간선(Edge)의 정보를 가지고 있는 자료구조로 인접 행렬(2차원 배열 사용)과 인접 리스트(리스트 사용)를 이용해서 구현할 수 있다. 서로소 집합(Disjoint Sets) 공통 원소가 없는 두 집합이다. 예를 들어 집합 {1, 2}와 집합 {3, 4}는 서로소 관계이다. 반면에 집합 {1, 2}와 집합 {2, 3}은 2라는 공통 원소가 존재하기 때문에 서로소 관계가 아니다. 서로소 집합 자료구조: 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조로 아래와 같이 두 종료의 연산을 지원한다. 지원하는 연산 때문에 합치기 찾기(Union Find) 자료 구조라고 불리기도 한다. 찾기(Find): 특정한 ..
최단 경로(Shortest Path) 개요 가장 짧은 경로를 찾는 알고리즘으로 '길 찾기' 문제라고도 부른다. 최단 경로 문제는 보통 그래프를 이용하여 표현하는데 각 지점은 그래프에서 '노드(Node)'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 또한 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제된다. 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 알고리즘이 적용된다는 특징이 있어 두 알고리즘의 한 유형으로 볼 수 있다. 컴퓨터공학과 학부에서 사용하는 최단 거리 알고리즘은 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘으로 총 3가지지만 코딩 테스트에 주로 등장하는 알고리즘에서 벨만 ..
다이나믹 프로그래밍 개요 큰 문제를 작게 나누고 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 문제를 해결하는 방향에 따라 두 가지로 나뉘는데 큰 문제를 해결하기 위해 작은 문제를 호출하는 탑다운(하향식, Top-Down)방식과 작은 문제부터 차근차근 답을 도출하는 보텀업(상향식, Bottom-Up)이다. 항상 다이나믹 프로그래밍을 사용할 수는 없으며 다음 조건을 만족할 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 잇다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 피보나치 수열은 위와 같은 조건을 만족하는 대표적인 문제이다. 피보나치 수열은 일반적으로 탑다운 방식으로 구현하면 재귀함수를 보텀업 방식으로 구현할 경우 반복문을 사용한다. 이때 ..
