C++ (47) 썸네일형 리스트형 백준 단계별로 풀어보기 - 시간 복잡도 (24262,24263,24264,24265,24267,24313) (C++) 얼마 전에 [백준] - [단계별로 풀어보기] 에 [시간 복잡도] 단계가 추가되었다. 미리 알아야 할 부분) 알고리즘 문제들을 풀다 보면, 시간제한이 빡빡한 문제들이나 주어지는 N의 범위가 매우 큰 문제들이 있다. 이러한 문제들을 풀기 전에 생각을 하고 코드를 짜야 시간 낭비 없이 문제를 풀 수 있다. 시간복잡도를 정확하게 계산할 필요는 없고 우리는 대략적으로 파악한다. 대략적으로만 알아도 충분하다. 그 방법을 Big-O 표기법이라고 하고, 어떤 코드가 작동하면서 계산이 몇번 이루어지는지 다항식으로 표현한 뒤 최고차항의 차수만 따와서 표기하는 것이다. [백준] - [단계별로 풀어보기] - [시간 복잡도] 를 풀어보면, 시간 복잡도를 대략적으로 파악하는 능력을 기를 수 있다. 그래서, 시간복잡도를 대략적으로.. AtCoder Beginner Contest 291 후기 (ABC 291 3솔) 이번 ABC는 친절하게도 에디토리얼이 있으니 개인적인 생각만 간단하게 남기겠다 왜 맨날 D번에서 막힐까? A - camel Case 문자열을 입력받고, 문자열의 처음부터 끝까지 순서대로 탐색하면서 대문자가 나오는 순간 인덱스 + 1 을 출력하면 된다 개쉽네~ 생각하면서 풀다가 아스키코드를 헷갈려서 오답을 2번 제출했다 아스키코드표에서 A가 a 보다 먼저 온다 그러니까 영어 대문자를 찾으려면 'Z' 이하의 char 을 찾아야 함 B - Trimmed Mean 문제 제대로 안읽어서 2번 오답을 제출했다 설명이 필요한가?? 5*N번 입력을 받은 다음 그것들을 sort 함수로 정렬한 다음 N번부터 ~ sync_with_stdio(0) #define ll long long const int divnum = 998.. AtCoder Beginner Contest 290 후기 (ABC 290 3솔) 3108딩 72점 오름 A번 #include #define fastio cin.tie(0)->sync_with_stdio(0) #define ll long long using namespace std; int main(void) { fastio; int N,M;cin>>N>>M; vector A(N); int ans=0; for (int i = 0; i >A[i]; } for (int i = 0; i >t; ans+=A[t-1]; } cout>N>>K>>S; string T=""; for (int i = 0; i < S.length(); i++) { if(K&&S[i]=='o'){ K--; T=T+"o"; } else T=T+"x"; }.. [BOJ 11444, 약간 쉬움] 피보나치 수 6 (C++) 개인적인 난이도 약간 쉬움 알면 풀고 모르면 못푼다 모르겠어서 아이디어 부분을 구글링하고 구현만 내가 했다 복습) 피보나치 수열을 컴퓨터로 표현하는 방법은 여러 가지가 있다. 1. 재귀함수를 이용해 계산한다 2. dp를 이용해 계산한다 3. (오늘 배울 방법) : 행렬의 거듭제곱을 이용해 계산한다. 1. 기본적인 모듈러 연산의 성질을 알아야 한다. 모듈러 연산의 합/차/곱에 대해 교환법칙과 분배법칙이 성립함을 알고 있으면 된다. 입력과 출력 사이의 과정에서 매우 큰 수를 다뤄야 할 때 자주 나온다. 2. 분할정복을 이용한 거듭제곱을 할 줄 알아야 한다 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A.. 0. Let's AtCoder https://atcoder.jp/users/fepick fepick - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 코딩테스트 준비도구로 AtCoder를 활용하려고 한다. 에디토리얼이 꽤 잘 되어 있고 문제들의 수준도 고르게 나오고 제한시간을 걸어놓고 풀 수 있다는 점에서 좋은 것 같다 알고리즘 학습도구로는 백준이 더 좋지만 코딩테스트 준비도구로는 AtCoder가 나은듯?? 그리고 지금까지 AtCoder 맛보기용으로 Begineer contest 287과 289에 참가했는데, 결과가 좋지는 못하다. 2.. (작성중)정수론 입문 0. 알아둬야 할 부분 이 내용은 정수론 교과서를 따라간 것이 아니라, 알고리즘 문제를 풀면서 나에게 필요한 부분만 공부한 것이고, 주관적인 부분이 많이 섞여 있으며, 틀린 부분이 있을 수 있으니 그냥 참고만 하자 정수론 문제들은 대부분 엄청나게 큰 수까지의 범위를 다룬다. 오버플로우에 조심하자. 아니면 다른 특별한 아이디어가 필요한 문제일지도 모른다. 그냥 파이썬 쓰면 쉽게 풀릴지도 모른다... 그리고 정수론 문제 풀다가 잘 모르겠으면 그냥 풀이를 보자. 정수론은 정말 알면 쉽게 풀지만 모르면 못 푼다고 생각한다. 1. sqrt, ceil, floor, round 이녀석들은 SQL을 하든 엑셀을 하든 어떤 언어를 공부하든 가장 기본적이고 유용하게 쓰일 녀석들임 C++에서 정수끼리의 나눗셈 결과는 .. [BOJ 25907, 쉬움] 양과 늑대 (C++) 개인적인 난이도 쉬움 인터랙티브 문제가 처음이라면 https://www.acmicpc.net/problem/23306 이 문제를 먼저 풀어보길 바란다 인터랙티브 문제는 머리가 아프지만 실제 난이도에 비해 티어가 높게 잡히는 것 같기도 하고 풀어보면 재미있다. 개꿀임 성공한 풀이) 내가 컴퓨터고 컴퓨터가 사람이라고 생각한 뒤, 이분탐색을 이용해 컴퓨터랑 스무고개를 한다고 생각하면 된다 양의 숫자와 늑대의 숫자가 같아지기 위한 조건은, 어떤 짝수의 날짜 D에 대해 양의 숫자가 정확히 D/2만큼 존재하는 것이다. 우리는 그러한 날짜 D를 찾아내 ! D로 출력하면 된다. 양의 숫자가 D/2보다 많다면, 그 이후에 늑대와 양의 숫자가 같아지는 어떤 날이 존재할 것이다. 양의 숫자가 D/2보다 적다면, 그 이전에 .. [BOJ 27296, 약간 어려움] 카탈란 마스터의 선분 그리기 게임 (C++) 개인적인 난이도 약간 어려움 문제가 정말 안 읽힌다. 카탈란이 뭔지도 모르겠고 처음엔 이게 무슨 어려운 정수론 문제인 줄 알았으나 한참 생각하고나서야 애드혹인걸 알았다 게임 이론 문제에 ->>> 두 명의 플레이어가 모두 자신이 승리하기 위해 최선으로 행동한다면이라는 내용이 들어가면, 상상도 못한 쉬운 답이 나오는 경우가 많은 것 같다. 과거에도 https://www.acmicpc.net/problem/26074 이거 풀면서 그렇게 생각했다. 접근 방법) 점의 개수가 N이라는 정수로 주어졌을 때, N이 커지면서 그릴 수 있는 다각형의 개수는 수없이 많아진다. 그렇지만 이 문제의 조건은 N이 정해졌을 때 선공이 이긴다 또는 후공이 이긴다 의 결과가 딱 1가지만 존재함을 내포하고 있다. 그러므로 우리는 점의 .. [BOJ 1799, 약간 어려움] 비숍 (C++) 개인적인 난이도 약간 어려움 실패한 풀이) 체스판에서 대각선을 체크하면서 말을 놓는 백트래킹의 구현은 그렇게 어렵지 않으나, 그냥 백트래킹하면 시간초과가 나게 되는 문제이다. 약간의 아이디어로 시간복잡도를 크게 줄일 수 있다. 안되는 이유 최악의 경우, 10*10 의 배열의 모든 칸에 비숍을 배치할 수 있다 검사할 칸의 개수 100개 -> 백트래킹 없이 완전탐색할 경우 2^100~=1e30 대략 1e22초 소요 백트래킹으로 탐색하며 비숍을 배치할 수 있는 위치에만 비숍을 배치한다고 해도 시간초과가 난다. 그 이유는 이러하다. 10*10 크기의 2차원 배열의 경우 20+20 개의 대각선을 그릴 수 있다. 인정?? 인정~ 비숍을 어느 한 위치에 놓을때마다 우상향 방향 대각선 1개와 좌상향 방향 대각선 1개에.. [BOJ 1629, 쉬움] 곱셈 (C++) 개인적인 난이도 쉬움 알면 1분만에 풀고 모르면 그냥 틀린다 매우 중요한 개념이 2 가지 들어있다. 정수론(모듈러 산술) & 분할정복(log N) 몰라서 2번 틀렸다 처음엔 정수론 몰라서 오버플로우로 틀리고 두번째엔 분할정복 몰라서 시간초과로 틀림 성공한 풀이) 핵심 1) 모듈러연산은 신기하게 덧셈 뺄셈 곱셈 분배법칙이 가능하다. 핵심 2) 거듭제곱 계산(pow) 는 분할정복을 이용해 계산하면 log N 안에 끝남 성공한 코드 #include #define fastio cin.tie(0)->sync_with_stdio(0) #define ll long long using namespace std; int main(void) { fastio; ll A,B,C;cin>>A>>B>>C; A%=C; ll ans.. 이전 1 2 3 4 5 다음
