소프티어

c 코드 공유합니다. 효율적으로 짜진 않았고 그냥 나열식으로 짰어요

#include <stdio.h> #include <math.h> int value = 0; int values[3][3] = {0,}; int main(void) { for(int i = 0; i < 3; i ++){ for(int j = 0; j < 3; j ++){ scanf("%d",&value); values[i][j] = value; } } int old_diff = 10; int new_diff = 0; // 가로 for(int i = 0; i < 3; i ++){ new_diff = abs(values[i][0] - values[i][1]); new_diff = new_diff + abs(values[i][0] - values[i][2]); if (new_diff < old_diff){ old_diff = new_diff; } new_diff = abs(values[i][1] - values[i][0]); new_diff = new_diff + abs(values...

풀이의 잘못된 점 잡아주시면 감사하겠습니다.

n 최대 500,000 문자열이 최대 1,000,000 이라길래 S length + T length = 1,000,000 이면 S에서 X를 탐색하는 과정에서 O(NS) 로 시간초과가 날것이라 생각해서 탐색 과정을 없애기위해 아래처럼 풀었는데요. 그냥 한 글자 입력마다 x인지 확인하고 인덱스만 찾아놓아서 합치는 방식으로 하려했는데 계속 틀렸다고 나와서요.. int n; char t[500005], ans[500005]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int idx = 0; getchar(); int cntA = 0; char a; while (1) { a = getchar(); if (a == ' ') break; if (a == 'x' || a == 'X') { idx = cntA; ...

시간 초과의 가능성

안녕하세요, 파이썬으로 문제 풀이 후 궁금한 점 있어서 글을 남깁니다. 풀이는 유튜브에 업로드 된 해설의 코드를 그대로 사용하였습니다. 문제에서 4중 for문을 사용하는데, Worst case의 경우 하나의 입력문에 대해 (20)^4=16*10^4 번의 연산을 거친다고 이해하였습니다. 여기에 Q의 최댓값이 3*10^4라면 최대 연산량이 (3*10^4)*(16*10^4)=48*10^8 의 연산량을 가지는 것이 아닌가요? 파이썬에서 1초 당 10^8 정도의 연산을 할 수 있다고 알고 있는데, 그렇다면 이 경우에는 해당 풀이가 시간 초과가 날 것이라 판단해야 하는것이 아닌지 궁금합니다. 제가 시간 복잡도 계산이 미숙하여 실수했을 수도 있을 것 같습니다. 이 문제의 경우 시간 초과가 나지 않을 것이라는 것을 어떻게 판단해야 할까요?

c언어 반례 부탁드립니다...!

#include<stdio.h> #include<stdlib.h> #include<string.h> int main(void) { char room[50][2][11] = {0,}; char room_name[11] = {0,}; char output[50][11] = {0,}; char temp[11]; char temp_cnt; char room_name_output[50][11] = {0,}; int count[50] = {0,}; int n; //회의실 개수 int m; //예약된 회의의 개수 int start_time; int end_time; int same; int current; int cnt; int zero_cnt[50]; scanf("%d %d", &n, &m); for(int i = 0 ; i < n ; i++) { scanf("%s", room[i][0]); } for(int i = 0 ; i < m ; i++) { scanf("%s %d %d", roo...

왜 일치하지 않는 TC가 생기는지 모르겠어요ㅠㅠ (C++)

#include<iostream> using namespace std; int main(int argc, char** argv) { int K,P,N; cin >> K >> P >> N; int result = K; for(int i = 0 ; i< N; i++){ result *= P; } cout << result%1000000007; return 0; }

[21년 재직자 대회 예선] 비밀 메뉴 - 파이썬 풀이

deque를 사용해서 처음부터 끝까지 사용자가 입력한 버튼을 M개씩 비교하는 풀이가 가능합니다. 여기서 N과 K값은 사용하지 않기 때문에 _(언더바)로 받아줘도 됩니다. import sys input = sys.stdin.readline from collections import deque M, N, K = map(int, input().split()) secret = deque(list(map(int, input().split()))) user = deque(list(map(int, input().split()))) queue = deque() while user:     queue.append(user.popleft())     if len(queue) > M: queue.popleft()     if queue == secret: break print('secret' if secret == queue else 'normal') 한편 문제 ...

파이썬 시간초과문제

import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) grid = [list(sys.stdin.readline().strip()) for _ in range(n)] ds = [(1, 0), (-1, 0), (0, 1), (0, -1)] ghost_pos_list = [] for i in range(n):     for j in range(m):         if grid[i][j] == 'D':             dest_pos = [i, j]         elif grid[i][j] == 'G':             ghost_pos_list.append([i, j])         elif grid[i][j] == 'N':             start_pos = [i, j] def calc_na...

같은 코드에서 순서만 바꿨는데 메모리 초과가 발생하는 이유가 궁금합니다.

같은 코드에서 순서만 바꿨는데 위에 코드는 4가지 테스트 케이스에서 메모리초과가 발생하고 아래는 메모리초과가 발생하지 않습니다. 그 이유가 무엇인가요? #메모리 초과 발생 코드 import sys sys.setrecursionlimit(10**6) def DFS(now, visit, adj): if visit[now]==1: return else: visit[now]=1 for neighbor in adj[now]: DFS(neighbor, visit, adj) return n,m=map(int, input().split()) # 정점, 간선 adj=[[] for _ in range(n+1)] # 노드별 이동 가능한 노드들 정보 adjR=[[] for _ in range(n+1)] # adj_reverse for _ in range(m): ...

DP로 푼 코드 + 해설 공유합니다 (파이썬)

다른 분들의 연습문제 톡을 구경하던 도중 DP이지만 저와 다른 방식으로 해결하신 분의 풀이 방법을 보고 배워 가는 내용이 많아서 제가 푼 방법도 공유해 봅니다! 문제를 처음 접했을 때는 2차원 DP 배열을 만들어서 dp[i][j][0]에는 (i, j)번째 칸까지의 최대 수확량을, dp[i][j][1]에는 (i, j)번째 칸까지 수로를 넣은 경로 중 가장 큰 값을 집어넣으려고 했습니다. 하지만 스프링클러를 사용하기 전 수확량이 최대인 경로라고 하더라도, 스프링클러를 사용한 후 수확량이 최대가 아닌 경우가 발생합니다. 예를 들어 4 1 3 5 7 9 1 1 1 1 1 1 1 로 입력값이 주어진 경우, 스프링클러를 사용하지 않았을 때 최대 수확량은 (1+3+5+7+1+1) = 18입니다. 그러나 스프링클러를 사용했을 때 최대 수확량은 (1+18+1+1+1+1) = 23이 됩니다. 따라서 이 방식으로 dp배열을 관리하면 오답을 받습니다. 제가 푼 방식은 2차원 DP 배열을 만들고, d...