백준22 [백준] 회문 (골드5, 시간복잡도는 왜 선형을 유지할 수 있을까.. N^2이 아니고?) https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 설명 회문(palindrome)은 앞 뒤 문자가 같아, 앞으로 읽어도 뒤로 읽어도 같은 문자가 되는 문자열을 의미한다. 우선 회문의 개념은 알았으니 문제를 좀 살펴보면, O(N^2) 풀이로는 도저히 풀 수 없을 것 같다는 걸 문자열의 범위만을 봐도 알 수 있다. 문자열의 길이는 최대 10만 까지 주어지므로, T개의 케이스를 모두 연산해야 하기 때문에 O(T * N^2) 만큼의 시간이 소요되게 알고리즘을 작성하면 시간초과가 난다.. 2024. 2. 8. [백준] 두 수의 합 [왜 여기까지만 생각했을까.. JAVA] 투 포인터 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 설명 실패했던 문제 중 가장 의미 있게 풀어낸 문제라고 생각해서 기록을 남겨보려고 한다. 이번 문제는 투 포인터에 관련된 문제다. 최근 들어 시간 복잡도를 계산하는 연습을 틀리더라도 최대한 정확하게 해 보려고 노력하고 있다. 그래서 시간 복잡도가 어떻게 되는지와 어떤 방식으로 생각을 해볼 수 있는지 작성해보려고 한다. 투 포인터를 .. 2024. 2. 3. [백준] (골드4) 알파벳 [실패 코드 + 생각해볼 부분 + set을 쓰는 것이 왜 효율적인지] BFS, DFS https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 실패 코드 import sys from collections import deque from string import ascii_uppercase r, c = map(int, input().split()) board = [list(input()) for _ in range(r)] def bfs(sx, sy): queue = deque([(sx, sy)]) dx = [(-1,.. 2023. 11. 4. [백준] 행렬 덧셈 [코드 + 패턴을 찾아보고 풀어보는건 어떨까?] 구현 https://www.acmicpc.net/problem/2738 2738번: 행렬 덧셈 첫째 줄에 행렬의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 차례대로 주어진다. 이어서 N개의 줄에 행렬 B의 원소 M개가 차례대로 주어진다. N과 M은 100보다 작거나 같 www.acmicpc.net 코드 #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; int** array = new int*[2*n]; for (int i = 0 ; i < 2*n; i++){ array[i] = new int[m]; fill.. 2023. 8. 31. 이전 1 2 3 4 ··· 6 다음