본문 바로가기

자료구조와 알고리즘/백준 beakjoon9

[백준] 1629번 : 곱셈 (#모듈러연산, 분할정복, 재귀, overflow) https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 무작정 풀면서 들이박는? 중인 나한테는 풀이를 보고도 한번에 이해하기 힘든 문제였다... 풀기 전에 모듈러 연산과 분할정복에 대해 알아야 한다. 모듈러 연산 (a+b)%c = (a%c + b%c)%c (a*b)%c = (a%c * b%c)%c 분할정복 (Divide and Conquer) b가 짝수일때 : a^b = a^(b/2) x a^(b/2) b가 홀수일때 : a^b = a^(b/2) x a^(b/2 + 1) 첫번째, 1629번 문제의 입력값 A,B,C 는.. 2024. 1. 17.
[백준] 3986번 : 좋은 단어(#stack) https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 풀이 방법 문자 위에 아치형 곡선으로 같은 단어끼리 이어줍니다. 다른 곡선과 겹치지 않게 모두 이어진다면 좋은 단어라고 합니다. 입력 받은 문자열을 세로로 돌려 stack을 쌓는다고 생각합니다. for문으로 하나씩 stack의 가장 top과 비교를 합니다. stack의 size가 1보다 크고, stack의 맨위top과 같은 글자면 stack에서 꺼내줍니다. (pop) 만약 스택이 비어있거나, top과 같은 .. 2024. 1. 11.
[백준] 1940번 : 주몽 (#조합) https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 풀이 방법 두개의 재료 고유번호 합이 10,000,000 이 되면 갑옷이 만들어집니다. N개의 재료가 주어지고, 두개의 재료를 합쳐 M이 되면 갑옷이 됩니다. 각 재료의 번호는 최대 100,000인 자연수입니다. 따라서, 순서와 상관없이 두 재료의 합이 M이 되는 경우의 수( nC₂ )를 구하면 됩니다. 풀이 코드 #include using namespace std; in.. 2024. 1. 7.
[백준] 1213번: 팰린드롬 만들기 (# string, char, insert) https://www.acmicpc.net/problem/1213 2024. 1. 6.

티스토리툴바