본문 바로가기

알고리즘 공부 및 문제 풀이/백준(BOJ)

 (220)
[기출 하] O, X 퀴즈 [문제] 문제를 맞으면 O, 틀리면 X인 결과 문자열이 주어졌을 때, 연속 된 O의 개수가 해당 문제에 주어지는 점수라고 한다. 예를 들어 OXXOOOX는 1+0+0+1+2+3+0=7점이다. OX문제에 대한 결과 값을 출력해라. [코드] int solution(string input){ int total = 0; int num = 1; for(int i=0; i
[기출 하] 깨알나라 신문 기사 [문제] 문자열의 행, 열, 행 확대 크기, 열 확대 크기가 주어질 때 확대 된 문자 배열을 출력하라. 입출력 예시) [코드] vector solution(int r, int c, int zr, int zc, vector words) { vector answer; string s; //행, 열 for(int i=0; i
[c++] 백준 1931 회의실 배정 백준 단계별로 풀어보기[그리디 알고리즘] 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net [풀이] 회의실 배정은 끝나는 시간이 빠른 순으로 배정해주어야 최대 배정이 가능하다. 끝나는 시간이 빠른 순으로 정렬을 해주되, 같다면 시작 시간이 빠른 회의가 앞에 위치하도록 한다. 그 다음 회의의 시작 시간이 현재 회의의 끝나는 시간과 같거나 더 늦어야 하고, 조건을 만족한다면 회의가 끝나는 시간을 변경해준다. 회의실 배정을 새로 해줄 때마다 cnt 값을 증가시켜준다. [코드] #include #include using namespace std; bool ..
[c++] 백준 2606 바이러스 백준 단계별로 풀어보기[DFS와 BFS] 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net [풀이] DFS를 이용. [코드] #include #include #include #include using namespace std; int n, m, cnt = 0; //정점의 개수, 간선의 개수, 시작 정점 int adj[101][101]; bool isVisited[101] = { false, }; queue q; void dfs(int v) {..
[c++] 백준 1260 DFS와 BFS 백준 단계별로 풀어보기 [DFS와 BFS] DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [풀이] DFS는 재귀를 이용해서, BFS는 큐를 이용해서 구현하였다. 무방향 그래프이기 때문에 인접행렬을 이용해서 인접관계를 표현했고, 같은 isVisited 배열을 이용하기 때문에 BFS 탐색 이전에 다시 초기화를 해주는 작업이 필요하다. [코드] #include #include #include #..
[c++] 백준 14425 문자열 집합 백준 단계별로 풀어보기 [문자열 알고리즘 1] 문자열 집합 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net [풀이] 트라이 알고리즘으로 insert와 find 함수를 구현하여 풀 수 있다. 트라이 알고리즘에 대한 공부는 알고리즘 카테고리에서... [코드] #include #include #include using namespace std; class Node { public: Node* childs[26] = {..
[c++] 백준 14725 개미굴 백준 단계별로 풀어보기 [문자열 알고리즘 1] 개미굴 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net [풀이] 트라이 알고리즘 응용 문제이다. 먼저 문자열을 vector를 이용해 저장하고 map를 이용해 트라이 구조를 나타낸다. 같은 층에 이미 똑같은 문자열이 존재한다면(경로가 존재), 그 다음 노드로 이동해서 단어를 삽입한다. 만약 존재하지 않는다면 새로 노드를 할당받아 단어를 저장한다. map은 key를 기준으로 오름차순 자동..
[c++] 백준 13305 주유소 백준 단계별로 풀어보기 [그리디 알고리즘] 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net [풀이] 가격이 가장 작은 주유소의 기름 최소값과 도로 거리를 곱할 수 있도록 비교해가며 min값을 설정한다. [코드] #include #include long long road[100000]; long long price[100000]; int main() { //주유소의 기름 가격과 각 도시를 연결하는 도로 길이를 입력, 최소의 ..

티스토리툴바