Dolphins의 HelloWorld

문제링크 : https://www.acmicpc.net/problem/3015 풀이 정답률이 22%대로 낮은편이며 아주 골치아픈 문제이다. 일단 이 문제를 풀기위한 가장 깔끔한 방법은 새로운 사람이 줄을 설 때마다 처리해주는 식으로 문제를 푸는 것이다. 예를들어 2 1 4 순으로 줄을 서 있다고 해보자 맨 첫사람의 키인 2는 일단 스택에 넣어주고 키가 1인 다음사람을 처리해준다. 앞사람보다 키가 작아 앞사람이 다음사람을 보는데 문제가 없으므로 (1,2)의 짝만 나오기 때문에 최종답에 1을 더해준다. 키가 4인 다음 사람을 처리해 줄 때 키가 1인 사람은 더이상 사람을 볼 수 없으므로 (1,4)인 케이스, 그리고 pop을 해준뒤 키가 2인 사람도 더 이 사람보다 키가 작기 때문에 (4,2)인 케이스를 더해..

문제링크 : https://www.acmicpc.net/problem/9935 풀이 스택을 이용하여 푼 문제이다. 스택에는 pair형식을 통해 첫번쨰 인자로 해당 문자, 두번째 인자로 index를 주었다. index같은 경우는 폭탄의 각 문자의 index로써 index를 0으로 초기화 한후 만약 문자열[i] = 폭탄[index]라면 스택에 문자열[i]와 index를 넣어준 후 index+1을 하여 계속 비교해나가는 식으로 진행하였다. 이 떄 만약 폭탄에 없는 문자가 나왔을 떄는 index로 -1을 넣어 주었으며 이렇게 진행하다가 index가 폭탄의 마지막 index까지 도달하면 해당 폭탄의 문자열만큼 스택에서 제거해주는 방식을 취하였다. #include #include #include #include u..

문제링크 : https://www.acmicpc.net/problem/3111 풀이 푸느라 상당히 시간이 많이걸린 문제이다 시간초과 , 출력초과가 빡치는 문제이다. 일단 나는 deque를 통해 코드를 작성했다. deque를 통해 앞에서부터 받을 때는 push_back을 통해 뒤에서부터 받을 때는 push_front를 통해 문자들을 받았다. 문자를 받을 때 마다 누적된 문제들이 검열하는 텍스트 A와 같은지 검사하며 front_index > a >> t; int front_index, last_index;//앞에서 부터 시작하는 index와 뒤에서 부터 시작하는 index; front_index = 0; last_index = t.size() - 1; //index의 위치 맨 처음과 맨 끝으로 조정 whil..

문제링크 : https://www.acmicpc.net/problem/1182 풀이 이런 문제를 해결해야 할 때 가장 먼저 하게되는 고민은 어떻게 모든 부분집합을 검사하는가이다. 이 때 이런 고민을 쉽게 해결할 수 있게 해주는 것이 비트마스크를 활용하는 것이다. 위의 문제의 경우같이 원소가 5개인 집합의 부분집합을 모두 검사한다고 해보자 일단 만약 원소가 5개라면 부분집합의 총 가짓수는 2^5 인 32가지가 될 것이다.(원소가 n개일 때 부분집합의 총 갯수는 2^n 이다.) 고로 변수 n에 원소의 갯수가 저장되어있다고 하면 0부터 1

문제링크 : https://www.acmicpc.net/problem/1987 풀이 DFS를 통해 해결할 수 있는 문제이다. 이 때 이미 지난 알파벳을 지나지 않도록 해야하는데 이를 위해서 map을 이용해 이미 밟은 알파벳에 대해 표시할 수 있도록하였다. #include #include #include #include using namespace std; string arr[20]; bool check[20][20]; int move_x[] = { 1,-1,0,0 }; int move_y[] = { 0,0,-1,1 }; int r, c; int result = 0; map m; void dfs(int x, int y, int num) { check[x][y] = true; num++; m[arr[x][y..

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42842 풀이 빨간색은 무조건 갈색으로 둘러싸여져야한다. 그 말은 일단 카펫의 가로, 세로가 3보다는 크다는 얘기이다. 그리고 갈색 격자의 수 + 빨간색 격자의 수 = 카펫의 넓이 이기 때문에 가로 * 세로를 해서 카펫의 넓이가 나오는 것을 구한다. 이 때 (가로-2) * (세로-2) 를 한 넓이가 빨간색 부분의 넓이이므로 이것까지 조건을 충족하는 것을 구하면 문제의 답을 구할 수 있다.

문제링크 : https://www.acmicpc.net/problem/9663 풀이 재귀를 통해 가능한 모든 부분을 탐색하였다. int queen(int rows) 위와같이 줄 번호를 매개변수로 받는 함수를 통해 문제를 풀었다. 해당 행이 주어졌을 때 모든 열을 탐색하면서 만약 대각선, 세로에 다른 퀸이 서있지 않다면 bool형 배열에 그것을 체크한 뒤 result += queen(rows+1)을 하도록 했다. 이 함수는 rows = n이 됐을 때 (주어진 행을 모두 검사하고 초과된 경우) 1을 return하며 그렇지 않은 경우에는 result를 return하도록 하였다. 대각선을 검사하는 방식은 다음과 같이 하였다. 오른쪽 위에서 왼쪽 밑으로 향하는 대각선의 경우 행과 열의 index를 더해보면 다음과..

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42839 풀이 일단 먼저 에라토스테네스 방법을 통해 소수인 것과 소수가 아닌것을 bool형 배열에 구분해놓았다. bool check[10000000]; void eratosthenes() { for (int i = 2; i

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42746 풀이 꽤 많이 고민했는데 풀이가 생각보다 간단해서 짜증났던 문제이다.... 암튼 풀이는 진짜 별게 없고 sort알고리즘에서 활용하기 위한 비교함수를 만드는게 핵심이다. 비교함수에는 매개변수로 string 변수 2개를 가져와서 예를들어 string s1과 string s2가 있다면 s1+s2와 s2+s1중 더 큰것을 먼저오도록 작성하면 이 문제는 끝이 난다. #include #include #include #include using namespace std; bool cmp(string s1, string s2) { if (s1 + s2 > s2 + s1) return true; else re..

문제링크 : https://www.acmicpc.net/problem/9095 풀이 재귀를 이용해서 풀었을 때 간단하게 풀 수 있는 문제이다. 재귀함수의 매개변수로는 (현재까지 더해진 숫자, 나타내야하는 정수) 2개를 준다.-> func(int sum, int goal) 여기서 sum == goal이 될 때까지 func(sum+1, goal) ; func(sum+2, goal) ; func(sum+3,goal) 을 이용해서 뻗어나가고 만약 조건이 충족이 된다면 자연스럽게 그 경우의 수들은 처음 시작한 함수로 모일것이다. #include using namespace std; int func(int sum, int goal) { if (sum > goal) return 0; if (sum == goal) r..