우노

들어가기 앞서, 코딩 테스트에서, 문제의 제한 시간은 일반적으로 1~5초 가량이다. 일반적인 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 1초에 실행할 수 있는 연산량은 1억번이다. 따라서, 문제를 풀기 전, 문제의 시간 복잡도를 확인한다면, 얼마나 효율적인 알고리즘을 작성해야하는지 눈치 챌 수 있다. 예를 들어, 주어진 N의 범위가 최대 5,000이며, 주어진 제한 시간이 1초라면, 시간 복잡도가 O(N^3)인 알고리즘의 연산 횟수는 10억을 넘어가며, 10초 이상의 시간이 걸리므로, 사용하기 어렵다. N 의 범위와 시간 복잡도에 따른 연산 횟수 N 의 범위가 1,000 일 경우 O(N) : 1,000 O(NlogN) : 10,000 O(N^2) : 1,000,000 O(N^3) : 1,000,000..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/72410 문제 풀이 예제 코드를 참고해, 각 단계별로 문자열 처리 예제 코드 #include #include #include #include using namespace std; string solution(string new_id) { string answer = ""; // 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. for (auto i=0; i=16){ new_id.erase(15); if (new_id[new_id.size()-1]=='.'){ new_id.erase(new_id.end()-1); } } // 7단계 new_id의 길이가 2자 이하라면, ne..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/92334 문제 풀이 주요 풀이 각 멤버의 index를 Map에 저장 신고된ID와 신고한ID를 Map에 저장 이때, 신고한ID는 중복을 제거하기 위해, Set 형태로 저장 신고 정보 문자열은 stringstream을 사용해 parsing 전체 흐름 신고 정보들을 parsing한 뒤, 신고 정보를 저장하는 Map에 전부 담고, 신고 정보 Map을 탐색하면서, 신고한ID의 개수가 K개 이상이면, 신고한 멤버들의 Count를 증가시키는 방식 예제 코드 #include #include #include #include #include using namespace std; vector solution(vector ..

문제 링크 https://www.acmicpc.net/problem/1744 풀이 최댓값을 유도하기 위해선 양수와 음수는 서로 곱해야한다. 양수 묶음의 경우, 큰 수끼리 곱해야한다. (ex. 5, 4) 음수 묶음의 경우, 절대값이 큰 음수끼리 곱해야한다. (ex. -5, -4) 1 은 어떠한 경우든, 묶어서 곱셈하는 결과값보다, 개별로 덧셈하는 결과값이 더 크다. 0 을 개별로 더하는 것은 무의미하므로, 음수의 개수가 홀수일 경우, 가장 절대값이 작은 음수와 0 을 곱해주는 방식이 최댓값 유도에 좋다. (ex. -1 * 0) 풀이 방법 양수들은 positive 벡터에 저장하고, 음수들은 negative 벡터에 저장한다. 0 의 개수는 개별 변수로 저장하고, 1 은 모두 총 결과값에 더해준다. 이후, po..

문제 링크 https://www.acmicpc.net/problem/13305 풀이 예제 그림 문제는, 현재 도시의 주유 가격이 다음 도시의 주유 가격보다 비싼지, 저렴한지에 따라 나뉘게 됩니다. 현재 주유소보다 다음 주유소가 싸다면, 현재 주유소에서는, 다음 주유소로 이동하는 데에 걸리는 거리만큼만 주유하고, 다음 주유소에서 더 주유하는 것이 이득입니다. 만약, 현재 주유소가 다음 주유소보다 싸다면, 다음 주유소에서 다다음 주유소까지 이동하는 데에 걸리는 거리만큼, 현재 주유소에서 더 주유하는 것이 이득입니다. 즉, 도시를 이동할 때마다 기름을 채워주되, 이전에 등장했던 주유 가격 중 가장 최소의 가격으로 기름을 채울지, 현재 주유소의 가격으로 기름을 채울지만 정하면 됩니다. 주의 사항 첫 번째 도시에..

문제 링크 https://www.acmicpc.net/problem/10162 풀이 초단위의 요리시간이 입력으로 들어왔을 때, 요리 시간이, A 버튼의 시간인 300초보다 크다면, 요리 시간을 300초로 나눈 뒤, 나눠진 몫을 A 버튼 사용 개수로 저장하고, 나머지를 남은 요리시간으로 저장합니다. 남은 요리 시간이, B 버튼의 시간인 60초보다 크다면, 요리 시간을 60초로 나눈 뒤, 나눠진 몫을 B 버튼 사용 개수로 저장하고, 나머지를 남은 요리시간으로 저장합니다. 남은 요리 시간이, C 버튼의 시간인 10초보다 크다면, 요리 시간을 10초로 나눈 뒤, 나눠진 몫을 C 버튼 사용 개수로 저장합니다. 이후에도 요리 시간이 남는다면, -1 을 출력합니다. 코드 #include using namespace ..

문제 링크 https://www.acmicpc.net/problem/1149 풀이 현재 집이 빨간색이라면, 다음 집은 초록색, 파란색이 가능합니다. 현재 집이 초록색이라면, 다음 집은 빨간색, 파란색이 가능합니다. 현재 집이 파란색이라면, 다음 집은 빨간색, 초록색이 가능합니다. 그렇다면 반대로, 현재 집이 빨간색이라면, 이전 집은 초록색, 파란색이 가능합니다. 현재 집이 초록색이라면, 이전 집은 빨간색, 파란색이 가능합니다. 현재 집이 파란색이라면, 이전 집은 빨간색, 초록색이 가능합니다. 따라서, 현재 집의 색을 칠할 때, 이전 집으로 가능한 색들을 확인하고, 이전 집들 중, 누적 비용이 가장 적은 색을 선택한 뒤, 현재 집까지의 비용을 [현재 집의 비용 + 이전 집까지의 최소 누적 비용] 으로 갱신..

문제 링크 https://www.acmicpc.net/problem/9095 풀이 해당 문제는 규칙을 찾는 것이 중요합니다. 따라서, 아래 그림을 통해 규칙을 찾아보겠습니다. 우선, 4 를 만들 수 있는 조합은 7가지로 이루어져있습니다. 1 + 로 시작하는 조합 1 + 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 3 2 + 로 시작하는 조합 2 + 1 + 1 2 + 2 3 + 로 시작하는 조합 3 + 1 즉, 1 + 로 시작하는 조합의 개수는 4 개입니다. 이는, 3 을 만들 수 있는 조합의 개수와 동일합니다. 또한, 2 + 로 시작하는 조합의 개수는 2 개입니다. 이는, 2 를 만들 수 있는 조합의 개수와 동일합니다. 마지막으로, 3 + 로 시작하는 조합의 개수는 1 개입니다. 이는, ..

문제 링크 https://www.acmicpc.net/problem/3055 풀이 문제 목표 고슴도치가 비버 소굴까지 안전하게 갈 수 있는, 최소 시간을 구하는 것입니다. 중요 사항 입력 받는 물의 시작 위치는 여러 곳일 수 있습니다. 물과 고슴도치는 매 분마다, 상하좌우로 비어있는 곳을 찾아 확장됩니다. 다음턴에 물이 채워지는 곳은 고슴도치가 이동할 수 없습니다. 풀이 방법 물을 먼저 확장시킨 뒤, 고슴도치를 이동시켰으며, 지도에서, 물이 확장되는 곳은 ‘*’ 로, 고슴도치가 이동하는 곳은 ‘S’ 로 변경하며 진행했습니다. 첫 번째 예제 입력에 따른 진행 과정 3 3 D.* ... .S. D** .S* SSS D** SS* SSS 두 번째 예제 입력에 따른 진행 과정 3 3 D.* ... ..S D**..

그래프란? 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조를 의미합니다. 그래프 탐색이란? 하나의 정점으로부터 시작하여, 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미합니다. 너비 우선 탐색(BFS, Breadth First Search)이란? 루트 노드 또는 임의의 노드에서 시작하여, 일정 노드와 인접한 노드들을 우선으로 탐색하는 방법입니다. 주로, 어떤 두 노드 사이의 최단 경로를 구할 때 사용되며, 주로, 큐(Queue)라는 자료구조를 사용해 구현됩니다. 너비 우선 탐색 예제 BFS 는, 아래와 같은 간단한 알고리즘에 의해 작동됩니다. 큐에서 하나의 노드를 꺼냅니다. 해당 노드와 연결된 노드들 중, 방문하지 않은 노드들을 큐에 삽입하며, 방문 처리합니다. 반복합니다...