분류 전체보기 (124) 썸네일형 리스트형 라인 코테 후기 *코딩테스트 특성상 자세한 문제에 대한 설명을 추가 할 수 없습니다. 갖고있지도 않습니다.(문제 설명, 예제 등등) 서류전형 합격하고 코딩테스트에 참여했습니다. 알고리즘 2시간 휴식 20분 시스템 디자인 2시간으로 이어지는 긴 시험이었고, 결론부터 말하면 완전 망했습니다.😭 1교시 알고리즘은 총 4문제 120분간 진행되었고 문자열로 시작해서 문자열로 끝났습니다. 1번 문제 난이도가 높아봤자 코포 B번 정도 되는데 문자열문제라 구현에만 30분이 소요되었습니다. 2번도 쌩문자열이라 너무 지쳐 skip했고, 3번을 풀러 갔는데 풀이가 떠오르지 않았습니다. 3번 문제를 요약해 보자면... 어떤 식당이 있고 식당에는 출입자 명부가 있다. 이때 출입자 명부는 2가지가 있는데, 하나는 들어온 순서 다른 하나는 나간 .. 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. 이분탐색+슬라이딩윈도우 시험 중에는 이분탐색에 뭘 더하면 될 것 같은데 모르겠어서 포기했습니다. 시험 끝나고 화장실 갔다오는데 이분탐색 조.. 대규모 트래픽에 대응하는 시스템 디자인 최근 알고리즘 동아리 알파벳에서 서비스하고있는 깃허브 프로필 벳지에 대해 곰곰히 생각해보았습니다. 얼마 안되는 요청에 대해서는 아무 문제없이 잘 동작하겠지만, 대규모 요청에 대해서도 생각처럼 동작할까?라는 주제로 이런 저런 생각을 했습니다. 생각에 꼬리를 물고 여러 문제점들이 예상되었고, 적당한 대응방안이 나오긴 했지만 만족스럽지 않았습니다. 또한 제가 많이 부족하여 근본적인 해결책이 나오질 않았습니다. 오늘부터 이 글을 보고 차근차근 생각을 정리해보려 합니다. 당장 아기자기하고 예쁜 서비스를 제공하는 것 만큼이나 안정적이고 확장성있는 서비스를 제공하는 것도 중요하다고 생각합니다. 별 영양가도 없는 긴 글 읽어 주셔서 감사합니다. 정렬 정당성 증명 loop invariant를 이용한 정렬 알고리즘 정당성 증명 삽입 정렬 초기: arr[:1]은 정렬 되어 있다 유지: loop가 끝나면 arr[:i] 정렬되어있다. 종료: arr 정렬되어있다 버블 정렬 초기: arr[n-1:n] 정렬되어있다 유지: loop 끝나면 arr[i:n] 정렬되어있다 종료: arr 정렬 3273 두 수의 합 투포인터 정당성 증명 배열 arr이 정렬된 상태 int s = 0, e = n-1; for (int i = 0; i x임으로 .. BOJ 문제풀이 (W22) 10806 부분합 투포인터를 사용하여 답을 갱신해주면 됩니다. 다만 이 문제에서 중요한 점은 후에 따로 글로도 쓸 주제이지만 loop invariant입니다. 각각의 원소에 대해서 그 원소를 끝으로 할 때, 합이 s이상이 되게하는 가장 인덱스가 큰 시작지점을 찾아 주는 반복문을 하나 넣어 loop invariant를 설정하면 됩니다. while (start+1=s) { sum-=arr[start]; start++; } 1992 쿼드 트리 대표적인 분할정복 문제입니다. 주어진 배열을 4등분하여 분할정복을 돌아주면 됩니다. 인덱스 슬라이싱 할 때 거리를 따로 구해서 슬라이싱해야하는 점이 구현의 팁입니다. 17626 four squares 1개일때, 2개일때, 3개일때 까지는 그냥 반복문으로 처리해주면 됩니다.. codeforces R703 D2 0솔.... A. Shifting Stacks 구현 할 수 있을 것 같아서 그쪽으로 방향 잡았다가 전을 다 태웠습니다.😨(h가 무려 10억입니다...) 애초에 가장 작은 증가 수열을 크기라는 관찰은 문제 열리자마자 알아챘는데 여기서 prefix sum은 상상도 못했습니다. 그냥 i번 인덱스에서 그때의 누적합이 증가 수열의 최소 크기보다 작으면 false 이렇게 풀면 됩니다.😡 codeforces R702 D3 solved: 2 out of 7 A,B 삽질해서 2문제 푸는데 30분 걸렸습니다. C번은 전처리해서 배열로 만들기는 했는데 이후 접근법에 있어 투포인터를 사용하는 트롤링, 그대로 2솔하고 끝나버렸습니다.😭 투포인터가 N개 배열에서 가능한 두개를 모두 탐색하는게 아니라는 점을 계속 잊고 있는 것 같습니다. A. Dense Array 문제에서 친절하게 식을 줘서 그대로 구현하면 됩니다. $\frac{max\left ( a_{i}, a_{i+1} \right )}{min\left ( a_{i}, a_{i+1} \right )} > 2$ 인 경우 원소를 몇개 넣어야 하는지 카운팅해주면 해결 할 수 있습니다. 저는 이 부분을 구현하는데 시간을 소모했는데 어렵지는 않습니다 아래와 같이 쉽게 구현 할 수 있습니다... BOJ 문제풀이 (W21) 원래 AC를 받은 문제만 쓰려고 했는데, 그냥 일지처럼 쭉 적어 기록이라도 남겨야겠다는 생각이 들어 앞으로는 못푼 문제도 쓰려고 합니다. 18248 제야의 종 가까운 사람일수록 더 많은 종소리를 들을 수 있다는 관찰을 직접 하지는 못했고 도움을 받았습니다. 이후 종소리 들은 횟수가 감소하는 순으로 사람을 정렬시키고 i번째 사람(가까운)은 못 들었는데 i+1번째(먼) 사람이 들은 case가 있으면 false 이렇게 구현하면 해결 할 수 있습니다. 7569 토마토 아직 AC받지 못했습니다. 토마토 상자를 입력 받을때 kappa를 줘서 그래프를 쌓고 bfs를 돌려 그래프의 최장 거리를 구해줬는데 틀렸습니다. 이미 방문했지만 더 짧은 거리로 갈 수 있다면 이를 que에 넣어줘야 합니다. 이 부분을 추가하고 AC.. 이전 1 ··· 6 7 8 9 10 11 12 13 다음