Data Structure & Algorithm/코테 스터디 TIL

[99클럽 코테 스터디 5일차 TIL] 알고리즘 수업 - 너비 우선 탐색 1 - 백준 24444

어제는 DFS라서 혹시나 했더니 역시나 오늘은 BFS다. https://www.acmicpc.net/problem/24444오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다.아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다.정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다.정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 for each v ∈ V - {R} ..

[99클럽 코테 스터디 4일차 TIL] 알고리즘 수업 - 깊이 우선 탐색 1 - 백준 24479

오늘의 문제는 DFS이다. https://www.acmicpc.net/problem/24479오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다.정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다.정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 visited[R] 풀이 접근문제에서 이미 DFS 수도코드(Pseud..

[99클럽 코테 스터디 3일차 TIL] 입국심사 - 프로그래머스

코테 스터딜 3일차 문제는 프로그래머스의 입국심사 문제다.마참내 이분탐색 코드를 사용했다. https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krn명이 입국심사를 위해 줄을 서서 기다리고 있습니다.각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.처음에 모든 심사대는 비어있습니다.한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다.가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다.하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받..

[99클럽 코테 스터디 2일차 TIL] 징검다리 - 백준 11561

오늘의 문제는 백준 11561번 징검다리 문제로 키워드는 어제와 같은 이진탐색이다.하지만 오늘도 이진탐색 로직은 들어가지 않았다.ㅎ https://www.acmicpc.net/problem/11561승택이는 강을 건너려 한다.승택이는 수영을 못하기 때문에, 강에 놓인 징검다리를 밟고 건너갈 것이다.승택이는 이제 강의 한쪽 변 앞에 서 있다.강엔 1번부터 시작해 2번, 3번, ... , N번 징검다리가 차례대로 놓여 있다.물론 강 건너편으로 바로 점프하는 것도 가능하지만, 더 재미있게 강을 건너기 위해 승택이는 다음과 같은 규칙을 정했다.1. 첫 징검다리는 점프해서 아무 것이나 밟을 수 있다. 이 점프가 첫 점프이다.2. 두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.3...

[99클럽 코테 스터디 1일차 TIL] 게임 - 백준 1072

1일차 문제는 백준 1072번 게임이다.https://www.acmicpc.net/problem/1072게임 횟수 : X이긴 게임 : Y (Z%)Z는 형택이의 승률이고, 소수점은 버린다.예를 들어, X=53, Y=47이라면, Z=88이다.X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.[입력]각 줄에 정수 X와 Y가 주어진다.[출력]첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다.만약 Z가 절대 변하지 않는다면 -1을 출력한다.[제한]1 ≤ X ≤ 1,000,000,0000 ≤ Y ≤ X 오늘의 키워드는 이분 탐색이었는데, 사실 단순 수학 이론에 좀 더 가까운 문제라고 생각됐다.내가 이분 탐색을 제대로 이해하지 못하고 있는 걸 수도 ..