2021. 9. 30. 01:34ㆍ카테고리 없음
본격적으로 공부하기 전 초보자를 위한 다양한 정보를 담았습니당
도움이 될지는 모르겠지만.. 보고 싶은 내용만 적당히 보면 될 것 같아요
목차
- 알고리즘 하면 뭐가 좋아요?
- 어떻게 공부해야 하나요?
- 어떤 코드를 짜야 할까요?
- ⭐⭐⭐얼마나 빠른 코드를 짜야 하나요? / 속도는 어떻게 측정하나요?⭐⭐⭐
- 왜 다들 C++을 쓰나요?
- 맞았는데 왜 틀려요??
- ⭐⭐⭐빠른 입출력이 뭔가요⭐⭐⭐
- 기타 팁
알고리즘 하면 뭐가 좋아요?
보통 "코드를 효율적으로 작성할 수 있게 되고 문제해결능력을 기를 수 있다" 라고 많이 이야기합니다.
이런 흔한 대답을 제외하고 제가 알고리즘 문제풀이를 하면서 직접적으로 얻은 점은
- 백준에서 골드/플래티넘/다이아를 달아볼 수 있다
- 백준 아이디에 이쁜 색을 넣을 수 있다(Codeforces, Atcoder)
- 웬만한 전공과목이 다 쉬워진다(대학 가서도 그럴지는 잘 모르겠습니다)
- 인서울 대학에 가기 쉬워진다(SW특기자 전형)
- 학기마다 상을 하나씩 받을 수 있다
- 세특에 적을 것들이 많아진다
- 코딩테스트를 따로 열심히 공부하지 않아도 된다
- 넥슨에서 매년 티셔츠를 선물받는다(NYPC)
- 재밌는 취미를 가지게 되었다
정도가 있습니다.
잃은 점도 꼽아보자면
- 잘
- 모르
- 겠
- 습니
- 다
어떻게 공부해야 하나요?
이번 대회를 열심히 준비해보는 것이 좋은 시작이라고 생각합니다 😀
(Beginner Division 참가자 한정)
공개된 알고리즘 주제를 이해하고 관련 문제를 많이 풀어보면 이번 대회에서 좋은 결과를 얻을 것 같습니당
"교과서 위주로 공부하세요" 같은 말이긴 하지만 저는 다른 특별한 방법을 모릅니다ㅠㅠ
각 게시물에서 알아야 할 점, 연습 문제 등까지 올릴 예정입니다
이번 대회를 넘어서 알고리즘 실력을 더 키우고 싶다면 아래 글들을 참고하면 좋을 것 같아요!
알고리즘 문제풀이(PS) 시작하기
이런건 고수들이나 써야 하지 않나 싶지만, 그래도 1년정도 공부하면서 이 분야를 어떻게 시작해야 할지 써보려 한다. 라고 운을 뗀다음 열심히 내 얘기만 했던 후속편이다. 내 인생사가 궁금하
plzrun.tistory.com
https://baactree.tistory.com/52
알고리즘 공부, 어떻게 해야하나요?
오랜만에 정상적인 포스팅을 쓴다. 메일로 가장 많이 물어 보는 질문들이 [알고리즘 공부 어떻게 해야하나요? 어떻게 하셨어요? 뭘 공부해야 할 지 모르겠어요.] 와 같은 질문들이다. 위 질문에
baactree.tistory.com
어떤 코드를 짜야 할까요?
주어진 문제를 빠르게, 적은 메모리를 사용하여 효율적으로 푸는 코드를 작성하면 됩니다.
개발할 때 좋은 습관은 아니지만 결국 대회에서는 정확성 다음으로 속도가 중요하기 때문에 알고리즘 문제를 풀 때는 네이밍 규칙이고 뭐고 본인만 알아볼 수 있게 짜도 괜찮습니다.
얼마나 빠른 코드를 짜야 하나요?
요약: 제한시간이 1초라면 문장의 실행 횟수가 대략 1억 ~ 10억 번을 넘어가면 안 됩니다.
아래 내용이 복잡하다 싶으면 문장이 최대 몇 번 실행되는지를 알아서 적당히 계산해도 괜찮을 겁니다.
같은 프로그램이라도 컴퓨터마다 속도가 다를 수 있기 때문에,
프로그램의 속도는 문장이 실행되는 총 횟수를 기준으로 계산합니다.
총 횟수는 어떻게 계산할까요?
- 반복문의 시행 횟수 * 반복문 안의 문장 수
- 함수의 호출 횟수 * 함수 안의 문장 수
- 그냥 호출되는 문장 수
등등을 모두 구해 더하면 되는데, 이때 정확히 구할 필요는 없고 대충 적당히 비슷하게만 구하면 됩니다.
어느 정도 대충이냐? 입력에 따른 실행 횟수를 식으로 나타냈을 때 최고차항의 차수만 같으면 됩니다.
n을 입력받아 1부터 n까지의 합을 구하는 두 코드를 통해 알아봅시다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// 1번 코드
#include <stdio.h>
int main(){
int n;
scanf("%d", &n);
printf("%d", n * (n + 1) / 2);
return 0;
}
// 2번 코드
#include <stdio.h>
int main(){
int n, answer = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
answer += i;
printf("%d", answer);
return 0;
}
|
cs |
1번 코드는 n이 얼마나 커지더라도 문장이 실행되는 횟수가 3번으로 변하지 않지만,
2번 코드는 실행 횟수가 대충 n번 정도입니다.
정확히 식으로 나타내려면 for문까지 계산해서 2 * n + 3번? 정도겠지만 알 게 뭐야
최고차항의 차수는 같으니 대충 n번이라고 생각하면 됩니다.
이렇게 "대충 n번 정도다" 를 "$O(n)$ 시간이 걸린다" 라고 말합니다.
마찬가지로 대충 $N^2$번 정도라면 $O(N^2)$, $N\times log_2 N$ 정도라면 $O(N log N)$이라고 쓰면 됩니다.
(보통 시간복잡도에서 로그의 밑은 생략합니다)
입력이나 데이터의 양이 얼마나 커지던 항상 실행 횟수가 같으면 $O(1)$ 시간 또는 상수 시간이라고 말합니다.
이처럼 코드의 속도를 잴 때는
입력에 따른 실행 횟수를 대충 식으로 나타낸 뒤
입력의 최대 크기를 식에 넣어 계산하면 됩니다.
백준에서 문제를 풀 때는 1초에 1억~10억개 정도의 문장이 실행된다고 생각하면 됩니다.
즉, 1번 코드는 n이 얼마나 커지든 1초 안에 무리없이 돌아가겠지만
2번 코드는 n이 억을 넘어간다면 1초가 넘게 걸릴 수도 있습니다.
보통 제한 시간은 1 ~ 2초이고, 출제자들은 정해보다 느린 풀이는 시간 초과를 내기 위해 제한을 딱 맞게 설정합니다. 즉 제한을 통해 정해의 시간복잡도를 유추할 수 있으며, 운 좋으면 풀이가 어떤 알고리즘인지도 감을 잡을 수 있습니다.
입력의 크기가 N일 때 주로 나오는 시간 복잡도를 정리해 보았습니다. 물론 절대적인 건 아니고 문제에 따라 다를 수 있습니다. 시간 복잡도별 자주 나오는 알고리즘은 이 글을 참고하세요.
| $N \leq 10^9 \sim 10^{18}$ | $O(1)$, $O(\log N)$ |
| $N \leq 1\,000\,000$ | $O(N \log N)$, $O(N)$ |
| $N \leq 100\,000 \sim 300\,000$ | $O(N \log N)$, $O(N)$, $O(N\sqrt{N})$ |
| $N \leq 1\,000 \sim 5\,000$ | $O(N^2)$, $O(N^2\log N^2)$ |
| $N \leq 100 \sim 300$ | $O(N^3)$ |
| $N \leq 15 \sim 20$ | $O(2^N)$, $O(N\times 2^N)$ |
| $N \leq 10$ | $O(2^N)$, $O(N\times 2^N)$, $O(N!)$ |
자세한 방법이 궁금하다면 '시간 복잡도'에 대해 공부해보는 걸 추천드립니다.
https://blog.naver.com/kks227/220769859177
빅오 표기법(Big-O notation), 시간복잡도, 공간복잡도
자료구조나 알고리즘에서 성능 측정의 가장 중요한 지표인 개념을 먼저 소개해드려야 할 것 같습니다. 그건...
blog.naver.com
왜 다들 C++을 쓰나요?
C++에는 스택, 큐, 우선순위 큐, 레드-블랙 트리, 정렬, 이분탐색, string 등
다양한 알고리즘/자료구조가 라이브러리에 구현되어 있어 편합니다.
또한 Python, Java 등의 언어보다 훨씬 빠르다는 장점도 있어 알고리즘 문제풀이에는 대부분 C++을 사용합니다.
1학년 프로그래밍 교과에서 함수를 배웠다고 들었는데, C언어로 반복문, 함수 등을 작성할 수 있으면 C언어로 코딩하면서 C++의 라이브러리만 가져다 쓴다는 느낌으로 C++을 사용해도 좋습니다.
물론 Python이나 Java 등을 사용해도 괜찮습니다.
맞았는데 왜 틀려요??
알고리즘 문제를 풀 때는 가능한 최악의 경우에도 문제없이 돌아가는 코드를 짜야 합니다.
흔히 하는 실수로는
- 길이가 최대 N인 문자열을 char str[N]; 과 같은 배열에 입력받으면 안 됩니다.
널 문자까지 고려하여 최대 N + 1칸이 필요합니다.
- scanf_s, gets_s 등 사용
scanf, gets를 사용해야 합니다. Visual Studio에서 오류가 난다면 이 블로그를 참고하세요.
- C언어의 Windows.h는 사용할 수 없으며, Numpy 등 Python의 내장 모듈이 아닌 것들도 사용할 수 없습니다.
- C, Java를 사용한다면 한순간이라도 int형의 최댓값을 넘지 않는지 확인해야 합니다. 대충 21억 정도입니다.
- 맞는 풀이 같은데 시간초과를 받았다면 빠른 입출력을 사용했는지 확인하세요.
- 0으로 나누는 경우가 생기지 않는지 생각해보세요.
- 그래도 모르겠다면 입력의 최솟값/최댓값 등 코너케이스에서 잘 작동하는지 확인해 보세요.
- 디버깅용으로 쓴 코드를 다 지웠는지 확인해 보세요.
- 그래도 모르겠다면 심호흡과 스트레칭을 하고 간절히 기도하며 코드를 꼼꼼히 체크해 보세요.
처음부터 코드를 다시 작성하는 것도 좋습니다.
이런 사태를 미연에 방지하기 위해서 머릿속으로 로직을 깔끔하게 정리하고 코딩을 시작하는 것도 좋은 방법입니다.
빠른 입출력이 뭔가욤
입출력은 매우매우 느려서, 입력이 아주 많은(대충 10000 ~ 100000개가 넘는 경우)에는 입력만 받아도 시간초과가 날 수 있습니다. 이런 경우에는 더 빠른 입출력을 사용해야 합니다. 분명 맞는 풀이인데 이상하게 시간초과를 받았다면 빠른 입출력을 사용했는지 확인해 보아야 합니다.
- C: 그냥 scanf, printf를 사용해도 됩니다.
- C++: 마찬가지로 scanf, printf를 써도 됩니다. iostream 헤더의 cin, cout을 쓰고 싶다면 main함수 맨 위에 ios::sync_with_stdio(0); cin.tie(nullptr); 을 적고 endl 대신 '\n'을 사용해야 합니다
- Java: BufferedReader, BufferedWriter를 사용하면 된다고 합니다.
- Python: 코드 맨 위에 import sys;input = sys.stdin.readline을 적어야 합니다.
기타 팁
- 이렇게 짜면 반복문이 정확히 T번 실행됩니다.
|
1
2
3
4
5
6
7
8
9
|
while (T--){
//asdf
}
while (T --> 0){
//이래도 됨
}
|
cs |
- 백준에서 컴파일 에러가 났다면 "컴파일 에러" 글씨를 눌러 에러 메세지를 볼 수 있습니다.
- Python에서는 a < b and b < c 를 a < b < c 처럼 쓸 수 있습니다.
- 문자열의 길이를 구할 때 strlen 함수는 O(문자열의 길이) 만큼의 시간이 걸립니다. 따라서
for (int i = 0; i < strlen(str); i++)
처럼 작성하면 안 되고, 길이를 for문 밖에서 미리 계산해야 합니다.
- 문제의 입력 제한을 보고 정해의 시간복잡도를 유추할 수 있습니다. 자세한 내용은 위 문단을 참고하세요.
- 배열의 값 모두를 특정한 값으로 채우고 싶을 때가 있습니다. 초기화할 값에 따라 여러 방법이 있습니다.
0. C++ vector의 경우: vector<int> v(n, x); 처럼 선언하면 크기가 n이고 모두 x로 채워진 vector가 생성됩니다.
1. 0으로 초기화하는 경우: main함수 밖에 전역 배열로 선언하거나 int arr[12345] = {0}; 처럼 선언하면 됩니다. 또는 아래 방법처럼 memset을 사용해도 됩니다.
2. -1으로 초기화하는 경우: <cstring> 헤더에 있는 memset 함수를 이용하면 됩니다. memset 함수는 memset(시작 주소, 값, 초기화할 크기) 의 형태로 사용합니다. 이 경우에는 memset(arr, -1, sizeof arr); 처럼 쓰면 arr이 몇 차원 배열이건 모두 -1로 채워집니다.
3. 매우 큰 값으로 초기화하는 경우: 매우 큰 값이 10억 정도로 충분하다면 역시 memset을 쓸 수 있습니다. int형 배열 arr을 초기화한다고 가정하면, memset(arr, 0x3f, sizeof arr); 처럼 쓰면 arr의 모든 값이 0x3f3f3f3f = 1,061,109,567으로 채워집니다.
※ memset 함수가 만능은 아닙니다. 가령 1, 2 같은 일반적인 값으로 배열을 채울 수는 없고, 위에서 언급한 경우는 memset이 원하는 대로 잘 작동하는 특이 케이스입니다. memset에 대해 자세히 알고 싶다면 이 글과 이 글을 참고하세요
- 생각보다 별로 팁이 없어요
- ㅎㅎ
- 읽어주셔서 감사합니다