벨로그로 바꿀까 고민하는 블로그

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수 배열을 만들어야 하는 것 빼고는 어제 풀었던 연속합 문제랑 비슷한 것 같다. Python으로 제출하니까 시간초과가 나길래 이번에도 C++로 다시 풀어봤다. 처음에는 #define MAX 4000000으로 한 후 primes[MAX] 이렇게 선언했는데 아예 입력이 받아지질 않았다. Chat GPT한테 물어보니까 이렇게 큰 크기의 배열을 stack에 할당하려고 하면 stack overflow가 발생할 수 있다고 한다. vector로 배열의 크기를 n으로 동적할당 하고 나니까 쉽게 통과했다. HTML 삽입 미리보기할..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 부분합 2 문제에서 푼 코드를 조금 바꿔서 풀었다. HTML 삽입 미리보기할 수 없는 소스

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 파이썬으로 비슷하게 코드를 짰었는데 시간초과가 나와서 오랜만에 C++로 풀어봤다. 이 코드는 시간복잡도가 O(n^2) 인데, 다른 풀이를 읽어보니까 투포인터 알고리즘으로 시간복잡도를 O(n)으로 줄일 수도 있었다.. 28ms 에서 4ms로 시간이 확 줄어드는게 너무 신기하다!! ㅋㅋㅋㅋ HTML 삽입 미리보기할 수 없는 소스 sum > m 이면 arr[st..

강의 자료 참고해가면서 최대한 정리를 해봤는데... 이게 맞나...??😂 DNS: IP 주소를 Host 명으로 바꿔주거나 Host 명을 IP 주소로 바꿔줌 (3계층 7계층) ARP: IP 주소를 MAC 주소로 바꿔줌 (3계층 -> 2계층) RARP: MAC 주소를 IP 주소로 바꿔줌 (2계층 -> 3계층)

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 백트래킹이 너무 싫다... 아직도 제대로 이해를 못한 것 같다. 실버2 문제인데도 스스로 못풀다니....... 코딩 어렵다..😭 부분집합 배운지 6년이나 지나서 부분 수열의 합이라는걸 대체 어떻게 구해야 하는지 잠시 헷갈렸다. 부분집합의 각 원소들을 선택하거나 선택하지 않는 경우를 나눠서 세면 좀 쉬워지는 것 같다., HTML 삽입 미리보기할 수 없는 소스 참고..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제가 어렵다기보다는 시간 초과랑 메모리 초과때문에...ㅠㅠㅠ 처음에는 매개변수로 지나온 알파벳들을 문자열 형태로 넘겼었는데 안되길래, 풀이를 봤다. 문자열로 계속 넘기면 낭비니까, visited 배열을 만들어서 이미 탐색한 알파벳은 다시 탐색하지 않도록 하면 되는 것이었다.. 아니 분명 풀이랑 똑같이 썼는데 왜 메모리 초과가 나오나 했는데 setrecursion(10**7) 때문인 것 같..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 암호만들기 문제랑 비슷한 문제인 것 같다. HTML 삽입 미리보기할 수 없는 소스

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 처음에는 이렇게 풀었었는데, 문제에 제시된 테스트 케이스만 통과했어서, 결국 풀이를 찾아봤다. import sys from collections import deque input = sys.stdin.readline def backtracking(y, x): # 좌표 if matrix[y][x] != 0: return for i in range(1, 10): endflag = True # 가로줄,..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 처음에는 부르트포스 방법처럼 하나씩 다 대입해서 풀려고 했는데, 이렇게 하다가는 답이 안나올 것 같아서 풀이를 찾아봤다. 입력을 받은 후 정렬한 후 가능한 모든 조합을 재귀함수로 만든 다음, 조건에 맞는 경우 출력하면 되는 것 같다. 근데 스스로 못 풀 것 같다😢 HTML 삽입 미리보기할 수 없는 소스 참고 1759번 풀이: https://fre2-dom.tistory.com/454

https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 🙃 특정 층을 한 번만 방문하라는 조건같은건 없어서 방문 처리를 어떻게 해야 하는지 잠깐 고민했었는데, 어떤 특정 층으로 다시 돌아온다는건 그 층에서 시작하는 것과 다름이 없으므로 visited 배열을 선언해서 특정 층을 방문하고 나면 방문 처리를 했다. HTML 삽입 미리보기할 수 없는 소스