Doby's Lab

https://www.acmicpc.net/problem/10769 10769번: 행복한지 슬픈지 승엽이는 자신의 감정을 표현하기 위해서 종종 문자 메시지에 이모티콘을 넣어 보내곤 한다. 승엽이가 보내는 이모티콘은 세 개의 문자가 붙어있는 구조로 이루어져 있으며, 행복한 얼굴을 나 www.acmicpc.net 공백 포함하기 위해 문자열 함수 getline() 사용 #include #include using namespace std; int main(){ string value; getline(cin, value, '\n'); int h = 0; int s = 0; for(int i = 0; i = value.size() - 2){ continue; } i..

https://www.acmicpc.net/problem/15489 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net 파스칼 삼각형의 이항 계수의 특성상 r번째 행, c번째 열은 (r - 1)C(c - 1)과 같음을 이용하여 풀면 된다. 그리고, 이중 for문을 이용하여 변 w 길이를 만족하게끔 최종합에다가 (r - 1)C(c - 1)을 더해주면 된다. [AC 코드] #include #include #define MAX 30 + 1 using namespace std; int cache[MAX][MAX]; int combi(int ..

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 n r이 nCr이라는 것을 알면 예전에 풀었던 문제와 똑같이 풀린다. 다른 점은 나머지 정리(MOD == 10007)로 인해 문자열의 합을 구할 필요 없다는 점이었다. (콤비네이션 예전 포스팅 https://draw-code-boy.tistory.com/101) [AC 코드] #include #include #define MOD 10007 using namespace std; int cache[1001][1001]; int combi(int n, int r..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 우선, 글에 들어가기 앞서 포스팅의 제목에서 '수열'이라고 강조한 이유는 '문자열'과 '수열'은 다른 의미이기 때문이다. 저번에 LIS를 포스팅하면서는 수열과 집합의 차이를 느꼈는데 이번 키워드에서는 문자열과 수열의 차이를 알아야 한다. (집합에 관해 적은 포스팅: https://draw-code-boy.tistory.com/85) [문자열 vs 수열]..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 다리를 잇는 경우가 고등학생 때 배우던 조합론: 콤비네이션을 기억해낼 수 있다면 풀릴 수 있는 문제였다. 시간도 0.5초로 짧아서 탑 다운 DP형식으로 구현을 했고 범위는 30 이전이라 문자열의 합은 구현하지 않아도 될 거 같았다. 콤비네이션에 관한 문제를 예전에 풀고, 포스팅해놓았어서 쉽게 풀렸다. https://draw-code-boy.tistory.com/101 [알고리즘] 백준 2407번:..

https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 > a >> b; map[a].push_back(b); map[b].push_back(a); } bfs(1); int cnt = 0; int minValue = INT_MAX; for (int i = 1; i

https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 바로 직전에 사이클을 문제를 풀어서 그런지 쉽게 재귀를 통해 풀 수 있었다. 방문하지 않았던 노드들을 탐색하기 시작한다. 방문하지 않은 노드로 탐색을 시작하면 바로 해당 노드의 방문을 체크한다. 해당 노드가 가리키는 노드가 방문하지 않았으면 재귀를 통해 다음 노드로 간다. 만약 가리키는 노드가 방문이 되어있으면 사이클이라는 ..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이번 문제는 계속 시간 초과가 나서 계속 뜯어고칠수록 코드를 점진적으로 진화시키는 기분이 들었다. 이번 문제의 키워드는 '사이클의 유무 판단'이다. 첫 시도 첫 시도에서는 각 노드마다 for문을 통해 '이 노드는 사이클을 형성하는가?'의 여부를 따졌었다. 그 여부는 백트래킹을 통해 두 개의 인자를 받아들여 코드를 짰다. 하지만, 노드의 최대 개수 100,000개가 주어지고, 100,000개 전체가 하나..