Algorithm/프로그래머스

[프로그래머스 level 3] 네트워크 (C++)

BFS 또는 DFS로 풀 수 있는 문제이다. 위 그래프는 2개로 나눌 수 있다. 위 그래프는 하나로 연결된 하나의 그래프이다. 모든 노드는 BFS 탐색의 시작점이 될 수 있다. BFS를 통해 방문한 노드는 방문 기록을 남기게 되고, 시작점이 되지 못한다. 시작점이 없을 때까지 BFS를 수행하고, 문제의 답은 BFS를 수행한 횟수가 된다. 개인적으로 이 문제를 비롯한 기본 bfs, dfs문제들이 왜 level 3인지 이해가 되지 않는다. 최종 코드 #include #include #include using namespace std; vector adj[201]; bool visited[201]; void bfs(int start){ queue que; que.push(start); visited[start..

[프로그래머스 level 3] 가장 먼 노드 (C++)

다익스트라 문제 시작노드는 1번으로 고정되어 있고, 간선 사이의 거리는 항상 1로 고정되어 있다. 일반적인 다익스트라 풀이와 거의 동일하다. 하지만 1번 노드에서 가장 멀리 떨어진 노드의 거리가 최댓값으로 갱신될 때마다 답을 1로 초기화 시켜야 한다. ex 우선순위 큐에 1번 노드가 있다. 가장 먼저 2번 노드에 방문하면 1번 노드와의 최대 거리가 1로 갱신이 되고, 가장 멀리 떨어진 노드의 수는 1이 된다. 그리고 3번 노드에 방문하면 1번 노드와의 거리가 1이므로 현재 최댓값인 1과 동일하다. 따라서 가장 멀리 떨어진 노드의 수는 2로 갱신이 된다. 동일한 방법으로 4, 5, 6번 노드에 방문하면 최대 거리가 2로 갱신이 되고, 가장 멀리 떨어진 노드의 수는 3이 될 것이다. 최종 코드 #includ..

[프로그래머스 level 3] 표편집 (C++)

카카오 2021 인턴 삽입, 삭제의 시간이 O(1)이거나 O(logn)이면 풀 수 있을 것 같았다. (알고보니 이동시간이 더 중요했다) log시간을 쓰려면 세그먼트 트리를 써야 할 것 같아서 너무 복잡해질게 예상되어서 그쪽으로는 시도하지 않았다. 예전에 백준에서 풀었던 'AC'문제랑 비슷하다고 생각했다. 그리고 학교 자료구조 시간에 리스트 과제 문제와 비슷했다. 처음에 리스트를 사용해 푸는 거라고 생각해서 List STL을 사용해서 시도해 보았다. STL에 있는 List는 삽입, 삭제는 O(1)이지만, 문제의 'U', 'D', 'Z' 명령어를 처리할 수가 없었다. 키 포인트 Z를 수행하기 위해서는 삭제된 행의 순서를 스택에 입력해 놓아야 한다. C는 리스트에서 값을 지우는 척만 하고 실제로 지워서는 안 ..

[프로그래머스 level 3] 입국심사(C++)

이분 탐색을 어떻게 사용해야할 지 떠올리기 정말 힘들었던 문제이다. 그리고 오버플로우도 주의해야 한다. n times return 6 [7, 10] 28 입출력 예 설명 가장 첫 두 사람은 바로 심사를 받으러 갑니다. 7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다. 10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다. 14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다. 20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다. 이분 탐색을 하려면 특정 값의 low와 high를 정해야 한다. 이 문제에서 특정..

[프로그래머스 level 3] 추석 트래픽 (Python)

문제에서 주어진 그림 덕분에 해결방법을 바로 떠올릴 수 있었다. 우선 문자열로 주어진 시간을 파싱해서 초단위로 모두 바꾼다. -> 문자열 파싱 때문에 Python 을 사용했다 그리고 위 그림처럼 시작 시간과 종료 시간을 튜플로 묶어서 리스트에 넣는다. (시간 구간을 원소로 하는 리스트 생성) 구간의 시작시간에 대해 오름차순 정렬한다. 구간 리스트를 순회하면서 구간을 우선순위 큐에 삽입한다. 우선순위 큐는 구간의 종료 시점에 대해 오름차순 정렬되어 있다. {구간의 시작 시간 - 1초} 값이 우선순위 큐의 top 원소의 종료 시간보다 같거나 크다면 1초 구간 내에 없다는 뜻이므로 우선순위 큐의 top 원소를 pop 한다. 따라서 우선순위 큐에 원소가 있다면 다들 1초 간격 내에 존재하는 구간인 것이다. 매 ..

[프로그래머스 level2] 프렌즈4블록 (C++)

카카오 코딩테스트 [1차] 문제 2차원 배열의 원소가 떨어지는걸 구현하는게 핵심인 구현 문제이다. 문제에서 구현할 부분이 확실하게 나눠져 있음을 확인했다. 2x2 블록을 모두 찾아서 지우기 지워진 블록 떨어뜨리기 2x2블록을 찾아서 삭제하는 부분이다. bool deleteBoard(){ int del = 0; for(int r = 0; r < N; r++){ for(int c = 0; c < M; c++){ if(!board_records[r][c]) continue; del += delete2x2(nboard[r][c], r, c); } } for(int r = 0; r < N; r++){ for(int c = 0; c < M; c++){ if(board_records[r][c] == 2){ board..

[프로그래머스 level2] 피로도 (C++)

현재 피로도에 따라서 최대로 탐험할 수 있는 던전의 수를 구하는 문제이다. 던전 탐험에 필요한 피로도가 2차원 배열로 주어지고, 던전 탐험 순서에 따라서 탐험할 수 있는 던전의 개수가 달라질 수 있으므로 백트래킹을 사용한 완전 탐색으로 구현했다. 매 dfs 호출마다 지금까지 탐험한 던전의 최대 갯수를 갱신해준다. (cnt는 매개변수로 가지고 있다.) answer = max(answer, cnt); 현재 던전에서 다음 던전으로 이동하는 부분이다. 주의할 점은 다음 던전으로 이동하기 위해서 현재 피로도가 다음 던전에 필요한 피로도보다 많아야 한다는 점이다. for(int i = 0; i < dungeons.size(); i++){ if(visited[i]) continue; if(nowHp < dungeon..

[프로그래머스 level2] H-index (C++)

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 위 말을 이해하기가 어려울 수 있다. h번 이상 인용된 논문이 h편 이상이다 -> 이 문장의 뜻은 h는 과학자가 발표한 논문의 개수 이하가 될 것이다. 예시를 보면서 이해해 보자. 논문의 인용 횟수 [3, 0, 6, 1, 5] 가 주어진다. 먼저 논문을 오름차순 정렬한다. [0, 1, 3, 5, 6] 여기서 2회 이상 인용된 논문은 3, 5, 6 논문이 되고, 2회 이하 인용된 논문은 0, 1 논문이 된다. 3회 이상 인용된 논문은 3, 5, 6 논문이 되고, 3회 이하 인용된 논문은 0, 1, 3 논문이 된다. 배열이 정렬 되었기 때문에 lo..

[프로그래머스] 다리를 지나는 트럭(C++) level2

Queue를 사용하는 문제이다. 문제에서 주어진 대로 트럭이 다리를 지나가는 과정을 구현하면 된다. 현재 차례의 트럭이 다리의 최대 무게 때문에 못 지나가는 경우, 무게가 0인 트럭을 지나가게 하도록 대체 할 수 있다. 핵심 while 문 내부 코드 분석 if(weightSum + now_weight

[프로그래머스] level2 순위 검색 (Python)

입력이 50,000이고, 쿼리가 100,000이다. 쿼리가 10만이라서 쿼리에 대한 답은 log 시간복잡도가 필요할거라고 감을 잡았다. 그리고 "java backend junior pizza 150" 위와 같은 문자열이 들어오면 - and - and - and - 1000 - and - and - and pizza 1000 - and - and junior and - 1000 ... 이러한 쿼리의 답에 모두 속하게 된다 그래서 각 info마다 어떤 쿼리의 답이 될 지 모르기 때문에 모든 쿼리에 대한 경우의 수를 모두 구해야겠다고 생각했다. _info = [i.split(' ') for i in info] _query = [] for q in query: a = q.split(' and ') la = a[..