PS/알고리즘 문제풀이 처음 시작하기(1) - 알고리즘 사이트 입문

알고리즘 문제풀이를 제대로 시작한 지 1년도 안된 초보지만, 그래도 누군가의 시작을 도울 만큼만은 알고 있다고 생각해서 글을 썼다

요즘 기업의 입사테스트에서 알고리즘 코딩 테스트는 거의 필수이고 대회도 많이 열리기 때문에 그 중요성만은 잘 알고 있으리라 생각한다

신입생이라면 술자리에서 선배들이 알고리즘의 중요성과 족같음을 여러 번 언급했을 테니..

하지만 생각보다 내 주위에는 알고리즘 중요한 거 너무 많이 들었고 해야 된다고 생각은 하는데, 그래서 어떻게 시작해야 되는데?를 모르는 사람이 너무 많았다 아직까지도

과거에 아무것도 몰랐던 내가 헤맸던 것을 위주로 글을 써보려고 한다

 

가장 접근성이 좋으면서 유명한 사이트는 백준 온라인 저지 BOJ(https://www.acmicpc.net/) 인데

Baekjoon Online Judge

난이도별 문제도 굉장히 많고 기업의 코딩 테스트 등이 실시간으로 복구가 잘 돼서 올라오는 편이라서 굉장히 추천하는 사이트이다

이외의 사이트들은 코드업, 코드포스, 정올, 프로그래머스, 코드 그라운드 등이 있다

 

 

하지만 백준 사이트는 아무런 기반 없이는 초반 접근이 좀 힘들다

가장 큰 이유는 문제 분류가 잘 되어있지 않기 때문(알고리즘 별로는 잘 되어있지만 난이도 순으로는 보기 힘들다)

 

그래서 추천하는 문제집으로는

단계별로 풀어보기 jh05013 Edition pt.1(입출력 사칙연산 루프 배열 BF 재귀 수학적 사고 정렬 소수 스택 큐 덱 DP)

: https://www.acmicpc.net/workbook/view/1946

별찍기(for문 응용) : https://www.acmicpc.net/workbook/view/20

 

이 두 문제집 문제들을 위에서부터 차례대로 풀어보면 좋을 것 같다.

 

이러한 문제들을 푸는것을 Problem Solving(PS)라고 하는데, PS를 처음 시작할 때 꼭 당부하는 것들이 있다.

 

1. 사용 언어는 ⭐C++⭐이 좋다

알고리즘 테스트들에서 지원하는 주 언어는 C/C++/Java가 대표적이고 요즘에는 파이썬도 지원하는 추세지만 시작을 하지 않았고 어떤 언어를 쓸 지 고민이라면 C++을 무조건 추천한다.

 

① 많은 풀이,자료들이 C 문법으로 되어있다

-> 문제를 풀다보면 성공한 문제일 때 남이 어떻게 풀었는지 참고하는 게 도움이 될때가 많은데, 대부분의 고수들 그리고 '좋은 알고리즘'으로 작성된 풀이들은 C++로 구현된 경우가 많기 때문에 언어가 다르면 참고하기 어렵다

 

② C에 비해 stl과 라이브러리 지원이 매우 잘 되어있음

-> 언어 입문을 C로 한 사람들이 많겠지만, PS를 할 때 매우매우매우 많이 사용되는 stl인 큐, 스택, 정렬, 초기화, 벡터 등은 C++에서만 쓸 수 있다. C를 쓴다면 문제를 풀 때마다 직접 구현을 해야된다는 점... 그렇기에 자료구조에 대해 완벽한 이해를 끝냈다면 그냥 stl을 쓰자

 

③ 속도와 직관성 면에서 C++이 최강

-> java는 객체지향언어이기 때문에 직관성이 떨어진다. 풀다보면 속도가 정말 중요하구나를 느끼기때문에 C++을 쓰는게 좋다

 

2. 꼭 C++의 문법을 쓸 필요는 없다

C++을 쓰래놓고 C++문법을 안써도 된다는건 이상하게 들릴수도 있지만, C++에서 대표적인 문법인 입출력 cin/cout은 입출력 속도가 굉장히 느린 편이다(다음 편에서 설명)

그렇기때문에 자기가 손에 익은대로 C와 C++ 문법을 적절히 섞어서 활용하자

나같은 경우는 헤더파일은 C++로, 코드는 대체적으로 C로 쓰는 편이다

 

 

그래서 이제 문제를 직접! 풀기위해 vscode(or visual studio)를 켰다면 백준의 대표적인 문제 A+B를 풀어보도록 하자

PS를 처음 하는 사람들에게 맛보기로 이 문제를 풀라고 시키면 자주 하는 실수들이 있다

이 코드의 문제가 뭔지 알겠나요....?

문제는 바로 이 부분이다

3. 입력 조건은 코드로 작성할 필요가 없다

PS를 시작하지 않고 교내 알고리즘 대회를 풀 때 내가 자주하던 뻘짓이었는데, 그것은 바로 입력에서 주어진 입력 조건을 코드에 직접 명시해주는 것이었다

물론 이건 소프트웨어공학 측면에서 봤을때는 정말 잘하고 있는 것이지만.... PS할 때는 전혀 도움이 안 된다

입력 조건에 명시되어있는 조건들은

'테스트 케이스는 이런 조건에 맞추어서 입력될 것이니까 그 범위 내에서 잘 동작하게 코딩하세요'임을 명심!!

 

대신 입력조건에서 잘 봐야하는 부분들이 있다.

BOJ 10757번: : 큰 수 A+B

이 문제는 위의 문제와 같아보이지만 전~~~~혀 다른 문제이다

아무 생각없이 이 문제를 똑같은 코드로 제출하면 당연히 틀린다

A와 B는 int형의 범위인 –2,147,483,648 ~ 2,147,483,647 를 훨씬 초과하기 때문에 이 문제는 A와 B를 그대로 자료형에 저장하는 것이 아닌, 덧셈 알고리즘 자체를 직접 구현해서 풀어야 하는 문제이다.

이 외에도 입력의 개수가 많을 경우 이를 배열에 저장하는 경우가 많은데, 배열의 크기를 잘 생각해서 여유있게 선언해주도록 하자

 

정리하자면 입력을 받을 때는

① 입력의 범위에 맞는 자료형 사용(큰 수일때 주로 long long형)

② 입력의 개수에 맞는 배열 크기 선언

이 두 가지를 꼭!!! 유의하자

 

추가로, 문제를 풀다보면

이런식으로 짜는 사람들도 있는데.....

4. 입출력은 꼭 조건에 맞도록 코딩한다

지켜주자....

띄어쓰기랑 줄바꿈도 예제 그대로 입력/출력 되어야 한다

예제 입력 옆의 복사를 눌러서 터미널에 붙여넣으면 예제 출력 그대로 출력되어야 하는거다

 

5. 예제는 예제일 뿐

예제에 나와있는 테스트케이스는 단순 예일 뿐

채점서버의 공개되지 않은 테스트케이스의 양은 매우 많다

그러니까 예제에 나와있는 테스트케이스만 해보고 바로 제출하기 보다는 입출력 조건의 최소/최대에 해당하는 예제를 직접 만들어서 테스트해보는 습관을 가지자

 

6. 안풀리는 문제는 계속 붙잡고 있지말고 풀이를 찾아보자😊

문제를 푸는 양이 늘어감에 따라서 PS를 할 때 모르는 부분이 점점 없어지겠지만, 처음에 문제를 풀 때 막히는 부분이 있다면 그 문제는 당신이 모르는 방법/라이브러리를 사용해서 해결이 되는 문제인 경우가 있을것이다

그러니까 모르는 문제가 있다면 몇날며칠 붙잡고 있지 말고 구글링을 해서라도 풀이를 확인하고 다시 풀어보자

 

 

 

이번 포스팅에서는 문제를 풀기 전 알고있으면 좋은 팁들을 적어봤는데

다음 포스팅에서는 실제로 코딩을 할 때 알아야 할 팁들을 써볼것이다!!!

**이 포스팅은 충북대학교 소프트웨어학과 알고리즘 동아리 샘마루의 알고리즘 세미나 강의자료를 참고해서 작성했습니다