eunno-an / programmers

프로그래머스 문제 풀이

👋 Hi

꾸준히, 방향에 맞게 하면 안될건 없어

• 🌱 I’m currently learning Algorithm, Programmers level3

programmers's Issues

DFS와 BFS의 성능 차이

경주로 문제의 DFS해법과 BFS해법 중
DFS는 시간 초과가 나고, BFS는 통과??

코파일럿

..

Pq custom function

Pq쓸때 커스텀 함수 쓸때
struct compare {
bool operator()(Job* A, Job* B) {
if (A->jobType == B->jobType)
return A->t1 < B->t1;
return A->jobType < B->jobType;
}
};
void printJobs(vector<Job*> jobs) {
}
vector solution(vector arr, vector processes) {
vector answer;
queue<Job*> Jobs;
queue<Job*> working;
priority_queue<Job*, vector<Job*>, compare > waiting; // 작업 queue
이런식으로 선언하자.

Skt 2차 코테풀때
Illegal instruction에러뜬 코드
bool compare(Job* A, Job* B) {
if (A->jobType == B->jobType)
return A->t1 < B->t1;
return A->jobType < B->jobType;
}
void printJobs(vector<Job*> jobs) {
}
vector solution(vector arr, vector processes) {
vector answer;
queue<Job*> Jobs;
queue<Job*> working;
priority_queue<Job*, vector<Job*>, decltype(&compare) > waiting; // 작업 queue

set의 요소 접근

set.rbegin() = set의 끝 요소를 나타내는 이터레이터

함수 사용시 얕은 복사와 깊은 복사 시간 차이

https://programmers.co.kr/learn/courses/30/lessons/43164#qna

여기서 dfs의 함수 매개변수 중 adj_list와 useTicket에 &를 붙이냐 안붙이냐에 따라 시간이 두배정도 차이난다.
(deep copy : 300 ms, shallow copy : 600ms)

만약 큰 변수들을 복사할 때 함수 로직에 지장이 없다면 deep copy를 이용하는게 시간, 공간 효율성 측면에서 유용하다.

lower_bound, upper_bound

vector A = { 1, 3, 7, 9 };
int B = 10;
cout << upper_bound(A.begin(), A.end(), B) - A.begin() << '\n'; // 4
cout << upper_bound(A.begin(), A.end(), 0) - A.begin() << '\n'; // 0
cout << upper_bound(A.begin(), A.end(), 1) - A.begin() << '\n'; // 1

cout << lower_bound(A.begin(), A.end(), B) - A.begin() << '\n'; // 4
cout << lower_bound(A.begin(), A.end(), 0) - A.begin() << '\n'; // 0
cout << lower_bound(A.begin(), A.end(), 1) - A.begin() << '\n'; // 0

이 gcd는 음수에 대해서도 잘 작동하는가?

long long gcd(long long a, long long b) {
if (b == 0) return 1;
return gcd(b, a % b);
}
long long lca(long long a, long long b) {
return a * b / gcd(a, b);
}
ㅇㅇ 잘 작동함.

vector에서 max 찾기

프로그래머스 레벨 3 스티커 떼기 문제에서 다른 사람 풀이를 보다가 찾음.
*max_element(v.begin() ,v.end());
algorithm 헤더에 존재한다.

auto it 사용과 관련한 이슈

Programmers Level3 베스트 앨범 문제를 해결하던 중, 값 정렬이 안되는 문제 발생.
for (auto it : streaming) sort(it.second.begin(), it.second.end(), compare);