프로그래밍 자료정리

🚀 2025 ACPC AWS x Codetree 프로그래밍 경진대회 🚀프로그래밍 실력을 뽐낼 준비가 되셨나요? 세계 최고의 클라우드 서비스인 AWS 인프라를 활용하여, 국제정보올림피아드 출신들로 구성된 코드트리 팀이 직접 출제 및 관리하는 프로그래밍 경진대회가 열립니다!✅ 온라인 예선: 4월 21일(월) ~ 5월 16일(금)✅ 본선 대회: 5월 25일(일) 13:00~17:00 (AWS 코리아 본사)✅ 참가 자격: 대학(원) 재학생 또는 휴학생✅ 사용 가능 언어: Python, Java, C/C++최대 300만원의 상금과 국제정보올림피아드(IOI), ICPC 수상자들의 멘토링 기회까지!지금 바로 참가 신청하고 최고의 알고리즘 대회에서 당신의 역량을 펼쳐보세요.👉 참가 신청: https://disco..

문제 링크https://www.acmicpc.net/problem/18789  알고리즘 분류- 구현- 그래프 이론- 그래프 탐색- 해 구성하기- 깊이 우선 탐색- 무작위화- 휴리스틱 코멘트8x14 격자판에 0~9의 숫자를 기록하여, 어느 한 점에서 8방향 중복 DFS 탐색을 통해 만들 수 있는 숫자 x가 있을 때 격자판은 숫자 x를 읽을 수 있다고 한다. 이 때 0부터 N까지의 모든 숫자를 읽을 수 있으면 격자판은 N의 점수를 가지게 된다. 이 점수 N을 극대화하는 것이 이 문제의 요구사항이다.완전탐색을 하게 될 경우 10^112라는 어마어마한 연산량을 요구하기 때문에 지역 최적해를 구하는 문제가 되겠다. 엄청 오래전부터 풀고 싶었던 문제인데, 최근에 드디어 풀게 되어서 블로그에 포스팅한다.제일 처음에는..

문제 링크https://www.acmicpc.net/problem/1006 1006번: 습격자 초라기하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소www.acmicpc.net 알고리즘 분류- 다이나믹 프로그래밍 코멘트다른 블로그에서는 2차원 dp로 해결한 코드도 보였다. 나는 그냥 3차원 dp 필드를 이용하여 풀이하였음.index i를 기준으로 바깥쪽 부분과 안쪽 부분이 i-1과 i를 동시에 커버하는지에 따라 type를 4종류로 나누는게 핵심이었다. 아래 2가지의 경우i-1번째 칸이 i번째 칸을 침범하지 않으므로 typ..

문제 링크 https://www.acmicpc.net/problem/16441 16441번: 아기돼지와 늑대 첫 번째 줄에는 격자의 행의 수를 나타내는 N (3 ≤ N ≤ 100) 과 격자의 열의 수를 나타내는 M (3 ≤ M ≤ 100) 이 주어집니다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열 www.acmicpc.net 알고리즘 분류 그래프 탐색 넓이 우선 탐색 (BFS) 코멘트 필드 타입을 저장하는 2차원 배열, 방문 여부를 체크하는 2차원 배열 2개로 bfs 탐색을 하면 된다. 상하좌우 1칸씩 이동할 때 이동하는 칸이 빙판이면 산이나 초원을 만날 때 까지 현재 진행 방향으로 계속 가면 된다. 늑대는 여러마리일 수도 있다는 점에 유의 소스코드 더보기 #define GR..

문제 링크 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 알고리즘 분류 수학 누적 합 코멘트 0부터 n까지의 누적합(n-1이 아님) mod M을 구했을 때, 나머지가 같은 두 누적합 A, B (A> mN >> mM; mSumArr.resize(mN + 1, 0); mModCnt.resize(mM, 0); int stkCnt = 1; for (int i = 0; i < mN; i++) { lint..

문제 링크 https://www.acmicpc.net/problem/10464 10464번: XOR 입력의 첫 번째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 1000)가 주어진다. 다음 T 개의 줄에는 두 개의 정수 S와 F가 주어진다. (1 ≤ S ≤ F ≤ 1 000 000 000) www.acmicpc.net 알고리즘 분류 수학 코멘트 몰라서 인터넷 찾아봤다. 힌트 1 더보기 https://www.secmem.org/blog/2021/07/17/various-technic-solving-xor-problem/ XOR 관련 문제를 푸는 접근법들 들어가기 전에 XOR (bitwise exclusive or)은 대표적인 bit 연산 중 하나입니다. 다른 bit 연산인 AND,OR,NOT이 갖지 못하..

문제 링크 https://www.acmicpc.net/problem/13422 13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마 www.acmicpc.net 알고리즘 분류 누적 합 두 포인터 코멘트 deque나 queue를 활용하면 쉽게 풀 수 있다. 최적화 안해도 시간이 널널해 보여서 컨테이너 2개를 사용해서 풀었다. 소스코드 더보기 class BaekJoon { public: BaekJoon() { int testCase; cin >> testCase; while (testCase--) { int N, M, K; cin >> N >> M >> ..

문제 링크 https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 알고리즘 분류 우선순위 큐 코멘트 단계별로 풀어보기 우선순위 큐 단계의 1655번 "가운데를 말해요"와 출력형식만 다른 문제이다. 우선순위 큐 2개를 사용한다는 것이 핵심이다. 소스코드 더보기 class BaekJoon { public: BaekJoon() { int T; cin >> T; while (T--) { Median(); } } void Media..