간타타 공부장 간타타 공부장

programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 1, 관심이 있는 정보는 어차피 skill 문자열에 있는 문자들이기 때문에 조사하고자 하는 문자열을 순회하여 skill에 있는 문자들만 뽑아내고 skill에 있는 인덱스를 벡터로 다시 만들어서 조사를 한다. 2, 벡터를 순회하면서 인덱스 숫자가 순차적으로 늘어나는지 확인한다. #include #include using namespace std; vector renewal(string skill, string search) { vector result; int str_size = search.size(); for (int i = 0; i < str_size; ..

programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 어떠한 사람들은 4차원 배열을 통하여 해결하였으나 나는 비트마스킹을 이용하여 문제를 해결하였다. 1, 해당 위치에서 이미 지나간 길의 정보를 저장하여야 하는데 map 이차원 배열에 해당 위치에서 위로 간 경우 1, 아래로 간 경우 2, 왼쪽으로 간 경우 4, 오른쪽으로 간 경우 8 을 저장하여 주고 & 연산자를 이용하여 지금 해당 위치에서 이동하려고 하는 길이 이미 지난 길인지 판별을 해 주웠다. *주의 할 점 - 지금 위치와 다음 위치 둘 다 이미 지나간 길에 대한 정보를 갱신 - 범위를 넘어 섰는지 확인 소스코드 #include #include usin..

programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 요즘은 dfs, bfs 단독으로 문제가 나오기 보다는 그래프 탐색을 이용하혀 한번 더 알고리즘 개념을 이용한 문제들이 종종 있는것을 볼 수 있다. 이번에는 그래프 탐색과 MST(최소비용 신장 트리) 개념을 합친 문제를 풀어 보았다. 나중에 프림스 알고리즘과 크루스칼 알고리즘에 대하여도 정리를 하여 포스팅을..

programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 생각보다 간단한 문제였는데 고민을 오래했다. *실패한 방법 O(n^2) 풀이법 1, 왼쪽 상단에서 오른쪽 하단으로 이어지는 대각선을 생각하였다.(어차피 대칭이므로 어느 선을 그어도 동일) 2, 정사각형의 왼쪽 하단과 오른쪽 상단의 점을 구한 후 두 점이 대각선의 아래에 있나 위에 있나 판별하여 갯수를 세어줌 => 결론은 시간초과와 약간의 실패 기록들..