꺼진불도다시보자

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 이분탐색은 보통 정렬되어 있는 숫자를 이용한다. 이분탐색을 이용해 찾아야할 값은 뭘까? distance의 범위가 100,000,000까지였기 때문에, distance를 가지고 이분탐색을 해야한다는 직감이 들었지만, 이분탐색으로 뭘 찾아야할 지, left와 right로 이동하는 기준이 뭐가 되야하는 지 알지 못했다. 결과적으로 여기서 이분탐색을 이용해 찾아야하는 숫자는 거리의 최솟값 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/1843 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 dp문제인 걸 알고 풀어도, 어떤 데이터를 dp 테이블에 저장해야할 지 모르면 말짱 꽝이다. 처음엔 지난 번에 했던 방법대로 possible_set을 만들어서 해결하면 될 것 같다는 생각을 했지만, 먹히지 않았다. 해결법은 다음과 같았다. 1. 2차원 dp테이블 2개 이용한다(mindp, maxdp). 2. 괄호의 개수를 늘려가면서 2차원 dp테이블에 값을 저장한다. 3. dptabl..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43164# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 dfs로 풀 수 있었다. 가장 고민했던 부분은 알파벳 순서가 낮은 경로를 통해야만 전 경로를 돌 수 있는 경우였다. 이것을 어떻게 처리해야할 지 감이 안잡혔다. dfs로 하면 될 거 같긴한데, 자꾸 에러가 나서 gpt에게 여쭤봤다. 코드가 간결하고 명확햇다. dfs를 돌면서 원소를 pop해버리면 경로가 온전히 저장되지 않을 거라고 생각했는데, dfs에 대한 오해가 있었다. 어차피 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42861#qna 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 kruskal을 사용했다. kruskal 알고리즘은 다음과 같이 구현한다. 그래프를 weight 오름차순으로 정렬하고, weight가 작은 순서대로 edge를 추가한다. 이 때, edge의 각 vertice가 두 개의 sub set을 cross하는 지를 알아야한다. 만약, 같은 subset에 있다면, 그 edge는 MST(minimum spanning tree)에 포함되지 않..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42883# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 .. 코드 #include #include #include #include using namespace std; //k가 1000000이고 number가 1000000이면, //시간 내에 불가능. -> 중첩 불가 //만약 k가 4라면, //처음 올 숫자는 앞에서 5개 중에 가장 큰 수. //두 번 째로 올 숫자는 앞에서 선택된 숫자 자르고 나서 //남은 k+1개 중 가장 큰 수. ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 through GPT.. 코드 #include #include #include #include #define MAX 1000000000 using namespace std; long long solution(int n, vector times) { long long answer = 0; long long left = 0; long long right = *max_element(tim..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 시간 내에 풀 수 있는 방법이 도저히 생각나지 않아서 GPT에게 물어봤다. 코드를 보고 놀랐다. 처음 보는 접근방식이었다. 2차원 배열 dp를 이용해 풀 수 있을까 생각해봤지만, 그 방법이 떠오르지 않았는데 코드를 보고 이마를 한 대 쳤다. n이 8번 가는 동안, 그 사이 만들어진 수식들을 저장한다. 다음 i번째에는 i-j와 j 번째 배열에 있는 수식들을 이용해 i번째 possibl..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 2차원 배열을 쓰려고 생각해봤는데, 시간복잡도가 안될 거 같았다. 그래서 linked list를 사용해서 풀었다. 노드 1을 먼저 큐에 담고, bfs방식으로 그래프를 탐색했다. 탐색하면서, visit배열에 1로부터의 거리를 저장했다. 코드 #include #include #include #include #include using namespace std; class node { pu..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 count를 전역변수로 설정하고, 방문횟수마다 +1을 해서 tree에 저장했다. 이렇게 하면, 각 노드의 자식 노드 개수를 구할 수 있다. 코드 #include #include #include #include using namespace std; vector dict = {'A', 'E', 'I', 'O', 'U'}; map tree; int count = 1; void make_t..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 input size가 100이다. 100!인 경우 절대 시간 내에 풀 수 없으므로, 전과는 다른 방법을 사용해야 했다. 송전탑의 개수를 세기 위해서 dfs를 써야하나, bfs를 써야하나 고민했는데, 문제에 설명되어있듯이 트리를 사용하면 쉽게 풀린다. f함수에서는 wires에서 하나를 삭제하고, 그에 해당하는 그래프를 find에 넘겨준다. find에서 연결되어있는 송전탑의 개수를 리턴..