전체 글
-
백준 16432번: 떡장수와 호랑이 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 30. 15:33
https://www.acmicpc.net/problem/16432 16432번: 떡장수와 호랑이 동희가 N일동안 호랑이에게 떡을 줄 방법이 있다면 i (1 ≤ i ≤ N) 번째 줄에 동희가 호랑이에게 주어야 할 떡을 출력합니다. 이 떡은 동희가 i번째 날에 만든 떡이어야 합니다. 만약 동희가 떡을 www.acmicpc.net 접근 구현 방법만 잘 파악하고 있다면 어렵지 않게 풀 수 있는 문제. 우선 오늘 받은 떡의 종류를 차례로 배열에 넣어준다. 이렇게 모은 각 날짜의 떡 종류 배열을 토대로 깊이 우선 탐색을 해준다. 이때, 체크해야 할 두 가지 조건이 있다. 첫 번째는 당연하게도 현재 날짜의 현재 떡에 접근한 적 있는지 탐색 여부다. 탐색 여부를 체크하지 않고 중복 방문을 허용한다면 연산이 기하급수적..
-
백준 11509번: 풍선 맞추기 (Python/Java)Algorithm/Algorithm Problem 2022. 1. 28. 12:02
https://www.acmicpc.net/problem/11509 11509번: 풍선 맞추기 첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다. www.acmicpc.net 접근 이 문제의 키포인트는 현재 높이의 화살과 이 화살이 풍선을 만날 수 있도록 체크하는 방법이다. 이 부분만 구현한다면 문제는 굉장히 쉽다. 우선 문제 조건을 확인해보자. 문제 조건에서 높이는 1에서 1000000까지다. 우리는 배열을 통해서 높이에 있는 화살 개수를 체크할 것이다. 이 경우에는 설정을 어떻게 해야 할까? 높이를 인덱스 번호로 두고 해당 인덱스에 들어있는 값을 화살의 개수로 두면 될 것이다. 물론 배열의 인덱스는 0부터 시작하니 정..
-
백준 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을 통해 모든 국회의원을 연쇄적으로 없앨 수 있게 된다. ..