Algorithm 102

[Algorithm] 서로 다른 두 범위가 겹치는지 확인하기

개요다음과 같이 두 개의 범위가 있다고 할 때,├───A───┤ ├───B───┤두 범위에 서로 겹치는 부분이 있는지, 없는지 판단하고 싶다. 간단한 방법이 있는지 알아본다.   경우의 수서로 다른 두 개의 범위가 위치할 수 있는 경우의 수부터 알아보자. 1. 범위 A의 최댓값이 범위 B의 최솟값보다 작은 경우max(A) ├───A───┤ ├───B───┤ 2. 범위 A의 최대값이 범위 B의 최솟값보다 크거나 같으면서 범위 B의 최댓값보다 작거나 같은 경우min(B) ├───A───┤ ├───B───┤ 3. 범위 A의 최소값이 범위 B의 최솟값보다 크거나 같으면서 범위 B의 최댓값보다 작거나 같은 경우min(B) ├───A───┤├───B───┤ 4. 범위 A의 ..

Algorithm 2024.10.04

[백준] 28702 - FizzBuzz

문제문제 : https://www.acmicpc.net/problem/28702FizzBuzz 문제는 i = 1, 2, 3,... 에 대해 다음 규칙에 따라 문자열을 한 줄에 하나씩 출력하는 문제이다.i가 3의 배수이면서 5의 배수이면 FizzBuzz를 출력한다.i가 3의 배수이면서 5의 배수가 아니면 Fizz를 출력한다.i가 3의 배수가 아니면서 5의 배수이면 Buzz를 출력한다.i가 3의 배수가 아니면서 5의 배수도 아니면 i 값을 출력한다.연속으로 출력된 세 개의 문자열이 주어질 때 이 세 문자열 다음에 올 문자열은 무엇인가?  풀이값이 출력되는 규칙을 확인해보면 3과 5의 최소공배수인 15를 주기로 출력 패턴이 반복되는 것을 확인할 수 있다. 따라서 출력 규칙을 만들고,  1. 출력 규칙 생성ru..

Algorithm/백준 2024.07.01

[백준] 1018 - 체스판 다시 칠하기

문제문제 : https://www.acmicpc.net/problem/1018지민이는 단위 정사각형으로 나누어져 있는 M X N 크기의 보드를 찾았다. 보드 내 정사각형은 검은색 또는 흰색으로 칠해져 있는데, 지민이는 보드를 잘라서 8 X 8 크기의 체스판을 만들고자 한다.체스판은 검은색과 흰색이 번갈아가면서 칠해져 있어야 하고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서 지민이는 보드를 잘라낸 후 몇 개의 정사각형을 다시 칠하려고 한다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하여라.  풀이좋은 방법이 없을지 좀 오래 고민을 해보았는데, 입력 크기도 작아서 그냥 완전 탐색하는 방식으로 진행했다. 1. 체스판 초기화체스판은..

Algorithm/백준 2024.06.20

[백준] 1260 - DFS와 BFS

문제문제 : https://www.acmicpc.net/problem/1260그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하라. 단, 방문할 수 있는 정점이 여럿인 경우에는 정점 번호가 작은 것부터 방문한다.첫째 줄에 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선을 연결하는 두 정점의 번호가 주어진다. 입력으로 주어지는 간선은 양방향이다.  접근2024.05.08-[알고리즘] 너비 우선 탐색(BFS) 이란, 2024.05.12-[알고리즘] 깊이 우선 탐색(DFS) 이란에서 살펴본 대로 구현하면 된다.   구현1. 입력값 초기화import sysN, M, V = map(int, sys.stdin.readline()...

Algorithm/백준 2024.06.19

[백준] 2108 - 통계학

문제문제 : https://www.acmicpc.net/problem/2108통계학에서 N개 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다.산술평균 : N개의 수의 합을 N으로 나눈 것중앙값 : N개의 수를 오름차순으로 나열했을 때 그 중앙에 위치하는 값최빈값 : N개의 수 중 가장 많이 나타나는 값범위 : N개의 수중 최댓값과 최솟값의 차이첫째 줄에 수의 개수 N을 입력받고, 다음 N개 줄에 걸쳐 정수를 입력받을 때 네 가지 기본 통계값을 구하여라.   접근통계 등의 데이터를 처리할 때는 numpy를 곧잘 사용하는데, 이번 글에서는 numpy 사용 없이 풀이해보려고 한다. 먼저 입력 데이터는 다음과 같이 선언했다.import sysN = int(sys.stdin.readline())list_n..

Algorithm/백준 2024.06.18

[백준] 1966 - 프린터 큐

문제문제 : https://www.acmicpc.net/problem/1966일반적으로 프린터 기기는 인쇄 명령을 받은 순서대로 문서를 인쇄한다. 그런데 최근 상근은 다음과 같이 동작하는 새 프린터 소프트웨어를 개발했다.1. 프린터 큐 내 맨 앞에 있는 문서의 중요도를 확인한다.2. 나머지 문서 중 현재 문서보다 높은 중요도의 문서가 있으면, 이 문서는 인쇄하지 않고 큐의 맨 뒤로 재배치한다. 그렇지 않으면 현재 문서를 인쇄한다.프린터 소프트웨어를 사용하여 프린터 큐에 있는 문서의 수와 중요도가 주어졌을 때, 임의 문서가 몇 번째에 인쇄되는지 반환하는 프로그램을 작성하라. 첫줄에는 테스트 케이스의 수가 주어지고, 각 테스트케이스는 두 줄로 이루어져 있다.테스트케이스의 첫번째 줄에는 문서의 개수 n과 인쇄..

Algorithm/백준 2024.06.14

[알고리즘] 깊이 우선 탐색(DFS) 이란

깊이 우선 탐색깊이 우선 탐색(Depth First Search)이란 그래프 탐색 방법 중 하나로, 최근에 방문한 정점을 선택한 뒤, 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 주로 깊이 우선 탐색과 같이 언급되는 알고리즘이다.단순 검색 속도는 BFS보다 느리기 때문에 검색이 아닌 순회할 때 많이 사용한다. 즉, 방문할 수 있는 모든 정점을 확인해야 할 때 깊이 우선 탐색을 사용한다. 또한 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법인 백트래킹, 그리고 자동 미로 생성에서 많이 사용한다. 참고로 깊이 우선 탐색으로 찾은 결과는 최단 경로가 된다는 보장은 없다. 또한 해가 없을 경우를 고려하여 탐색할 깊이를 미리 지정할 필요가 있다.   동작 방식임의..

Algorithm 2024.06.03

[백준] 2606 - 바이러스

문제https://www.acmicpc.net/problem/2606웜 바이러스는 네트워크를 통해 전파되기 때문에 한 컴퓨터가 웜 바이러스에 걸리면 네트워크 상에서 연결된 모든 컴퓨터가 웜 바이러스에 걸린다.예로 들어 그림 1과 같은 네트워크가 있다고 할 때, 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번, 5번 컴퓨터를 거쳐 3번, 6번 컴퓨터까지 전파된다. 즉, 2번, 3번, 5번, 6번 컴퓨터가 웜 바이러스에 걸리게 된다.컴퓨터의 수와 네트워크 상에서 직접 연결되어 있는 컴퓨터의 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의의 수를 구하여라.입력으로는 첫째 줄에 컴퓨터의 수가, 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이후로 ..

Algorithm/백준 2024.05.31

[백준] 2178 - 미로탐색

문제문제 : https://www.acmicpc.net/problem/2178N X M 크기의 배열로 표현되는 미로가 있다.101111101010101011111011미로에서 1은 이동할 수 있는 칸이고, 0은 이동할 수 없는 칸이다. 이 미로에서 (1, 1)에서 출발해 (N, M)으로 이동할 때 지나야 하는 최소 칸의 개수를 구하는 프로그램을 작성하라. 한 칸에서 다른 칸으로 이동할 때는 서로 인접한 칸으로만 갈 수 있다.입력의 첫째 줄에는 두 정수 N, M이 주어지고, 다음 N개의 줄에 M개의 정수가 붙어서 입력으로 주어진다. 또한 항상 도착 위치로 이동할 수 있는 경우만 고려한다.  2024.05.10-[프로그래머스] 게임 맵 최단거리와 동일한 형태의 BFS 문제이다. 게임 맵 최단거리에서 불필요한..

Algorithm 2024.05.30

[프로그래머스] 게임 맵 최단거리

문제문제 : https://school.programmers.co.kr/learn/courses/30/lessons/1844ROR 게임은 두 팀으로 나눠서 진행하는데, 상대 팀의 진영을 먼저 파괴하면 이긴다. 즉, 각 팀은 상대 팀 진영에 빠르게 도착해야 한다. 아래 그림은 당신의 팀 캐릭터(행 :1, 열 : 1), 상대 팀의 진영(행: 5, 열: 5) 그리고 게임의 맵(5 X 5)을 표현한 것이다.맵에서 검은 부분은 벽으로 막혀 갈 수 없는 길이고, 흰 부분이 갈 수 있는 길이다. 캐릭터는 동서남북으로 한 칸씩 이동하되 맵을 벗어날 수는 없다. 만약 상대 팀 진영이 벽으로 막혀있다면 상대 팀 진영에 도착할 수 없다.게임의 맵을 이차원 배열 maps 매개변수로 전달받을 때, 캐릭터가 상대 팀 진영에 도착..

Algorithm 2024.05.30