-o-k's story

www.acmicpc.net/problem/2675 2675번: 문자열 반복 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다 www.acmicpc.net Level: Level 1 풀이: 미참고 Language: C++ 프로그램: Visual Studio 2017 문제설명 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다. S에는 QR Code "alphanumeric" 문자만 들어있다. QR Code ..

www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 www.acmicpc.net Level: Level 1 풀이: 미참고 Language: C++ 프로그램: Visual Studio 2017 문제설명 영어 대소문자와 띄어쓰기만으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다. 입력/출력 입력 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문..

www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net Level: Level 1 풀이: 미참고 Language: C++ 프로그램: Visual Studio 2017 문제설명 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다. 통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 ..

www.acmicpc.net/problem/16435 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net Level: Level 1 풀이: 미참고 Language: C++ 프로그램: Visual Studio 2017 문제설명 스네이크버드는 뱀과 새의 모습을 닮은 귀여운 생물체입니다. 스네이크버드의 주요 먹이는 과일이며 과일 하나를 먹으면 길이가 1만큼 늘어납니다. 과일들은 지상으로부터 일정 높이를 두고 떨어져 있으며 i (1 ≤ i ≤ N) 번째 과일의 높이는 h..

www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net Level: Level 2 풀이: 기존 풀이 참고 Language: C++ 프로그램: Visual Studio 2017 문제설명 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상..

www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net Level: Level 1 풀이: 기존 풀이 참고 Language: C++ 프로그램: Visual Studio 2017 문제설명 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져..

그래프 탐색 그래프의 각 정점을 방문하는 것을 탐색이라고 한다. 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것을 말한다. 탐색에서 노드의 방문 순서에 따라 방법이 나누어진다. 두 가지 방법: BFS, DFS 너비 우선 탐색(Breath First Search) , BFS https://www.youtube.com/watch?v=66ZKz-FktXo 정의: 특정한 데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘, 즉 시작점이 있을 때 시작점과 가까운 것 위주로 탐색하겠다는 것 특징 - 큐(=먼저 들어온 것을 먼저 처리, 선입선출)를 사용한다. - 맹목적인 탐색을 하고자 할 때 사용할 수 있는 탐색 기법이다. - 재귀적으로 동작하지 않는다. - 흔히 미로 찾기..

www.acmicpc.net/problem/2401 2401번: 최대 문자열 붙여넣기 어떤 긴 문자열이 주어지고 여러 개의 짧은 문자열들이 주어질때 이때 짧은 문자열을 긴 문자열에 붙여 넣을때 가장 길게 붙여 넣는 경우를 찾아라. 단 이때 짧은 문자열들끼리는 교차 할 수 없 www.acmicpc.net Level: Level 2 풀이: 기존 풀이 참고 Language: C++ 문제설명 어떤 긴 문자열이 주어지고 여러 개의 짧은 문자열들이 주어질 때 이때 짧은 문자열을 긴 문자열에 붙여 넣을 때 가장 길게 붙여 넣는 경우를 찾아라. 단 이때 짧은 문자열들끼리는 교차할 수 없다. (‘aabbc'에 'aab'와 'bbc' 둘 다 붙여 넣는 것은 불가능하다.) 또, 짧은 문자열은 여러 번 사용할 수 있다. 입력..

www.youtube.com/watch?v=PNPIk3hc6ic 그리디(Greedy) 알고리즘 그리디 알고리즘: 당장 눈 앞에 뵈는 최적의 상황을 쫓는 알고리즘, 단순한 형태이다. 장점: 최적의 해에 근사한 값을 빠르게 구할 수 있다. 정렬기법이 함께 이용 그리디 알고리즘이 최적의 해를 보장하는 경우도 있지만 그렇지 않은 경우도 많다. 그럴 경우에는 다이나믹 프로그래밍 등의 기타 알고리즘 기법을 적용하여 해결해야한다. 문제설명 & 풀이 문제: 1260원을 거슬러주어야 할 때 가장 적은 숫자의 화폐를 이용해 거슬러주는 경우에 대해서 찾아본다. 풀이 가장 큰 동전 먼저 계산을 해준다. 그리디 알고리즘이란? 큰 경우부터 찾는 알고리즘과 같이 간단하게 탐욕적으로(한가지 경우만 보고 쫓는다) 문제를 해결하는 기법..

문제 설명 바로 앞 번호의 학생이나 바로 뒷 번호의 학생에게만 체육복을 빌려줄 수 있다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육 수업을 들을 수 있는 학생의 최댓값을 return 해야 한다. Error Code #include #include #include using namespace std; int solution(int n, vector lost, vector reserve) { if (n30) return 0; int answer = n-lost.size(); for(int i=0; i