[C++/백준] Solved.ac 2단계

[solved.ac 2단계 모음집]

https://www.acmicpc.net/group/workbook/view/20371/71152

 

알고리즘을 조금씩 꾸준히 풀면서 항상 기초가 부족하다고 느꼈다. 

일단, 새로운 유형의 알고리즘 유형을 봐도 외우지 않고 양치기로 해결하려고 하는 느낌이 있고, 

문법을 잘 몰라서 써칭해본적도 많다... 

 

그래서 좀 방향을 바꿔서 기본부터 차근차근 올라가기 위해서 solved.ac 2단계부터 6단계까지 모두 부수기를 진행하려고 한다..!! 

 

물론 그 과정에서 지켜야하는 몇 가지가 

매일 써칭하는 문법 ( cstring...애들... )은 찾아보고 정리 + 외워버리기

알고리즘 대표 유형 코드는 외우기. 툭 치면 툭 나와야한다. 

MST, 위상 행렬, 플로이드 워셜 같이 알고있는데 좀 생각해야 나오는 알고리즘들 다 외우기 

다른 사람들 코드를 최소 2개 참고하기 ( 쉬운 문제도 포함 ) 

 

 

2단계에서는 크게 헷갈리는 문제가 없을 것 같아서 무조건 20분 내로 풀어야 하는 걸로 잡았다. 

헷갈리는 개념만 정리하고 일요일에 외우도록 하는걸로. 

 

#include<algorithm> reverse(v.begin(), v.end()) 

주소값을 넣어서 사용할 수 있고, algorithm 헤더 파일임. 팰린드롬 풀면서 썼는데 cstring 내에 있는게 아니었음. 

문자열의 경우 주소값은 s.begin(), s.end()를 쓸 수 있고 (&s[0], &s[0]+ s.length()) 이렇게 가능함. 

주소로 접근하려고 &s, &s+len 이런식으로 했는데 오류가 났었음. :(

 

영화 감독 숌

https://www.acmicpc.net/problem/1436

실버 5 영화 감독 숌... 실버 5인데 못 풀어서 진짜 당황 스러웠다 ㅋㅋㅋㅋㅋ 결국엔 써칭으로 해결. 아무리 머리 쥐어짰어도 못 풀었을 거 같다. 

뭔가 DP나 이런 쪽으로 생각도 했는데 왠지 실버 5니까 DP는 아닐거 같고 무조건 완탐인데~ 했다. 

알고리즘 풀이나 시간 최적화 같은걸 너무 신경쓰다보니까 아예 숫자 666부터 계속 올라가면서 찾는다? 는 생각을 못하게 된 것. 

요즘 브루트 포스가 좀 약점인 거 같다. 요행 부리다가... 

-> 티어 낮은 문제를 많이 풀어봐야 겠다는 생각이 굉장히~~ 많이 든다!

나는 앞 뒤로 막 숫자를 붙이는 규칙을 찾아서 풀었는데 이렇게 하면 규칙 세우기가 상당히 까다롭다. 실제로 내가 했던건 나오지도 않았음. 

좀 더 단순하게도 생각할 줄 알아야하는데 ...

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<map>

using namespace std;

int N;
map<int, int> MAP;
vector <int> v;
int _sum[100];

void push_num(int next) {
	if (MAP[next])
		return;
	v.push_back(next);
	MAP[next] = 1;
}

int main() {
	cin >> N;
	int num = 666;
	int cnt = 1;
	while (cnt<N) {
		num++;
		string s_num = to_string(num);
		if (s_num.find("666") != -1) {
			cnt++;
			
		}
	}

	cout << num;
	
}

 

#include<string> string.find("find_string"!==-1)

string이 항상 약한데.. 문자열을 잘 안풀어서 그렇다. 

string.find("")!=-1 또는 string.find("")!=string::npos 이렇게 하면 그 내부에 있는지 없는지 확인할 수 있다. 없ㄷㅏ면 string::npos(=-1)을 리턴하는 것. 

찾았다면 시작 위치를 출력한다. 

 

랜선 자르기

https://www.acmicpc.net/problem/1654

투포인터 문제였다. 문제 접근 자체는 쉬웠는데, 몇 가지 놓쳐서 두 번 틀렸었다. (이전에 풀어본 듯?)

1. 길이 최대 값이 2^31-1 인데 int로 할당함 . 

2. s = 1에서 시작. s를 0에서 시작해서 division by zero가 발생했다. 이 오류를 보자마자 바로 잡긴 했는데 앞으로는 투포인터 문제에서 중간에 나누기가 들어가면 s를 0으로 하는 오류를 범하지 말자... 

 

 

통계학

https://www.acmicpc.net/problem/2108

간단한 산수 문제였다. 여기에 반올림이 나왔는데, 나는 코드로 구현했음. 하지만... cmath 메서드를 알았으면 더 좋았을 듯. 

#include<cmath>

• round() : 반올림
• floor() : 내림
• ceil() : 올림

자료형 변환 시키는 과정에서도 문제가 있었다. double(int/int) 이렇게 했기 때문에 이미 내부에서 int 연산이 일어났고, 소수점이 나오지 않은 것. 

(double)n/int 이런식으로 한 수에 double 형을 섞어주면 원하는대로 얻을 수 있다.