너와 나의 스토리

문제: https://www.acmicpc.net/problem/1389 문제 풀이: - 자기 자신은 dist[a][a]=0;- 양방향이므로 dist[a][b]=1;dist[b][a]=1; - 그 외 INF로 채움 - 각 점에서의 케빈 베이컨 구해서 vector에 넣음- sort 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa6599396958ea#file-1389-6

문제: https://www.acmicpc.net/problem/11403 문제 풀이:갈 수 있는 곳만 1 나머지는 INF 부여결과가 INF 아니면 갈 수 있는 곳 소스 코드:https://gist.github.com/hovy1994/bca02488b651f0f128aa6599396958ea#file-11403

문제: https://www.acmicpc.net/problem/3109 문제 풀이:처음 열의 맨 윗 칸에서 시작 ㄴ> 위 칸이 최대한 위쪽으로 진행해야 (↗) 많이 설치 가능 - ↗ → ↘ 순으로 갈 수 있는 방향 확인하고 진행하므로 가장 많이 설치할 수 있게 이동 함- 즉, visit을 지우지 않고 기록하면서 진행하면 됨 소스 코드:https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-3109

문제: https://www.acmicpc.net/problem/1941 문제 풀이: * 처음에는 단순하게 dfs로 풀었는데 ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ ㅇ 이런식으로 이동이 불가능 했다 -> fail - 무작위로 7명을 뽑아낸 후 - '이다솜파(S)'가 더 많은지 (4명 이상) 확인YES -> 모두 연결되어 있는가 (bfs 이용)YES -> cnt++; 소스 코드:https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-1941 Testcase:case1:YYYYYYYSYYYSYSYYYSYYYYYYY -> 답1: 48 case2:YYYYYYYSYYYSSSYYYSYYYYYYY -> 답1: 592 * 다른 방법: 훨씬 빠름bfs, dfs 둘 다..

문제: https://www.acmicpc.net/problem/2210 문제풀이1: 방문한 루트를 string( tmp)으로 기록하고 tmp.size()==6일때 map에 저장해 map에 존재하지 않을 경우만 cnt++ 해서 cnt를 출력하는 방법으로 문제를 풀었다. 소스코드: https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-2210 결과:메모리: 2652 KB 시간: 4ms 문제풀이2: 개선된 방법 map을 사용하지 않고 bool check[10][10][10][10][10][10]; 을 사용해 존재하는 경로를 파악하였다 소스코드: https://gist.github.com/hovy1994/8b11fc944de34cd39b..

문제:https://www.acmicpc.net/problem/1339 문제 풀이1: 백트래킹 이용 void func(int cur,int pos, int cur_sum,int sum,int visit) cur: 몇번째 단어를 보는 중인지 알려줌pos: 현재 보는 단어에서의 위치cur_sum: 현재 보는 단어에서 현재위치까지의 합sum: 지금까지의 합visit: 지금껏 사용한 숫자를 표시 모든 수를 대입해보고 가장 결과 값이 큰 값을 출력 소스 코드: https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-1339 결과:메모리: 1992KB 시간: 632ms 문제 풀이2: 각각의 위치에 따른 값을 부여ex) ABCC위치의 값은 1B위..

문제: https://www.acmicpc.net/problem/2023 문제 풀이:- '에라토스테네스의 체' 이용해서 풀려고 bool arr[100000000] 만들면 메모리 초과가 난다 ㅎㅎ - 맨 첫 숫자는 2 3 5 7만 가능하다 - 홀수만 가능하다ㄴ> 시간 많이 줄어들기 때문에 그때그때 소수인지 판단해줘도 됨. 소수코드:https://gist.github.com/hovy1994/8b11fc944de34cd39b157b2c16144a87#file-2023

문제: https://www.acmicpc.net/problem/1562 문제 풀이:dp[수의 길이][수의 개수][1