codingtest12 [1일 1문제] 백준 1654번: 랜선 자르기 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다.. 2023. 9. 22. [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문제] 백준 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문제] 백준 23884번: 알고리즘 수업 - 선택 정렬 4 문제 오늘도 서준이는 선택 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 선택 정렬로 배열 A를 오름차순 정렬할 경우 K 번 교환이 발생한 직후의 배열 A를 출력해 보자. N이 매우 커서 시간 초과를 고민하고 있는 우리 서준이를 도와주자. 크기가 N인 배열에 대한 선택 정렬 의사 코드는 다음과 같다. selection_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다. for last 2023. 9. 5. [1일1문제] 백준 24445번: 알고리즘 수업 - 너비 우선 탐색 2 문제 오늘도 서준이는 너비 우선 탐색(BFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자. 너비 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 내림차순으로 방문한다. bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 for each v ∈ V - {R} visited[v] 2023. 9. 4. [1일1문제] 백준 2210번: 숫자판 점프 문제 5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다. 숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오. 입력 다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다. 출력 첫째 줄에 만들 수 있는 수들의 개수를 출력한다. 풀이 이론으로 공부만 하다가 처음 푸는 dsf 문제여서 그런지 생각보다 어렵고 감도 안 잡힌다. 일단 풀이를 보고 이해해야겠다. 참고.. 2023. 9. 3. [1일1문제] 백준 10773번: 제로 문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할.. 2023. 9. 2. [이코테] chapter12 구현 문제 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. 구현 알고리즘 : 머릿속에 잇는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기 ✨구현 알고리즘은 피지컬 싸움이다! (1) 완전 탐색 : 모든 경우의 수를 다 계산하는 해결 방법 (2) 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 문제 - 고려해야하는 메모리 제약 사항 - 파이썬은 자료형의 표현 범위 제한은 고려 안해도 됨! 리스트는 보통 128MB ~ 512MB 데이터의 개수(리스트 길이) 메모리 사용량 1,000 약 4KB 1,000,000 약 4KB 10,000,000 약 40MB 12-1.py 럭키 스트레이트 - ⭐1/3 (⭕) N = input() n = len(N) // 2 rig.. 2023. 7. 24. [이코테] chapter11 그리디 문제 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. 그리디(greedy) 알고리즘 : 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 그리디는 최적의 해를 보장할 수 없을 때가 많음 but, 코딩 테스트에서의 대부분의 그리디문제는 탐욕법으로 얻은 해가 최적의 해! 정당성 분석 필수! 11-1.py 모험가 길드 - ⭐1/3 (❌) 기준도 못잡고, 정당성 분석도 못해서 20분동안 고민하다가 포기한 문제! ㅠㅠ [교재 풀이] 근데 풀이를 보니까 넘 단순했다.. 오름차순으로 공포도 정렬 후 앞에서부터 공포도를 하나씩 확인하며 ''현재 그룹에 포함된 모험가의 수" >= "현재 확인하고 있는 공포도" 위의 조건을 만족하면 그룹 설정! 문제를 풀다가 'int' object i.. 2023. 7. 10. 이전 1 2 다음
