'알고리즘'에 해당되는 글 319건

summary

• Find the edge that can be removed from a connected graph with n nodes and m edges to make it a tree.

approach

• Use a union-find data structure to keep track of connected components in the graph
• Iterate through the edges, and for each edge, check if the two nodes are in the same component
• If they are, then the edge is the redundant one
• Otherwise, union the two components.

complexity

• O(n + m log n) due to the union-find operations, where n is the number of nodes and m is the number of edges.

explain

• The solution uses a union-find data structure to keep track of connected components in the graph
• The union-find data structure is initialized with each node as its own component
• Then, for each edge, the solution checks if the two nodes are in the same component by calling the `disjoint` function
• If they are, then the edge is the redundant one, and the solution returns it
• Otherwise, the solution unions the two components by calling the `uf` function
• The `disjoint` function is used to find the root of a node, and the `uf` function is used to union two components.

Solution Code:

class Solution {
public:
    int uf[1001];
    int disjoint(int x){
        if(x == uf[x]) return x;
        return uf[x] = disjoint(uf[x]);
    }
    vector findRedundantConnection(vector>& edges) {
        for(int i = 0 ; i <= 1000; i++){
            uf[i] = i;
        }
        vector ans;
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            if(disjoint(a) != disjoint(b)){
                uf[disjoint(a)] = disjoint(b);
            } else{
                ans.push_back(a);
                ans.push_back(b);
            }
        }
        return ans;
    }
};

실수: 문자열의 길이가 1일경우를 생각하지 못해서 시간을 낭비.

시간 복잡도: O(N^2 +알파..?)

시간복잡도 계산이 잘 안된다. 

12번 라인과 17번 라인이 서로 의존적이다. 

n이1인경우 strncmp는 거의 연산비용이 들지 않게되고...

그렇다고 n을 N으로 키우면... 중간의 while(right < N) 반복문 접근수가 줄어든다.

잘 모르겠다.

입국심사.

처음엔 당황했지만.. 생각해보니 풀 수 있었다.

이분탐색 문제라는걸 몰랐으면 더 힘들었을 것 같다.

BFS 이용해서 풀었다.

크루스칼로 풀었다.

/**

실수:

disjoint함수의 두 a,b값이 다른 경우 uf[disjoint(a)] = disjoint(b); 최상위 번호를 찾아 넣어줘야하는데...

uf[a] = disjoint(b) 로 넣어주었다.. ㅠㅠ

이렇게 되면 두집합이 합쳐질때 최상위번호가 바뀌는게 아니라.. 중간쯔음에서 바뀌기 때문에... 집합 전체가 합쳐지지 않는다.

오히려 이건 가능하다.

uf[disjoint(a)] = b

b는 최상위가 아니여도... a의 최상위를 b로 바꿔주었기때문에.. disjoint 함수를 부르게되면 최상위 번호로 갱신된다.

**/

프로그래머스(programmers) N으로 표현

/**
1. 빼기와 나누기의 경우 순서가 바뀌는경우 결과값이 달라진다.
처음에 최적화를 한답시고, i/2+1 까지만 돌렸다가, WA를 받았다. 
이 점을 확인 한 후 i-1까지 돌렸다.

2. newN(222,333,44444) 의 숫자를 만들고.... 만들어야 하는 최종 숫자와 비교를 하지 않았다.
단순한 실수인데... 반례를 찾느라 한시간이 걸렸다. ㅜㅜ
구현 도중에도 검사해야겠다는 생각을 하지 않았다.;;;;;;;;;;;;
**/

1. 자료구조:

2. hash 함수: unsigned long getNameKey(char* name);

위와 같은 상황에서 이름의 hash값을 이용하여 gAllStudent에 있는 여러명의 학생 이름을 빠르게 찾을 때 한 실수다.

name1, name2 를 찾는다 했을때, getNameKey로 얻은 hash값을 nameKey1, nameKey2라고 하면

위와 같이 작성했다..

그런데.. hash값이기 때문에, name1, name2이름은 다르고 nameKey1과 nameKey2 가 같은 경우가 존재한다.

이런 경우 name2도 첫번째 if문만 들어가기때문에... 문제가 발생한다. 따라서 else if문을 if문으로 변경하여 가볍게 해결할 수있다.

위 실수를하여.. 원인 분석에 꽤 많은 시간이 들어 정리해 놓는다.

VS Code Problem Solving용 환경설정

작업 당시 운영체제: Ubuntu 18.04 64bit

VS Code를 활용하여 백준, 알고스팟, 코드 포스 등 여러 문제를 풀기위한 간단한 환경설정들이 검색해도 나오지 않아, 여기에 정리한다.

내가 VS 코드를 처음 설치하고 부딪힌 문제는 총 두개이다.

1. 어떻게 실행하지? -> Code Runner 이용

2. 인풋을 어떻게 입력하지? -> 설정 변경

1. VS Code 설치 : 생략

2. extension의 C/C++ 설치

   나는 C/C++ 를 사용하므로 해당 extension을 설치하였다.

3. code runner 설치

   빌드 및 실행하기 위한 code runner 설치

4. File -> preference -> setting에 들어 간 후

extensions -> Run Code configuration -> Run In Terminal checking!!!

5. 마우스 오른쪽 클릭, Run Code를 통해 실행

6. 터미널창에 입력이 가능한지 확인

VS Code를 사용하기위한 5분 설정 팁이다. Code Runner만 설치하여 사용할 시 output에 실행 결과가 나타나게 되는데, 이 output창에는 입력을 넣을 수가 없다.

따라서 PS를 위한 입력을 주기위해서는 위와 같은 세팅을 통해, 터미널에서 실행하는 것으로 변경 해야한다.

나도 시행착오 끝에 알아낸 방법인데, 

더 좋은 방법이 있다면 댓글로 정보 공유 부탁드립니다.  :D

못풀었다.

종만북 코드를 이해하고 책을 보지않고 따라해보았다.

leaf에서 leaf까지의 최대값과 leaf에서 root까지의 최대값의 최대값이 정답이 되는것으로 나눈것을 생각하지 못했다. 더 깊이 생각하는 습관을 가져야겠다.

트리 탐색시 다음노드들의 리턴값을 벡터에 저장하여 높이를 뽑아내는 패턴도 기억 해야겠다는 생각을 했다.

트리 탐색 기본 구조도 익혔고, 트리 생성 기본 구조도 익힐 수 있었다.

영역 구하기 응용문제였던 것 같다.

인접한 지역과의 차가 L이상 R 이하인 영역을 벡터에 담고,

담긴 벡터들 값의 평균을 구해 이동된 다음 맵을 만드는 방법을 선택했다.

때문에 맵을 map[50][50][2]형태로 선언하였고,  두맵을 번갈아 가며 사용하게된다.

 방문배열은 매번 초기화 하는 비용을 없애고 싶어서 int형으로 선언하여 이동한 날짜수를 기록해주었다.

사실 인접한 지역을 구하면서 sum값을 구하면 더 효율적인 코드게 되겠지만, 결국 시간복잡도에서는 차이가 없을 것 같아 편하게 답을 구하는쪽으로 코딩했다.