반응형 알고리즘63 백준 #1111 IQ Test 이번 문제는 이원 일차 방정식을 푸는 문제입니다. IQ Test란 이름을 가지고 있지만, 뭐 그렇게 거창한 것은 아닙니다. 이원 일차 방정식에서 미지수를 구하기 위해서는 최소 2개의 식이 필요합니다. Gold III 문제인데, 정답률은 15.4%로 아주 낮습니다. 실제 문제 난이도가 어려운 것은 아닌데, 틀릴 수 있는 소지가 많아서 난이도가 높게 잡혔다고 보입니다. 이원일차 방정식으로 풀어도 되겠지만, 인접한 두 항의 차를 구하는 방법도 있습니다. 앞에 방식보다는 인접한 두 항의 차를 이용하는 것이 더 편하겠죠. 사실 원리는 이원일차 방정식에서와 똑같습니다. \[ ax_0 + b = x_1 , ax_1 + b = x_2 \to a( x_1 - x_0 ) = x_2 - x_1 \] 일단 처음 3개의 항만 .. 2020. 1. 3. 백준 #1107 리모컨 일부숫자버튼이 고장나서 숫자를 원하는대로 못 누르는 리모컨이 있습니다. 이 리모컨에서 최소한의 버튼을 눌러서 원하는 채널을 틀려면 어떻게 할까요? 조금은 어려울 수 있는 문제입니다. 고장난 숫자키만 아니라면 BFS로 풀 필요도 없이 숫자로 채널을 바로 선택하거나, 그것보다 적은 횟수의 채널 위아래 버튼을 누름으로써 해결볼 수 있겠죠. 난이도는 Gold V 입니다. 정답벼율이 21.7%로 상당히 낮습니다. https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주.. 2020. 1. 2. 백준 #1103 게임 숫자가 써져있는 보드의 맨 왼쪽 위에 돌이 있고, 그 칸에 써져있는 숫자만큼 돌을 상하좌우로 옮길 수 있습니다. 이 게임은 돌이 보드 중간에 있는 구멍 또는 밖으로 나가게 되면 끝나게 됩니다. 돌의 위치에서 판단할 때, 가장 오랫동안 돌을 움직이기 위해서는 모든 경우를 생각해야 합니다. 또는 돌이 지나왔던 칸으로 다시 돌아온다면, 그 게임을 무한하게 즐길 수도 있습니다. 난이도는 Gold I입니다. 사실 생각보다 난이도가 높습니다. 맞은 사람 548명, 정답비율 17.6%. 이 문제는 모든 경우를 찾으면 반드시 시간초과로 실패하게 됩니다. 그렇다고 모든 경우를 찾지 않으면 안 됩니다. 모순이죠? 다행히 자신이 왔던 자리로 돌아오면, 사이클을 이루기 때문에 그 상태에서는 더 조사할 필요가 없습니다. 또한 .. 2020. 1. 2. 백준 #1094 막대기 막대기란 문제는 알고리즘을 설명하고, 그 결과를 예측해야 합니다. 사실 여기서 설명하는 알고리즘은 복잡해보이지만, 그것이 무엇을 의미하는지 알면 손쉽게 문제를 풀 수 있습니다. 64와 절반으로 자른다라는 의미만 잘 이해한다면, 쉽습니다. 난이도는 Silver V이지만, 그보다 더 낮아져야 맞을 듯 합니다. https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다. 막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를.. 2020. 1. 1. 백준 #1083 소트(정렬) 이번 문제는 버블 정렬을 잘 이해하고 있다면, 쉽게 풀 수 있는 문제입니다. 난이도가 Gold IV이긴 하지만 더 낮아져도 상관 없을 문제라고 봅니다. 정답비율은 30.5% 정도로 높지가 않습니다. 정답자 184명. https://www.acmicpc.net/problem/1083 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다. www.acmicpc.net 버블 정렬은 이해하기 아주 쉬운 정렬이고, 구현도 쉽게 할 수 있죠. 버블정렬은 이웃한 것끼리 위치를 바꾼다는 개념입니다. 키 순으로 줄을 설 때.. 2019. 12. 31. 백준 #1081 합 숫자가 주어지면, 숫자에 있는 모든 자릿수의 합을 구할 수 있습니다. 예를 들어서 \(47 \to 4+7=11\)이 됩니다. 이 문제는 주어진 숫자 범위에 있는 모든 수에 대한 자릿수의 합을 구하는 것입니다. 이미 이 문제는 #1019에서 다루었던 것입니다. 단지 다른 것은 #1019 문제는 1부터 주어진 숫자까지의 자릿수 합이지만, 여기서는 시작하는 숫자가 주어진다는 것뿐입니다. #1019는 모든 자릿수들의 빈도를 출력하는 것이지만, 이 문제는 합을 표현하는 것입니다. 아이러니하게 #1019는 난이도가 Gold I 이지만, 이문제는 두단계 낮은 Gold III입니다. https://www.acmicpc.net/problem/1081 1081번: 합 첫째 줄에 L과 U이 주어진다. U은 0보다 크거나 같.. 2019. 12. 31. 이전 1 2 3 4 5 6 7 8 ··· 11 다음 728x90
