전체 글 (124) 썸네일형 리스트형 BOJ 문제풀이(W24) 2098 외판원 순회 2617 구슬찾기 구슬의 대소관계를 이용하여 그래프를 만들고, 이를 탐색하여 문제를 해결했습니다. 1번 구슬이 2번 구슬보다 무겁다면 1에서 2로 가는 간선을 그어주고 각각의 구슬에 대해 dfs를 돌려 그 구슬보다 무거운 구슬의 숫자를 셌습니다. 9009 피보나치 어떤 정수에서 그 정수보다 작은 피보나치 수열 중 가장 큰 피보나치수를 하나씩 빼주면서 문제를 해결했습니다. 5582 공통 부분 문자열 dp[i][j] := s[i]=t[j]이면서 이를 끝으로 하는 최대 공통 부분 문자열의 길이 이렇게 배열을 정의하면 쉽게 해결 할 수 있습니다. 주어진 두 문자열의 길이가 4,000이라 시간안에 풀 수 있습니다. 9251 LCS 최장 공통 부분 수열을 찾아주는 문제입니다. 수열을 찾아주는 .. BOJ 문제풀이(W23) 7578 공장 구간합을 구하는 문제로 치환되는 순간 매우 편해집니다. 포인트는 문제를 구간합을 구하는 문제로 치환하기와 쿼리에서 요구하는 인덱스를 구하는 부분입니다. 기계가 교차하는 조건을 생각해보면 첫번째 포인트를 잡을 수 있습니다. $i b_{a_{j}}$이면 교차합니다. 그러니까 j를 1부터 n까지 돌면서 j~N까지 구간의 합을 구해주면 문제를 해결 할 수 있습니다. 이때 배열을 전부 0으로 초기화시켜주고 j를 하나씩 돌면서 기계를 연결시키면서 배열의 해당 인덱스를 1로 만들어줍니다. 이 부분에서 배열 A의 값이 배열 B의 몇번째 인덱스와 일치하는지를 찾아주는것은 이분탐색을 통해 구현했습니다. 2096 내려가기 메모리 제한이 4MB입니다. N이 10만이라 입력이 30만개인데 int형이 8byte이니.. 소프트웨어 마에스트로 1차 코테 후기 진짜 금방 막 시험이 끝났습니다. 알고리즘 올솔하려고 시험친건데 느낌상 3솔이라 이럴줄 알았으면 sql이랑 web문제를 먼저 풀 걸 이라는 후회가 남습니다. 아무튼 시작 A. DFS 그냥 dfs돌려서 leaf찾아주고 각 리프의 부모를 쭉 출력해주면 됩니다. 다만 출력을 주어진 간선 순으로 하라는데 이게 구현이 더 어려웠습니다. 저는 그냥 역순 놓고 제출했습니다.(당연히 간선순으로 출력 안나왔습니다😅) B. Two pointer 각 배열마다 투포인터를 이용하여 주어진 시간이하의 가장 큰 값을 찾아주면 됩니다. $O(N^2)$ 정도 시간으로 잘 돌아갈 것 같습니다. C. 이분탐색+슬라이딩윈도우 시험 중에는 이분탐색에 뭘 더하면 될 것 같은데 모르겠어서 포기했습니다. 시험 끝나고 화장실 갔다오는데 이분탐색 조.. 이전 1 ··· 25 26 27 28 29 30 31 ··· 42 다음