알고리즘
-
백준 24955번 숫자 이어 붙이기알고리즘 2023. 3. 1. 11:01
문제 설명 이번 문제는 N개의 집과 N-1개의 도로에서 집마다 1~N까지 번호가 붙어있고, 두 집 사이를 이동할 경우 도로를 이동할 때, 출발지점부터 끝지점까지 이동하면서 집의 번호를 이어붙이면 어떤숫자가 되는지 맞추는 문제입니다. 문제 풀이 아이디어 시작집과 끝집 사이를 최소로 이동하는 방법 bfs를 이용해 최소 이동 방법을 구할 수 있습니다. queue에 넣을 원소는 [{이어붙인 번호:string}, {현재 집}]의 배열 형태입니다. 집 번호와 현재 집 문제에서 제시된 집에는 1~N의 번호가 붙어있습니다. 만약 집 1에 번호 3번이 붙어있는 경우 집의 번호는 3번이고 현재 집은 1이라고 표시하겠습니다. (헷깔릴 수 있으므로 위와 같이 정의했습니다.) 풀이 bfs [시작 집의 번호, 시작 집]배열을 q..
-
백준 20311 화학 실헙알고리즘 2023. 2. 28. 22:45
문제 설명 이번 문제는 시험관의 전체 개수, 시험관에 들어있는 시약 종류의 개수와 각 시약이 들어있는 시험관의 개수가 주어지고, 시험관을 나열할 때 모든 이웃한 시험관 쌍에 대해, 두 시험관에 들어 있는 시약의 색깔이 서로 다르게 나열할 수 있는 방법을 출력하는 문제입니다. (조건을 만족하는 시험관 배열을 만들 수 있으면, 시험관의 색깔 번호를 공백으로 구분하여 순서대로 출력합니다. 답이 여러 개일 경우 아무거나 출력, 조건을 만족하는 시험관 배열을 만들 수 없으면 -1을 출력합니다.) 문제 풀이 아이디어 조건을 만족하는 방법 이웃한 두 시험관의 색이 무조건 다를 수 있는 조건 중 하나는 가장 많은 시약의 개수가 전체 시험관 개수의 절반을 넘어서면 안 되는 것입니다. 1. 가장 많은 시약의 수가 절반 이..
-
백준 25918번 북극곰은 괄호를 찢어알고리즘 2023. 2. 27. 15:29
문제 설명 이번 문제는 협이가 O와 X를 원하는 만큼 놓을 수 있고, 하루가 지나면 북극곰이 O는 '('와 ')'로 찢고 X는 ')'와 '('로 찢을 경우, 주어진 괄호 문자열을 만들기 위해서는 최소 며칠이 걸리는지 구하는 문제입니다. 문제 풀이 아이디어 스택 괄호가 어느 방향으로 존재하든 그 반대 방향의 괄호가 들어오면 해당 문자열 'O'나 'X'를 만들 수 있다는 것입니다. 그러므로 이전에 들어온 문자열과 비교할 수 있는 FIFO인 스택을 사용해보도록 하겠습니다. 하루보다 더 많이 걸리는 경우 만약 '()'와 ')('와 같이 다른 방향의 괄호가 나란히 왔을 경우, 해당 괄호 문자열은 하루만에 만들 수 있습니다. 만약 '(('와 '))' 같은 방향의 괄호가 나란히 나왔을 경우, 해당 괄호 문자열을 하루..
-
백준 1636번 한번 열면 멈출 수 없어알고리즘 2023. 2. 25. 09:00
문제 설명 이번 문제는 프링글스마다 중독 스트레스 범위가 주어지고 원숭이가 프링글스를 먹을 때 해당 프링글스의 중독 스트레스 범위 내에서 중독 스트레스를 스스로 조절할 수 있습니다. 하지만, 중독 스트레스를 조절할 때마다 예상 수명이 1년씩 줄어들게 됩니다. 원숭이가 N개의 프링글스를 열어서 모든 프링글스를 무조건 먹게될 경우, 프링글스를 한 통씩 먹으면서 원숭이가 중독스트레스를 조절할 때, 줄어드는 예상 수명을 최소화하는 프로그램을 작성하는 문제입니다. 문제 풀이 아이디어 이전 프링글스와의 중독 스트레스 범위 비교 경우의 수와 스트레스 조절 최소화 이전 프링글스의 중독 스트레스 범위를 a1~b1(노란색), 현재 프링글스의 중독 스트레스 범위룰 a2~b2(초록색)라고 할 때, 1. b1 < a2인 경우 ..
-
백준 20529번 가장 가까운 세 사람의 심리적 거리알고리즘 2023. 2. 24. 09:56
문제 설명 이번 문제는 mbti가 주어졌을 때 네 가지 척도에서 다른 것의 개수를 심리적인 거리로 측정할 때, N명의 학생 중 가장 가까운 심리적 거리를 가지고 있는 3 학생의 심리적 거리를 구하는 문제입니다. 문제 풀이 아이디어 경우의 수 비교할 세 사람의 mbti가 모두 같은 경우 비교할 세 사람 중 두 사람의 mbti가 같은 경우 비교할 세 사람의 mbti가 모두 다를 경우 가장 가까운 거리를 가지는 조건 모두 같은 mbti를 가진 사람이 3명이면 3명의 심리적 거리는 0이 되므로, 같은 mbti를 가진 사람이 3명이 있는 경우 최소 심리적 거리는 0이 됩니다. 같은 mbti를 가진 사람이 2명이면 2명의 심리적 거리는 0입니다. 다른 한 사람과의 심리적거리를 a라 할 경우 3명의 심리적 거리는 2..
-
백준 3130번 붙인드롬알고리즘 2023. 2. 23. 22:54
문제 설명 이번 문제는 길이가 같은 펠린드룸 두개를 나란히 붙여서 길이가 N인 수를 만들 때, M으로 나누어 떨어지는 개수를 구하는 문제입니다. 문제 풀이 아이디어 팰린드롬 구하기 구하고 싶은 팰린드롬의 길이 n이 짝수일 경우 0~9 숫자 n//2개의 중복순열의 개수가 답이 됩니다. 예) 4자리의 팰린드룸을 구하면, 0000, 0110, 0220, 0330, .... 위와 같이 2자리 수와 2자리 수를 뒤집은 수를 합치면 팰린드롬이 됩니다.(00, 01, 02, 03, ....) 그러므로 4자리의 팰린드룸 개수는 10^2가 됩니다. 구하고 싶은 팰린드룸의 길이 n이 홀수일 경우 (0~9 숫자 n//2개의 중복순열의 개수) * (중간에 올 수 있는 수 10개) 예) 5자리의 팰린드룸을 구하면, 00000,..
-
백준 3541번 상근타워알고리즘 2023. 2. 22. 14:56
문제 설명 엘리베이터의 개수가 m개인 매우 높은 타워에서 하나의 엘리베이터만 정해서 탈 때, n번의 버튼을 눌러서 갈 수 있는 가장 낮은 층을 구하는 문제입니다. 문제 풀이 아이디어 엘리베이터가 움직일 수 있는 층 상근 타워는 0층부터 매우 높은 층까지, 지상에만 존재하기 때문에 지하로는 내려갈 수 없다. 그러므로 우선 엘리베이터를 위로 올린다음에 아래로 내려서 최대한 낮은 층에 머물 수 있도록 해줘야합니다. 낮은 층을 찾는 방법 엘리베이터를 타고 가장 낮은 층에 도착하는 경우의 수는 다시 로비로 되돌아올 경우입니다. 엘리베이터가 다시 로비로 도착할 수 있는 방법은 엘리베이터를 타고 올라간 층수와 내려올 수 있는 층수가 같을 경우입니다. -> 최소 공배수 풀이 반복 찾기 버튼을 누를 때마다 낮은 층수를 ..
-
백준 15686번 치킨 배달알고리즘 2023. 2. 21. 22:33
문제 설명 이번 문제는 좌표에 치킨 집과 가정 집이 있고 남길 치킨 집의 개수가 주어졌을 경우, 가정 집과 가장 가까운 치킨 집 사이의 거리를 치킨 거리라고 할 경우, 모든 가정 집의 치킨 거리의 합의 최소값을 구하는 문제입니다. 문제 풀이 아이디어 치킨 거리의 합의 최소값 구하는 방법 이번 문제는 각 가정집에서 치킨 집까지의 거리를 모두 구해야지만 최소값을 구할 수 있습니다. 그리고 남길 M개의 치킨 집 조합에 따라 각 가정집의 치킨 거리는 달라집니다. 그러므로 이번 문제는 모든 경우의 수를 다 살펴봐야지만 정답을 구할 수 있습니다. -> 브루트포스 알고리즘 풀이 풀이 1. 각 치킨 집 중 m개의 조합을 구해서 각 조합의 치킨 거리를 구한 다음 비교하여 최소값을 구해냅니다. ->필자는 위의 방법을 사용..