Beelog

programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자 programmers.co.kr 문제는 위와 같으며, 이 문제는 문자를 1개씩 반복하는 경우, 2개씩 반복하는 경우, ... n개씩 반복하는 경우를 순차적으로 모두 확인하면서 기준 문자와 다음 문자가 같은 경우 수를 증가시키고 다른 경우는 지금까지 구한 기준 문자와 그 수를 저장한 뒤 기준 문자를 다음 문자로 변경하는 방식으로 모든 반복 경우를 확인한 뒤, 그때마다 구해진 문자열의 길이를 비교해 최소 ..

programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이 programmers.co.kr 문제는 위와 같으며 큐를 사용하여 문제를 풀 수 있습니다. 다리를 하나의 큐라고 생각하고 각 경우를 확인하며 트럭이 다리를 건널 수 있도록 하였습니다. 먼저 다리로 사용할 큐를 생성한 뒤, 트럭의 수만큼 반복을 진행합니다. 이는 모든 트럭이 다리 위로 올라갈 때까지 반복하는 것입니다. 이후 각 트럭에 대해서 아래와 같은 조건을 확인합니다. CASE 1. 다리가..

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제는 위와 같으며, 일반적인 BFS 문제에 벽을 부수는 경우가 추가된 것입니다. 따라서 단순히 해당 위치를 방문했는지 여부를 확인하는 visited 배열을 [0, 0] 으로 만들어서 [벽을 부수지 않고 해당 위치를 방문한 경우 지나온 칸 수, 벽을 부수고 해당 위치를 방문한 경우 지나온 칸 수] 를 저장하는 형태로 생성합니다. 그리고 큐에 데이터를 저장할 때 [현재 위치의 x, 현재 ..

www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제는 위와 같으며, BFS 를 통해 문제를 풀 수 있습니다. 먼저 이 문제는 BFS 를 수행하는데 연결이 끝나려면 최종적으로는 사이클이 만들어져야 한다는 것입니다. 1 => 3 => 3 2 => 1 => 3 => 3 3 => 3 4 => 7 => 6 => 4 5 => 3 => 3 또한, 이미 1부터 시작하여 3을 확인하고 3이 사이클을 이룬다는 것을 확인한 뒤에는 2를 확인한 경우도 1까지 확인한 경우와 뒷부분 사..

www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제는 위와 같고, Deque 를 사용하여 BFS 를 구현하는데 최단 거리를 구할 수 있는 지점을 알아야 하므로 방문했는지 확인하는 visited 배열을 boolean 형식이 아닌 int 형으로 만들어서 해당 인덱스에 이전에 방문했던 위치값을 넣는 방식으로 구현하였습니다. 파이썬 코드는 다음과 같습니다. from sys import stdin from collections im..