Java 코딩테스트 교재 49~53번

이번엔 Discord에서 했습니다.

49

50 (나의 발표)

Q. 이 코드는 왜 있나요?

        if (x != y) {
            parent[y] = x;
        }

A.사용되는 함수를 살펴보겠습니다. find 함수, union 함수

static int find(int x) {
        if (x == parent[x]) {
            return x;
        } else {
            return parent[x] = find(parent[x]);
        }
    }

    static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            parent[y] = x;
        }

find 함수에서 if (x == parent[x]):

이 if 문이 없다면, find 함수는 무한 루프에 빠질 가능성이 있습니다. 왜냐하면 각 집합의 대표(루트 노드)를 찾는 과정에서, 자기 자신이 대표인 경우를 확인하지 않고 계속해서 부모 노드를 찾으려 시도하게 될 것이기 때문입니다. 따라서 이 if 문은 무한 루프를 방지하는 중요한 역할을 합니다.

union 함수에서 if (x != y):

이 if 문이 없다면, 이미 같은 집합에 속해있는 두 원소를 또 다시 합치려는 시도를 하게 됩니다. 이렇게 되면 프로그램의 성능이 저하되고, 불필요한 연산이 추가됩니다. 따라서 이 if 문은 불필요한 연산을 줄이고 프로그램의 효율성을 높이는 역할을 합니다.
따라서, 이 if 문들은 프로그램이 정확하고 효율적으로 동작하도록 하는 데 필수적입니다.

-> 왜 여기에 if 처리를 했는 지에 대한 이야기를 했다.

51

-> 그래프와 트리에 대한 이야기를 했다.

52

-> 트리 구현 중, 이 트리가 바이너리/일반 트리인지에 대한 이야기를 좀 더 나눴다. Testcase의 경우 바이너리라는 가정을 깔고 진행해서 통과했지만, 그렇지 않을 경우 조건을 넣어주자는 점을 이야기 했다.

53

이번주의 merge issue

다른 분께서 어떤 class를 사용하시다가 계속 빨간 줄이 떠 버전을 변경하셨다고 하셨다.

내 .idea 폴더 내의 xml 파일 2개가 충돌이 나서 우선 내 파일을 지우고 PR 했더니 IntelliJ에서 안 열리는 이슈가 있었다.

해결

그래서 .idea 폴더 내의 내용을 지운 후 다시 merge해주셨고, 잘 돌아갔다.

앞으로 .gitignore을 사용해주시기로 했다.