Algorithm159 # 교차점 계산 # 문제 # 풀이 각각 N회 반복하는 이중 for문을 생각하면 최대 1억회 반복하게 된다 T의 범위는 나와있지 않아 T까지 포함한 시간 복잡도는 잘 모르겠지만 N이 최대 10,000이기 때문에 O(N^2) = 1억회 즉, 대략 1초 시간 제한이 따로 안나와있어서 일단 이 방법으로 해결했음 #include #include using namespace std; int first[10000]; int second[10000]; ifstream fin("cross.inp"); ofstream fout("cross.out"); int main() { int T, N, num; fin >> T; for (int i = 1; i > N; for (int j = 0; j > first[j];.. 2022. 7. 4. #1543 문서 검색 # 문제 # 입력 및 출력 # 풀이 string의 find 함수를 사용해서 문자열을 찾는다 str.find("찾는 문자")를 통해 str에서 찾는 문자가 몇 번째 인덱스에 있는지를 리턴해준다 중복되지 않게 찾아야하기 때문에 str.find("찾는 문자", 찾기 시작할 위치)를 사용하고 찾기 시작할 위치를 (앞에서부터 조회해 처음 찾는 문자를 발견한 인덱스 + 찾는 문자 길이)로 설정해준다 #include #include using namespace std; int main() { string doc, word; getline(cin, doc); getline(cin, word); int pos = word.size()*(-1), cnt = 0; while (1) { pos = doc.find(word, .. 2022. 6. 30. #2193 이친수 # 문제 # 입력 및 출력 # 풀이 dp[i]의 이친수는 dp[i-1]자리 이친수에 '0'을 붙이거나, dp[i-2]자리 이친수에 '01'을 붙인 수가 된다 따라서 점화식은 dp[i] = dp[i-1] + dp[i-2] #include using namespace std; long long dp[91] = { 0,1,1, }; int main() { int N; cin >> N; for (int i = 3; i 2022. 6. 29. #1966 프린터 큐 # 문제 # 입력 및 출력 # 풀이 우선순위 큐 하나와 그냥 큐 하나를 선언해서 풀었음 우선순위 큐를 사용해선 중요도가 가장 높은 인쇄물을 찾고 그냥 큐를 사용해서 현재 인쇄 대기중인 대기열을 확인하도록 했음 #include #include using namespace std; int main() { int T, N, lo, num; cin >> T; while (T--) { priority_queue f; queue q; int cnt = 1; cin >> N >> lo; for (int i = 0; i > num; f.push(num); q.push(make_pair(i, num)); } while (1) { if (f.top() == q.front().second) {.. 2022. 6. 28. #11052 카드 구매하기 # 문제 # 입력 및 출력 # 풀이 dp[n] = max(dp[0]+dp[n], dp[1]+dp[n-1], dp[2]+dp[n-2], ... , dp[n-1]+dp[1]) 중복되는 값은 있지만 간단한 반복문으로 구현하기 위해 그냥 위의 식으로 풀었음 #include #include using namespace std; int dp[1001]; int main() { int n; cin >> n; for (int i = 1; i > dp[i]; } for (int i = 1; i 2022. 6. 26. #11403 경로 찾기 # 문제 # 입력 및 출력 # 풀이 N*N 행렬을 전부 조회해서 해당 좌표를 시작점으로 잡고 연결된 곳을 전부 1로 표시해줌 시작점으로 잡았던 좌표만 visit를 체크해줌 #include using namespace std; int graph[100][100]; int visit[100][100]; int n; void dfs(int x, int y) { visit[x][y] = 1; for (int i = 0; i < n; i++) { if (graph[y][i]) { graph[x][i] = 1; if (!visit[x][i]) dfs(x, i); } } } void print() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout .. 2022. 6. 25. 이전 1 ··· 7 8 9 10 11 12 13 ··· 27 다음
