[기초다지기] 백준 문제집으로 시작하기

어떻게 시작하면 좋을까, 알고리즘?

 코딩은 좀 해봤는데 뭔가 기초가 부족한 것 같기도 하고, 기초를 다지고는 싶은데 어떻게 시작해야될지는 모르겠고..  나름 알고리즘을 공부한다고 백준 알고리즘을 주제별로는 풀어본 적은 있어도 기초부터 차근차근 풀어본 적은 없었다. 항상 과제할 때도 그렇고 프로젝트 할 때도 그렇고 그때그때 함수라든가 함수의 특징을 찾아 쓰기 때문에 찾은거 또 찾고 또 찾고.. 약간 자괴감드는 행동만 하는 것 같아서 이번에는 아주 쉬운 것부터 진행하기로 했다. 구글링 안해도 바로바로 코딩할 수 있도록!

 그래서 서칭해본 결과 백준 문제집에  단계별로 풀어보기라는 아주 좋은 edition이 있었다! 개인적으로 문제집은 푼 만큼 파란 게이지바가 올라가는 희열감이 좋아 문제집으로 진행했다. (｀▽´)

단계별로 풀어보기 에디션

 오늘은 총 15문제를 풀었는데 막상 기초만 계속 풀라고 하니 지겨운 감이 있어 중간중간 쉬면서 진행하기로.. 이 포스터에는 푼 문제 중 노트해놔야 맘 편히 발 뻗고 잘 수 있을 문제들만 메모해놓도록 하겠다.

(코드들은 꼭 풀어보고 참고하세요. c++)

 

---

 

11719번: 그대로 출력하기 2

이 문제에서는 내가 맨날 찾는 getline() 함수에 대해 한번 정리하고 가겠다.

getline 함수는 한 줄을 읽어주고 문자열에 저장해주는 친구다.

getline() 함수에는 두가지 종류가 있다는 사실을 꼭 집고 넘어가야 한다. 

1. cin.getline()

iostream 라이브러리에 있는 cin.getline(char* a, streamsize n, char delim);

a 문자열
n 저장할 문자의 최대 개수
delim 해당 문자에 도달하면 직전 문자까지만 가지고 온다. (delim 인자는 optional)

2. getline()

string 라이브러리에 있는 getline(istream& i, string& s, char delim);

i 입력스트림 오브젝트 (보통 cin을 집어넣으면 된다)
s 저장할 string 
delim 해당 문자에 도달하면 직전 문자까지만 가지고 온다. (delim 인자는 optional)

 

 일단 이렇게 해서 풀긴 풀었는데... 영 찝찝한 감이 있다. 문제는 이렇게 나와있다.

그대로 출력하기2 문제

음.... 입력이 최대 100줄로 되어있다는 말은 입력값이 4줄이면 4줄만 입력받아서 출력하고 싶은데 어떻게 해야될지 모른다는 것이다! getline()함수는 buffer에 저장된 string을 가지고 온다. 그니까 만약에 다음줄에 입력값이 더 없으면 계속 마지막 줄을 가지고 온다는 ...

 그래서 만약에 for문이나 while문으로 getline함수를 100번 반복하고 위의 예제 입력값을 넣어주면 5번 줄부터는 Online Judge가 들어가기 때문에 입력값의 마지막 줄은 100번을 채울 때까지 계속 출력된다는 이야기다!

    Hello

Baekjoon
   Online Judge
   Online Judge
   Online Judge
.
.
.

 근데 sublime text3 에디터를 쓰는 나로썬 이 코드가 틀린 것이 분명한데 밑의 코드로 제출하면 성공으로 채점된다.. 영 찝찝하단 말이지.. 

코드

#include <iostream>
#include <string>

using namespace std; 

int main(){ 

	string a; 
	int count = 0; 

	while(count < 100){ 
		getline(cin, a); 
		cout << a <<endl; 
		count++; 
	} 

	return 0; 
}

 

 

---

 

10430번: 나머지

 이 문제는 진짜 간단한 문제인데, 여기서 집고 넘어갈 점은 연산자 우선순위!

적어도 이 문제를 보면 %과 + 혹은 * 중에 어떤게 우선인지는 알 수 있다. (%이 우선) 근데 웬만하면 그냥 가로() 사용해서 입력하자.. 이런데서 실수하면 찾기도 힘들다. （´＿｀）

우선순위 테이블

연산자 우선순위 테이블

 

코드

#include <iostream>

using namespace std;

int main(){

	int a, b, c;
	cin >> a >> b >> c;
	cout<< (a+b)%c <<endl;
	cout<< (a%c + b%c)%c <<endl;
	cout<< (a*b)%c <<endl;
	cout<< (a%c * b%c)%c <<endl;

	return 0;
}

 

---

 

15552번: 빠른 A+B

 이번 문제는 문제보자마자 으잉? ( ﾟoﾟ) 했던 문제이다. 이 문제는 진짜 초보자들을 위한 팁을 모아놨다고 해야하나... 알고리즘 공부 그리고 코딩을 하기 위해서는 기본적으로 이 정도는 알아야한다는 이야기들을 써놨다. 그래서 여기서는 그 글들 중에 내가 알아야 할 것들, 내가 몰랐던 것들을 정리해보았다. 웬만하면 밑에 링크 들어가서 직접 보는 것이 최고!

15552 문제의 문제

 

> https://www.acmicpc.net/blog/view/55

BOJ 101

 

> https://www.acmicpc.net/blog/view/70

자주 틀리는 요인

cin/ cout 사용할 때 cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 개행문자(\n)를 쓰자. 

 이게 무슨 소리인고 하니 구글링을 진행했다. cin/cout의 속도가 scanf/printf 에 비해 느리다는 것이다. 또한 endl도 \n 보다 느리다는 것이다. 뭐, 입출력 관련해서 분명히 속도에 관한 이야기가 나오겠거니 했지만, 이 문제는 꼭 한번 집고 넘어가는 것이 좋겠다. 

 '아인스트라세의 소프트웨어 블로그'에 아주 잘 설명되어 있어 말을 빌리자면 시간초과가 난 문제들은 입력값의 수가 100만개 이상이었다는 것이다.  그래서 이제의 입출력이 100만까지 인가보다. 자세한 내용은 링크 들어가서 직접 읽어보세요!

> https://eine.tistory.com/entry/CC-%EC%9E%85%EC%B6%9C%EB%A0%A5-%EB%B0%A9%EB%B2%95%EC%97%90-%EB%94%B0%EB%A5%B8-%EC%86%8D%EB%8F%84-%EC%A0%95%EB%A6%AC

C/C++ 입출력 방법에 따른 속도 정리

NULL 문자는 하나의 문자로 취급된다. NULL문자와 공백은 엄연히 다른 것.

각 테스트 케이스마다 초기화시켜주기.

오버플로우는 항상 조심하기.

float보다 double 사용하기.   float는 사실 유의미한 사용이 불가하므로 웬만하면 double 사용하기.

char 배열에 길이 N의 문자열을 담으려면 널문자까지 담아야하므로 배열의 크기는 N+1이 되어야 한다.

전역 배열의 크기는 넉넉하게 잡기. 만약 10000 크기의 수열이 필요하다고 할 때 int a[10023] 처럼 실제보다 조금 더 잡는 것이 좋다.

a <= b <= c 는 a <= b && b <= c 가 아니라 (a<=b) <= c 이다.

 

---

 

11720번: 숫자의 합

 여기서는 char to int에 대해서 알아보자. 일단 아스키코드(ASCII Code)라는 것을 다들 알 것이다. 아스키 코드란 컴퓨터가 정보를 저장할 때 숫자로 모두 저장하는데 특정 문자, 숫자, 기호에 대해 0부터 127까지의 수를 이용해서 저장하는 인코딩 방식을 말한다.

 우리가 살펴볼 char to int 의 방법 중 하나가 이 아스키 코드를 이용하는 것이다. string에 저장된 각 char는 숫자 0을 48로 저장한다. 그러므로 int()를 씌어준 값에 48만 빼면 우리가 원하는 int값이 나온다는 것이다. 

 아스키 코드 테이블

아스키코드

코드

#include <iostream>

using namespace std;

int main(){

	int n;
	cin >> n;

	string a;
	cin >> a;

	int x = 0;
	for(int i=0; i< n; i++){
		int num = int(a[i])-48;
		x += num;
	}

	cout << x;

	return 0;
}

 

-

2019.07.07 AM 12:12

이렇게 해서 알고리즘 첫 포스팅이 끝났는데... 이거 나중에 복잡한 문제 풀 때는 포스터 쓰는 시간 장난 아니겠는데?