느낀점

  • 알고리즘이 어렵지는 않다
  • 전반적으로 손이 많이 가는 문제들이 많았던것 같다.
  • 라인 코테 특성상, 히든 테케가 많이 주어져서
    • 히든 테케를 얼마나 많이 맞췄는지가 관건이 될것같다.
    • 합격선을 감히 예측하자면 2솔~3솔 사이?
  • 꼼꼼하게 히든테케 풀었다면 2솔도 기대해볼만 하다.
  • 이번 시험에서 불리했던 사람은, 다양한 알고리즘을 공부했던 사람들
    • 하지만, 이런 유형의 시험은 어떻게 준비할 수가 없다.
    • 단 하나 있다면, 시간 정해놓고 코테 환경에 노출시키는것

코딩테스트 구성

  • 1차 : 알고리즘을 푸는 문제이고 총 4문제가 나왔고, 2시간 내에 풀어야한다.
  • 2차 : 복잡한 문제를 하나주고 점점 조건을 추가하는 문제로, 코드의 퀄리티를 확인

1차 1번

  • 단순 구현 문제
  • 문자열을 파싱해서, 주어진 로직에 따라 순회하며 최대값을 구하는 문제
  • 일단, 데이터 크기가 작아서 알고리즘 생각할것 없이
  • 따라서 구현만 해주면 된다.
  • 근데 꽤 복잡해서 시간을 꽤 많이 쓴것 같다.

1차 2번

  • 단순 구현 문제
  • 문자열에서 특정 조건을 찾아주는 문제로
  • 구현이 조금 복잡해서 시간을 오래 사용했다.

1차 3번

  • 사실 시간이 부족해서 풀지는 못했다
  • 그리디하게 항상 최악의 조건을 가정해서 푸는 문제

1차 4번

  • DFS 문제로 계속 깊게 들어가서 앞선 부모노드를 일정 규칙에 따라 출력해주는 문제
  • DFS 중에, 부모노드를 각각 잘 저장해놓으면 문제 없었을것 같다.
  • 단 마지막에, 정렬기준에 맞게 정렬해주는 문제가 좀 까다로웠다.

2차

  • 복잡한 문제를 하나주고 점점 조건을 추가하는 문제
  • 점점 기능이 확장되기 때문에, 인터페이스를 사용해서 클래스의 구현을 다르게 하면 될것같은데..
  • 시간내에 클래스까지 만들진 못했고, 정답을 맞추는것을 목표로, 그리고 코드의 퀄리티를 목표로 깔끔하게 나누기만 했다.

총평

  • 라인과 함꼐 2021 상반기가 시작되었다.
  • 1차 코테는 알고리즘 자체가 어렵진 않고, 복잡한 구현을 시간을 얼마나 잘 사용하는것이 관건.
  • 2차 코테는 구현하는 과정에서 코드의 복잡도를 줄이는 문제..
    • 2차를 준비하려면, 구현을 많이 해보고 누군가 코드리뷰를 해줘야할것 같은데..
    • 학부생 수준에서 너무 힘든것이 아닐까..

문제링크 : https://leetcode.com/problems/container-with-most-water/


문제 추상화

  • 물을 담을때 가장 많이 담기는 크기 구하기
  • 물이 담긴다 >> 두 막대중 더 작은것 * 두 막대의 거리
  • 둘다 높아야되고, 사이가 멀어야함

아이디어

  • 브루트포스 접근 : 각 막대에 대해서 모든 막대를 탐색해보자
    • 시간복잡도 : O(N^2) > 1e10 > 시간초과
  • 시간복잡도 줄일수 있는방법
    • 이진탐색? > 정렬하고 있지 않아서 불가
    • DP? > 이전 값을 재활용 할 수가 없음
    • 투포인터? > 전체에서 가장 큰 값을 찾아야함
      • st, en이 왼쪽에서 시작? > st, en을 움직이는 조건이 어려움
      • st은 왼쪽에서, en은 오른쪽에서 시작
        • 둘중에 작은 값을 움직이면 됨 > 이렇게 해보자
  • 투포인터 st 왼쪽에서, en 오른쪽에서
    • 최대값을 갱신해줌
    • 둘중에 더 작은값이 이동
    • 최대값 리턴

시간복잡도 계산

  • 투포인터 순회 : O(N)

자료구조

  • 막대 높이 : int[N]
    • 막대 최대높이 : 1e4 > INT 가능
  • 투포인터 최대값 : 1e4 * 1e5 > 1e9 > INT 가능

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public:
        int maxArea(vector<int>& height) {
            int st = 0;
            int en = height.size()-1;
 
            int maxv = 0;
            while(st!=en) {
                int area = min(height[st], height[en]) * (en-st);
                maxv = max(maxv, area);
 
                // 더 작은값을 움직이자
                // 같을때 어떤 값을 움직이냐가 차이가 있을까? > 없을 듯
                if(height[st] > height[en]) en--;
                else st++;
            }
 
        return maxv;
    }
};
cs

문제유형

  • Two pointer - 배열 순회
    • N^2 를 N에 푸는 방법
    • 어떤 연산값을 구해야할때, 순차적으로 구해야하는 경우

문제링크 : https://www.acmicpc.net/problem/7453


아이디어

  • 접근 1. 배열 4개를 모든 경우의수로 더할경우
    • O(N^4) : 4000^4 > 시간초과
  • 접근 2. 두개씩 더해서 이진탐색 사용 가능할까?
    • 두개씩 더한다음
    • 한개만 정렬을 해줌
    • 그다음 각각 더해서 0이되는 수를 찾기
    • 0이 되는 여러개가 있을 수 있잖아 > 마지막에 같으면 여러개 구하기
    • 시간복잡도
      • 두개씩 곱함 : N^2 * 2
      • 한개 정렬 : N^2 * lgN^2
      • 모든 수에대해 더해서 0이되는 수를 이진탐색으로 찾기 : N^2 * lgN^2
      • 더해서 0이 되는거 여러개 있을경우, 계속 더해주기 : N
      • 총합 : O(N^2 * 2 + N^2 * lgN^2 + N*2 * lgN^2 * N) = O(N^3 * lgN^2) = 64e9 * 20 > 시간초과
  • 접근 3. 두개씩 더해서 투포인터 사용
    • 두개씩 더한 다음 모두 정렬
    • 각각의 배열에서 하나는 왼쪽(st)부터, 하나는 오른쪽(en)부터 시작해서 더해서 0이되는값 찾기
      • 더해서 0이 될경우, 각각 값이 같은 수 구해서 곱하기
      • 이떄, 더해서 0이될경우, 포인터 넘어가므로 O(N) 사용할 필요없음
    • 더해서 0보다 작을경우 st++, 클경우 en--

시간복잡도 계산

  • 두개 더한다음 정렬 : N^2 * 2 + N^2*lgN^2 * 2
  • 투포인터 수행 : N^2 * 2
  • 총합 : O(N^22 + N^2lgN^22 + N^22) = O(N^2*lgN^2)

자료구조

  • A,B,C,D 배열
    • 최대값 : 2^28 > INT 가능
  • 두개씩 더해준 값 : AB, CD
    • 최대값 : 2^29 > INT 가능
  • 합이 0이되는 쌍의 개수
    • 4000^4 > long long 사용

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
int A[4010];
int B[4010];
int C[4010];
int D[4010];
int AB[16000010];
int CD[16000010];
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    
    // 두개씩 더하기
    int k=0;
    for(int j=0; j<n; j++) {
        for(int i=0; i<n; i++) {
            AB[k] = A[j] + B[i];
            CD[k] = C[j] + D[i];
            k++;
        }
    }
    
    // 정렬
    sort(AB, AB+k);
    sort(CD, CD+k);
    
    ll cnt=0;
 
    int st = 0;
    int en = k-1;
    
    while(st <k && en >=0) {
        int sumv =AB[st] + CD[en];
        if(sumv == 0) {
            // 두개가 같은게 여러개 있을 수 있음
            // 같은 값을 곱해서 더해주기
            int originSt = st;
            int sameSt = 0;
            while(AB[st] + CD[en] == 0) {
                sameSt++;
                st++;
                if(st==k) break;
            }
           
            int sameEn = 0;
            while(AB[originSt] + CD[en] == 0) {
                sameEn++;
                en--;
                if(en<0) break;
            }
            cnt += sameSt * sameEn;
        } else if(sumv < 0) {
            st++;
        } else {
            en--;
        }
    }
    
    cout << cnt << '\n';
    return 0;
}
 
cs

문제유형

  • Two pointer - 두 배열의 pointer
    • 두배열의 합이나 곱으로 모든 경우의 수를 따져야할때
    • 양쪽에서 st, en놓고 올라가고 줄어드는 방법
    • 이때 조심해야할것 : 배열이 같은 값이 중복될 수 있음
    • 이떄 중복되는것 계산해줘야함

'알고리즘 > 백준' 카테고리의 다른 글

백준 18233 민준이와 마산 그리고 건우  (0) 2021.04.20
백준 1238 파티  (0) 2021.04.20
백준 2581 소수  (0) 2021.03.18
백준 12865 평범한 배낭  (0) 2021.03.18
백준 8983 사냥꾼  (0) 2021.03.18

+ Recent posts

티스토리툴바