컴공에서 살아남기

주유소 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다. 예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는..

Enemy AI의 공격 기능을 구현하기 위해 Action Task 클래스를 작성하였다. 💻 CBTTaskNode_Action ExecuteTask 함수에서는 Owner의 Weapon Component를 불러와서 현재 장착중인 무기의 공격을 수행하도록 DoAction 함수를 실행시켜주었다. Enemy가 공격하는 도중에 Task_Action이 성공 또는 실패되어 종료된다면, 다음 Task 노드로 흐름이 바뀌기 때문에 공격하고 나서는 EBTNodeResult를 대기 상태인 InProgress로 반환해준다. 실제로 Task_Action 노드를 끝내는 처리는 Tick 함수에서 진행한다. TickTask 함수에서는 Enemy가 공격을 끝내고 다시 Idle Mode가 되었는지, 현재 공격이 실행중인지를 나타내는 bI..

균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 짝을 이루는 두 괄호가 있을 때,..

[ 띄워쓰기를 포함하여 Enter 칠 때까지 문자열 입력받기 ] cin.getline(변수 주소, 최대 입력 가능 문자수, 종결 문자); ex) cin.getline(str, 100); getline(입력스트림 오브젝트, 문자열을 저장할 string객체, 종결 문자); ex) getline(cin, str); @ 주의사항: cin >> int형 변수; 을 사용하고 나서 바로 getline(cin, str); 을 사용하면 getline에서 문자열을 입력받지 않고 바로 다음 코드로 넘어간다. 이유: 버퍼에 정수 값을 입력한 뒤 누른 엔터('\n')가 그대로 남아있어 getline()에 들어가기 때문 따라서 cin.ignore() 함수를 사용하여 입력 버퍼의 모든 내용을 제거해줘야 getline 함수가 정상적..

[ vector 초기화 ] vector v(n); vector vv(n, vector(m)); [ vector의 멤버함수 ] vector v; - v.assign(5,2); 2의 값으로 5개의 원소 할당 - v.front(); 첫번째 원소를 참조 - v.back(); 마지막 원소를 참조 (++v.back() 하면 마지막 원소의 값을 1 올릴 수 있다) - v.clear(); 모든 원소를 제거, 원소만 제거하고 메모리는 남아있다. - v.pop_back(); 마지막 원소를 제거 - v.insert(2,3); 2번째 위치에 3의 값을 삽입 - v.insert(2,3,4); 2번째 위치에 3개의 4의 값을 삽입 (뒤에 원소가 있다면 뒤로 밀림) [ vector의 최대/최소 값 찾기 ] - int value =..

플로이드 문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거..

📖 플로이드 워셜 알고리즘 다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구하는 알고리즘이다. 그러나, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에는 "플로이드 워셜 알고리즘"을 사용해야 한다. 📌 플로이드-워셜 알고리즘 vs 다익스트라 알고리즘의 차이점 1. 플로이드 워셜 알고리즘은 다익스트라에 비해 소스코드가 매우 짧아 구현이 쉽다. 2. 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야 하기 때문에 2차원 테이블에 최단 거리 정보를 저장한다. (다익스트라 알고리즘은 한 지점에서 다른 지점까지의 최단 거리만을 구하므로 1차원 리스트에 저장하였다) 3. 플로이드 워셜 알고리즘은 DP 알고리즘에 속한다. 만약 노드의 개수가..

평범한 배낭 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100..

🎒배낭문제 (Knapsack Problem) 배낭문제는 조합 최적화 문제의 일종이다. 간략하게 말하자면, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분 집합을 찾는 문제이다. 분할 가능한 배낭 문제 0-1 배낭 문제 배낭 문제는 분할 가능한 배낭 문제와, 0-1 배낭 문제로 나뉘어 진다. 위 그림을 통해 보면, A박스를 열어 12kg의 금괴 중 일부만을 챙겨 갈 수 있는 문제가 '분할 가능한 배낭 문제'이고, 박스를 열지 못해 금괴 일부를 꺼내지 못하고 통째로만 취급하는 문제가 '0-1 배낭 문제'이다. 분할 가능한 배낭 문제는 그리디 알고리즘으로 풀 수 있다. 반면, 0-1..

동전 1 문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 예제 입력 1 3 10 1 2 5 예제 출력 1 10 해당 문제는 DP를 이용하여 경우의 수를 구하는 문제이다. 지금까지 경우의 수를 구하는 문제는 BFS..

영단어 암기는 괴로워 문제 화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다. 자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자. 입력 첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으..

통계학 문제 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. 출력 첫째 줄에는 산술평균을 출력한다. 소수점..