본문 바로가기

전체 글108

[1일 1문제] 백준 17471번: 게리맨더링 문제 백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 .. 2023. 9. 9.
[1일 1문제] 백준 17135번: 캐슬 디펜스 문제 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다. 성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 .. 2023. 9. 8.
[소공] 1장 소프트웨어공학 소개 1-1 소프트웨어 1. 소프트웨어란? : 프로그램과 그 외의 문서로 이루어진 것. 여기서 말하는 문서는 프로그램의 개발 및 운용 등에 필요한 정보 문서. 2. 소프트웨어의 특징(6) : 복잡성, 순응성, 변경성, 비가시성, 복제용이성, 비마모성 (마모되다: 마찰 부분이 닳아서 없어지다) 3. 소프트웨어의 유형(3) 소프트웨어 분류 특징 소프트웨어 카피 수량 요구되는 하드웨어 개발 인력 주문형 소프트웨어 특정 대상의 요구를 만족시키기 위해 제작한 소프트웨어 적음 낮음 많음 패키지 소프트웨어 패키지화 해 상업적으로 판매하는 소프트웨어. 워드프로세서 중간 높음 중간 임베디드 소프트웨어 다른 시스템에 내장된 소프트웨어 많음 중간 적음 4. 시스템이란? : 필요한 기능을 실현하기 위해 관련 요소를 어떤 법칙에 따.. 2023. 9. 7.
[1일1문제] 백준 14502번: 연구소 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 .. 2023. 9. 7.
[1일1문제] 백준 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15.. 2023. 9. 6.
[이코테] chapter07 이진 탐색 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. 이진 탐색 : 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 (1) 순차 탐색 순차 탐색이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 시간 복잡도는 O(N)이다. (2) 이진 탐색: 반으로 쪼개면서 탐색하기 이진 탐색은 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 데이터를 찾는 방법이다. 그래서 내부의 데이터가 이미 정렬디되어 있어야만 사용할수 있는 알고리즘이다. 시간 복잡도는 O(logN)이다. 이진 탐색을 구현하는 방법에는 재귀함수를 사용하는 방법과 반복문을 사용하는 방법이 있다. 1️⃣ 재귀함수로 구현 def binary_sear.. 2023. 9. 6.
[1일1문제] 백준 23884번: 알고리즘 수업 - 선택 정렬 4 문제 오늘도 서준이는 선택 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 선택 정렬로 배열 A를 오름차순 정렬할 경우 K 번 교환이 발생한 직후의 배열 A를 출력해 보자. N이 매우 커서 시간 초과를 고민하고 있는 우리 서준이를 도와주자. 크기가 N인 배열에 대한 선택 정렬 의사 코드는 다음과 같다. selection_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다. for last 2023. 9. 5.

티스토리툴바