Algorithm
-
백준 4179번: 불! (Python/Java)Algorithm/Algorithm Problem 2022. 1. 25. 23:23
https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 접근 조금의 디테일만 다를 뿐 백준 5427번 불(https://www.acmicpc.net/problem/5427)과 완전 같은 문제. 해당 문제 풀이(https://codestation.tistory.com/14)를 참고하면 문제없이 풀 수 있을 것이다. 풀이 Python from collections import deque upDown = [-1, 1, 0, 0] leftRig..
-
백준 1541번: 잃어버린 괄호 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 24. 23:34
https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 접근 괄호를 묶는다는 의미만 알면 쉽게 풀 수 있는 문제다. 다들 알다시피 수학에서 괄호는 '먼저 계산한다'는 뜻이다. 그렇다면 덧셈이 있는 곳에 괄호를 쳐 숫자들을 더해준다면 나중에 뺄 때는 숫자 한 개를 뺄 때보다 훨씬 더 큰 수를 뺄 수 있게 된다. 즉, 가장 작은 수를 만들 수 있다. 구현 또한 간단하다. '-'를 기준으로 나눠준다. 그리고 그 나눠진 문자열을 다시 '+'를 기준으로 ..
-
백준 2343번: 기타 레슨 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 23. 20:52
https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 접근 이분 탐색 문제에서 가장 먼저 찾아야 할 것은 이분 탐색의 범위다. 최솟값과 최댓값을 알아야 둘로 나누어 탐색할 수 있기 때문이다. 이 문제에서 최솟값은 레슨 목록 중 가장 길이가 긴 레슨의 시간이다. 레슨은 나누어 저장할 수 없고 블루레이 하나에 무조건 저장이 되어야 한다. 어떤 레슨을 넣더라도 하나의 블루레이 디스크에 다 저장할 수 있으려면 블루레이 디스크가 레슨 중 가장 길이가 긴 레슨을 저장..
-
백준 15729번: 방탈출 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 22. 16:14
https://www.acmicpc.net/problem/15729 15729번: 방탈출 첫째 줄에 N(1 ≤ N ≤ 1,000,000)가 주어지고 둘째 줄에는 쪽지에 적혀 있는 N자리의 수가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 접근 주어진 버튼을 전부 0으로 만들어야 하는 것이 목표다. 또, 누른 버튼의 오른쪽 2개까지 함께 버튼이 눌린다. 이 얘기는 바로 앞 버튼부터 상태가 1인 버튼을 눌러나가야 한다는 뜻이다. 마지막, 혹은 중간부터 누르는 것은 의미가 없다. 그렇게 누르게 된다면 그보다 앞의 버튼을 눌렀을 때 상태가 변하게 될 수 있기 때문이다. 풀이 Python buttonNum = int(input()) board = list(map(int, (input()).spli..
-
백준 3079번: 입국심사 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 21. 09:05
https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 접근 이분 탐색은 결국 정렬되어 있는 범위 혹은 배열을 반씩 나누어 탐색하는 방법이다. 즉, 범위의 최솟값과 최댓값을 아는 것이 중요하다. 해당 문제에서 가장 최소로 나올 수 있는 시간 값은 가장 짧은 심사 시간이다. 최대로 나올 수 있는 시간은 가장 긴 심사시간에 모든 친구들이 심사를 받았을 때, 즉 '가장 긴 심사시간*친구 수'다. 이 범위를 중심으로 이분 탐색을 해본다. 설정한..
-
백준 16678번: 모독 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 20. 09:00
https://www.acmicpc.net/problem/16678 16678번: 모독 명예에 죽고 명예에 사는 나라 얼라이언스에는 1명의 왕과 N명의 국회의원이 있다. 각 N 명의 국회의원은 a1, a2, ..., aN 의 명예 점수를 갖고 있으며, 명예 점수가 양수인 한 그들은 국회의원을 www.acmicpc.net 접근 연쇄작용이 있다는 것이 중요한 문제. 일단 한 명이라도 명예 점수가 0이 나온 상태가 계속 이어지면 반복해서 국회의원들을 없앨 수 있다. 이 얘기는 무엇이냐, 바로 1부터 가장 큰 수까지 1씩 차이나는 숫자 조합이 만들어져야 한다는 뜻이다. 그래야 -1을 할 때마다 명예점수가 0인 국회의원이 계속 나오고, 한 번의 Defile을 통해 모든 국회의원을 연쇄적으로 없앨 수 있게 된다. ..
-
백준 16564번: 히오스 프로게이머 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 19. 21:35
https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ X www.acmicpc.net 접근 이분 탐색 문제를 풀 때 제일 먼저 찾아야 하는 조건은 최솟값과 최댓값이다. 이분 탐색은 특정 정렬 혹은 범위를 반씩 나눠가며 탐색하는 알고리즘이다. 때문에 범위를 특정할 수 있는 최솟값과 최댓값을 구하는 것이 필수적이다. 예시를 통해 살펴보자. 여기서 구할 수 있는 최솟값은 당연하게도 가장 낮은 레벨인 10이다. 그..
-
너비 우선 탐색 (Breadth-First Search, BFS)Algorithm/Algorithm Categories 2022. 1. 18. 08:34
기본 개념 '너비 우선 탐색'이란 그래프(혹은 트리와 같은 자료구조)를 탐색하는 방법 중 하나로, 자신이 탐색할 수 있는 가장 가까운 곳을 우선적으로 탐색하는 알고리즘이다. 다시 말해, 루트 노드에서부터 시작해 인접한 자식 노드들을 한 번씩 탐색하고 이를 반복해 탐색을 수행하는 알고리즘이다. 자신과 가까운 모든 경로를 탐색하고 그다음 거리의 경로를 탐색한다. 때문에 모든 경로를 탐색해야 하는 경우 '깊이 우선 탐색'보다 빠르게 수행할 수 있다는 장점이 있다. 예시 3*3, 총 9칸의 보드가 있고 이 보드를 탐색한다고 해보자. (움직일 수 있는 방향은 상하좌우 네 방향뿐이며 현재 내 위치는 A이다.) 너비 우선 탐색에서는 Queue를 이용해 탐색하는 방식을 주로 사용한다. Queue를 만들어주고 내 위치를..