퇴사맨이 쓰러지지 않는 개발블로그

파이썬으로 코테를 준비하는 사람들은 대개 'deque' 를 활용하여 bfs를 구현할 것이다.deque를 활용하면 큐에 노드를 넣어주고 빼주는 과정이 굉장히 빨라지기 때문에, 시간복잡도를 해결하기 위한 가장 기본적이면서도 강력한 방법으로 사용되고 있다. 사용 방법은 다음과 같다 (at 파이썬)from collections import deque // deque 임포트 받기q = deque() // 노드를 넣고 빼줄 큐 생성q.append() // 노드 넣어주기q.popleft() // 노드 빼주기, 큐에 들어있는 노드 중 가장 먼저 넣어준 노드를 빼줌// 일반적으로 노드를 빼주는 것은 O(n)의 시간복잡도를 가지나, deque를 활용해 생성한 큐에서// popleft를 활용해 빼준다면 O(1)의 시간복잡도..

프로그래밍/코테 준비 2024. 7. 7. 22:47

.js로 코딩테스트를 칠 일이 생겨 급하게 입출력을 공부했다.조금 복잡하기 때문에 따로 정리해두고 나중에 또 확인하면 좋을 것 같아서 글을 쓴다. 자바스크립트로 입력을 받는 방식엔 크게 두가지의 케이스가 있다고 볼 수 있다.첫째, 파일로 받기둘째, 콘솔로 직접 입력받기 이번 게시글에서는 콘솔로 입력받기를 정리할 예정이다. 콘솔로 입력받기란? 흔히 vs code같은 ide에서 bash창을 통해 직접 입력값을 넣어주는 케이스를 말한다. 방법1. 기본 골격const readline = require('readline');const rl = readline.createInterface({ input: process.stdin, output: process.stdout,});let num = 0;let nu..

프로그래밍/코테 준비 2024. 6. 28. 14:06

문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오. 접근N에서 시작하여 K에 도달하는 경우 중 최단 이동거리를 만족하는 경우를 체크하면 되는 문제이다.BFS를 이용하면 K에 도달하는 경우를 최초로 발견한 시점이 곧 최단 이동..

프로그래밍/코테 준비 2024. 6. 25. 14:20

위상정렬 알고리즘이란 우선순위가 정해져있는 작업을 처리할 때, 해당 작업의 순서를 결정해주기 위한 알고리즘이다. 대학의 수강신청을 예를 들어보자. 과목 1, 2, 3, 4, 5가 있다. 3번 과목을 듣기 위해선 4번 과목을, 5번 과목을 듣기 위해선 1번 과목을 사전에 들을 필요가 있다.(선수과목) 이 경우 다음 과 같이 표현할 수 있다. 4 -> 3 1 -> 5 전체 순서를 구했을 때, 4번이 3번보다 앞에 있어야 하고, 1번이 5번보다 앞에 있어야 한다. 조건이 적을 경우 간단히 생각하는 것 만으로도 순서를 구할 수 있다. 위의 예시의 경우 1번과 4번을 앞에 적어주고 2, 3, 5번을 뒤에 적어주는 식으로(ex: 1 4 2 3 5) 답을 출력할 수 있다. 그러나 조건이 많아진다면 위와 같은 단순한 ..

프로그래밍/코테 준비 2024. 3. 3. 18:12

LCA 알고리즘이란? 2개의 노드가 주어질 경우, 해당 노드들의 공통된 조상 중 가장 깊이가 깊은 노드를 조회하는 알고리즘이다. 대략적인 순서는 다음과 같다. 1. 모든 노드에 대해 깊이를 계산한다. 2. 최소 공통 조상을 조회할 두개의 노드를 확인한다. 3. 해당 노드들의 깊이를 똑같이 맞춰준다. 4. 부모 노드를 한단계씩 거슬러 올라간다. 5. 하나의 노드에서 만날 때 나온 값 출력 코드는 다음과 같다. (백준 11437 문제 참고) import sys # 깊이 계산 함수 def dfs(node, depth): check_nod[node] = 1 depth_nod[node] = depth for i in tree_nod[node]: if check_nod[i] == 1: continue parent_..

프로그래밍/코테 준비 2024. 2. 29. 01:57

15311 약팔기 문제 요약: 연속된 부분의 합을 통해 1 ~ 1000000까지의 수를 모두 표현할 수 있는 길이 2000의 리스트를 만들면 되는 문제. 모든 수를 표현한다는 것 -> 자릿수의 개념으로 접근. 우리가 일상적으로 사용하는 10진법을 보면 1 ~ 9까지의 수, 그리고 10 ~ 90까지의 수를 이용해 1 ~ 100까지의 수를 나타내고 있다. 이를 표현하면 다음과 같다. 10 10 10 10 10 10 10 10 10 10 / 1 1 1 1 1 1 1 1 1 왼쪽의 10이 10의 자릿수, 오른쪽의 1이 1의 자릿수라고 생각하면 편하다. 가운데 /를 기준으로 수를 도출할 수 있다. 가령 98이라는 수를 도출하고 싶다면, 10의 자릿수 9개와 1의 자릿수 8개를 골라 연속된 부분으로 만들어 출력하면..

프로그래밍/코테 준비 2024. 2. 27. 09:49

문제:재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다. 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... , 10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ... 총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라. 입력: 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다..

프로그래밍/코테 준비 2023. 11. 5. 23:19

트리는 그래프의 일종으로, 여러 개의 노드와 간선으로 이루어져 있다. 트리의 가장 위에 존재하는 노드를 '루트 노드'라고 부르며, 다른 모든 노드는 루트 노드로부터 얼마나 떨어져있는지에 따라 깊이라는 개념으로 표현할 수 있다. 백준 1991번 문제를 한번 풀어보자 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGF..

프로그래밍/코테 준비 2023. 4. 12. 01:32