PS Study 1st Week

CDD·2023년 3월 22일

algorithm

목록 보기

1/2

Algorithm Study

어쩌다보니 부트캠프 내에서 스터디장을 맡게 되었다. 스터디를 만들게 된 이유는 소마 코테에서 좌절을 맛보기도 했고, 알고리즘에 대한 이해가 너무 부족해서 정말 단순한 문제들도 못풀 때도 많기 때문이었다. 교수님이 실제 코딩이 아닌 이론으로만 가르쳐줘서 코딩으로는 해 볼 생각을 안하고 있었는데, 4학년이 끝나서야 코테 공부를 시작하다니 기분이 처참해졌다. ~~컴공을 졸업해놓고 실버 문제 따위에서 해매고 있다니,~~ 이러한 부끄러운 모습을 개선하기 위해 스터디를 시작했고, 시작하자마자 좌절이었다.

Python to JS

사실 이때까지 python으로만 알고리즘 문제를 풀다보니 입출력을 받거나 배열을 구현하는 데 있어 아무런 어려움이 없었기에 문제를 몰랐다. 이번 스터디원들이 모두 js를 사용하여 알고리즘 스터디를 진행하길 원하기도 했고, 인터넷에 찾아보니 가끔 js로만 코테를 보는 곳도 있다고 해서 '나도 이 참에 JS로 문제나 풀어볼까?' 싶어서 반강제로(?) 팀원들의 언어를 JS로 고정시켰다. 나름 여러 언어들을 해왔으니 구현은 쉽겠다 싶었다, 알고리즘은 문제 해결력이 중요한거니 언어가 뭐가 문제인가 싶기도 했다. 그렇게 문제가 선정되었고, 꽤 쉬워보이는 문제들이었기에 자신감 있게 풀이에 들어갔으나 생각보다 어떻게 구현해야 할 지 감이 잡히지 않았다.

'파이썬으로는 이렇게 했는데, 이거 JS로는 어떻게 풀지?' 라는 생각이 자꾸 반복되면서 어쩔 수 없이 인터넷을 뒤져야 했다. 양심 상 풀이를 뒤지기는 그렇고 모르는 함수에 대해서 서칭을 했는데, 하면 할수록 끝이 없어서 결국 문제들을 다 풀지 못했다. 그래서 조만간 map() 함수와 같은 array 계열 함수에 대해 좀 공부를 하면서 이 곳에 포스팅을 해야겠다는 생각이 들었다.

아, 그리고 readline 모듈에 대해 학습하려고 했으나 뒤늦게 시작한 탓에 시간이 많이 모자라서 백준 문제를 풀지 못했다. 다음주 내로 재빨리 학습해서 주어진 모든 문제를 풀 수 있도록 해봐야겠다.

PS

완주하지 못한 선수

function solution(participant, completion) {
    participant.sort();
    completion.sort();
    
    for(var i = 0; i < participant.length; i++) {
        if(participant[i] != completion[i]){
            return participant[i];
        }
    }
}

이 문제는 간단했는데, 시간 초과 에러 때문에 약간의 애를 먹었다. 2단 루프문을 통해 처음에 결과를 구현했었는데, 테스트 케이스 시간 초과가 떠서 코드를 수정했다. 이름들이 participant, completion으로 주어지기에 미리 오름차순으로 배열해놓고 양 쪽 index 내의 값을 비교해가며 다른 결과가 나오면 곧바로 리턴하는 방식이다.

카펫

function solution(brown, yellow) {
  const answer = [];
  const carpet_size = brown + yellow; // 넓이

  for (let height = 3; height <= carpet_size / height; height++) {
    var width = Math.floor(carpet_size / height);
    if ((height - 2) * (width - 2) === yellow) {
      return [width, height];
    }
  }
}

이 문제를 해결하기 위해서는 격자무늬 구조에 대한 이해가 필요하다. 격자무늬 내의 모든 값을 더하면 넓이가 나오는 구조이고 그렇기에 처음부터 넓이의 값은 주어져있다. 이를 carpet_size로 선언해줬고, 여기에 최소 높이인 3부터 순차적으로 나눠져가며 제일 바깥 테두리 부분을 제외한 넓이가 노란색과 일치하는지에 대한 조건, if ((height - 2) * (width - 2) === yellow)으로 코드를 완성시켰다.

신고 결과 받기

function solution(id_list, report, k) {
  const answer = new Array(id_list.length);
  answer.fill(0);
  const report_list = {};

  id_list.map((user) => {
    report_list[user] = [];
  });

  report.map((user) => {
    const [user_id, report_id] = user.split(" ");
    if (!report_list[report_id].includes(user_id)) {
      report_list[report_id].push(user_id);
    }
  });

  for (const key in report_list) {
    if (report_list[key].length >= k) {
      report_list[key].map((user) => {
        answer[id_list.indexOf(user)] += 1;
      });
    }
  }
  return answer;
}

사실 이 문제를 풀 때가 제일 난감했는데, 머릿 속에 떠오른 구현을 어떻게 처리할지 고민이 많았다. 그렇게 수차례 시도하다가 결과값이 이상하게 나와서 타인의 문제풀이를 참고했다. answer에 0을 채워 [0, 0, 0, 0]과 같은 형태로 만들어주고, 마지막에 처리 결과를 담아주는 식으로 구현했다. id_list에서 map() 함수를 이용하여 user, 즉 key 값을 설정해주고 value는 빈 배열 형태로 구성한다. report에서 map 함수는 인자로 받아온 report 배열에서 신고를 한 사람과 당한 사람을 따로 저장하고, if (!report_list[report_id].includes(user_id)를 통해 중복 확인을 해준다. 중복이 아닐 경우 report_list의 report_id에 해당되는 키 값에 user_id라는 value 값을 push 해준다. 마지막 루프문은 value의 길이를 세 몇 명의 사람에게 신고를 당했는지 확인해주는 방식이다.

바이러스

import sys
from collections import deque


def BFS(V):
    queue = deque([V])
    visited_BFS[V] = 1
    count = 0
    while queue:
        V = queue.popleft()
        for i in range(computerCount):
            if linkedList[V][i] == 1 and visited_BFS[i] == 0:
                queue.append(i)
                visited_BFS[i] = 1
                count += 1
    print(count)


computerCount = int(input())
link = int(input())
linkedList = [[0 for _ in range(computerCount)]
              for _ in range(computerCount)]
visited_BFS = [0] * (computerCount)

for i in range(link):
    x, y = map(int, sys.stdin.readline().split())
    linkedList[x-1][y-1] = linkedList[y-1][x-1] = 1

BFS(0)

computerCount로 컴퓨터의 개수를 입력받고, linkedList 배열을 이용하여 각 인덱스마다 [0, 0, 0, 0 ...]의 형식으로 채워준다. 이렇게 하는 이유는 이어지는 경우를 체크하기 위해서이다. 방문 확인을 위한 visited_BFS 배열도 만들어주고, 반복문으로 이어지는 점들을 입력 받아 linkedList 배열의 해당 인덱스에 1로 표시해준다.

# 1번 컴퓨터가 2, 4번 컴퓨터에 연결 되어 있는 linkedList 구조
[[0, 1, 0, 1, 0 ...], ...]

그리고 나서 깊이 우선 탐색으로 들어가는 데 초기 인자를 0으로 넘겨준 이유는 1번부터 탐색을 시작하기에 그렇게 넘겨줬다. queue를 만들어 준 후에 [0] : 1번 컴퓨터의 visited 값을 1로 바꿔주고, queue가 끝날 때까지 반복하여 순회한다. for loop 안에 있는 조건문을 보면 queue에서 popleft된 값과 이어진 부분을 검사하는 조건과 방문 여부를 확인할 수 있는 조건 이렇게 총 2개로 이뤄져있다. 그렇게 선정된 i는 queue에 append되고, 탐색 카운팅이 올라가는 구조로 되어있다.

사실 비슷한 류의 BFS, DFS를 몇 문제 풀어봤지만 JS로 시도하다가 실패했다. JS에 대해 더 열심히 공부해봐야겠다.

CDD

다음 포스트