전체 글
![[BOJ] 16637 - 괄호 추가하기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FoKLUp%2Fbtq9BZEKgZD%2FL1QHbdmGTRznhTTOOlibFK%2Fimg.png)
[BOJ] 16637 - 괄호 추가하기
문제 출처 [BOJ] 16637 - 괄호 추가하기 풀이 문제는 최대 길이가 19인 수식이 주어지고 수식에 괄호를 쳐서 연산의 결과가 가장 크도록 만들어야 합니다. 수식은 기존에 연산자 우선순위를 따르지 않고 앞에서부터 차례대로 연산이 수행되는데 이 때 괄호는 가장 먼저 수행됩니다. 완전탐색으로 모든 괄호를 쳐줄 수 있는 경우를 봐주어 문제를 풀었습니다. 재귀함수를 사용하여 괄호를 포함한 수식의 경우를 만들어주고 수식을 계산하여 가장 큰 수를 찾았습니다. 3 + 8 * 7 - 9 * 2라는 예제에 (3 + 8) * 7 - (9 * 2)와 같이 괄호를 붙여 수식을 만드는 과정과 결과로 vector에 남는 값들을 연산해 수를 찾는 과정입니다. 코드 small-j/Algorithm Contribute to sm..
![[BOJ] 13164 - 행복 유치원](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbWwRbe%2Fbtq9wgOQPjf%2FZCHyr1nxlRUi4keqkWNLFK%2Fimg.jpg)
[BOJ] 13164 - 행복 유치원
문제 출처 [BOJ] 13164 - 행복 유치원 풀이 유치원에서 N명의 원생들을 키 순서대로 줄 세우고 조를 나누어 티셔츠를 맞추려고 합니다. 조마다 티셔츠 맞추는 비용은 해당 조의 가장 큰 키의 원생 - 가장 작은 키의 원생 입니다. 원생이 키 순서대로 서있고, 서있는 원생이 인접한 원생들로 조를 이루어야 합니다. 각 원생이 바로 뒤의 원생과 얼마나 키차이가 나는지 확인하여 그 중에서 큰 수들을 조를 이루어야하는 수보다 1 작은 수 만큼 빼주면 그 수를 기점으로 조를 나누게 됩니다. 가장 차이나는 수가 큰 부분을 잘라서 조를 이루면 가장 작은 티셔츠 비용이 나오게 됩니다. 코드 small-j/Algorithm Contribute to small-j/Algorithm development by creat..
[BOJ] 17359 - 전구 길만 걷자
문제 출처 [BOJ] 17359 - 전구 길만 걷자 풀이 전구 묶음을 적절히 이어 전구 상태가 바뀌는 횟수를 최소로 하는 것을 목표로 하는 문제였습니다. N이 10으로 10!이어도 시간이 충분하기 때문에 전구 묶음의 배치는 완전 탐색으로 구성하면 됩니다. 하지만 완전 탐색을 돌릴때 묶음의 조합이 완성되어 이어진 묶음에서 전구 상태가 몇번 바뀌는지 매번 확인하게 되면 시간초과가 납니다. 각 전기 묶음의 전구 상태가 몇번 바뀌는지 미리 저장해놓고 각 전기 묶음이 이어지는 부분에서 전구의 상태가 바뀌는지만 확인해주어 시간초과를 해결할 수 있습니다. 코드 small-j/Algorithm Contribute to small-j/Algorithm development by creating an account on ..
[BOJ] 15918 - 랭퍼든 수열쟁이야!!
문제 출처 [BOJ] 15918 - 랭퍼든 수열쟁이야!! 풀이 랭퍼드 수열의 조건을 보면 다음과 같습니다. 1. 1 이상 n 이하의 자연수가 각각 두 개씩 들어있다. 2. 두 개의 n 사이에는 정확히 n개의 수가 있다. => 이 조건은 두 개의 n이 위치한 인덱스는 i, i + n + 1 이라는 것을 말합니다. 그렇기 때문에 문제에서 주어지는 x번째 수와 y번째 수는 y - x - 1 이라는 것을 알 수 있습니다. 이 문제는 완전탐색을 통해 풀 수 있습니다. 하지만 그냥 완전탐색을 돌리게 되면 12!이 되어 4억이 넘게 돌아가서 2초를 넘겨 시간초과가 나게 됩니다. 그래서 어떤 조건을 주어 완전탐색을 모두 도는 것이 아니라 일부만 돌아주면 됩니다. 1. 숫자는 쌍으로 넣어준다. 현재 인덱스, (현재 인덱..
[BOJ] 14654 - 스테판 쿼리
문제 출처 [BOJ] 14654 - 스테판 쿼리 풀이 매 경기의 결과를 비교해주어 연승의 횟수를 세서 많은 연승의 수를 출력하면 되는 간단한 구현 문제였습니다. 모든 경기마다 첫 번째 팀이 이겼는지, 두 번째 팀이 이겼는지 확인하여 이긴 팀의 승의 횟수를 올려주고 진 팀의 승의 횟수를 0으로 만들어주었습니다. 그리고 매번 가장 큰 값을 갱신해주어 가장 많은 연승 횟수를 구해주면 됩니다. 여기서 주의 할 점은 누가 승자인지 확인해주는 부분을 예외가 없도록 잘 짜주어야 한다는 것입니다. 저는 따로 game이라는 함수를 만들어서 첫 번째 팀이 이길경우 1 반환, 두 번째 팀이 이길경우 2 반환, 비길경우 3을 반환해주었습니다. 코드 small-j/Algorithm Contribute to small-j/Alg..
![[BOJ] 9519 - 졸려](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F3dqFy%2Fbtq9DlOaCX2%2FPuLf8FNxrekdLIW5CX9OKk%2Fimg.jpg)
[BOJ] 9519 - 졸려
문제 출처 [BOJ] 9519 - 졸려 풀이 눈을 깜빡인 횟수를 모두 돌아주어 문자열의 상태를 알아낸다면 시간초과가 날 것입니다. 그래서 다른 방법을 찾아야 합니다. 문제의 문자열이 바뀌는 규칙대로 쭉 써보다보면 규칙을 찾을 수 있습니다. 위의 사진과 같이 원래의 문자열로 돌아오는 주기가 있고 위의 예제는 5번 눈을 깜빡이면 다시 원래의 상태로 돌아오게 됩니다. 그렇다면 X를 주기만큼 나눈 나머지 값만큼 문자열을 바꿔준다면 정답을 구할 수 있습니다. 이 때 나머지 값만큼 문자열을 바꿔줄때는 정해진 규칙의 반대로 문자열을 바꿔주어야 눈을 깜빡이기 전 원래의 문자열을 찾을 수 있습니다. 코드 small-j/Algorithm Contribute to small-j/Algorithm development by ..
[BOJ] 8979 - 올림픽
문제 출처 [BOJ] 8979 - 올림픽 풀이 문제에서 입력받은 국가의 등수만을 알아내면 되기 때문에 알아낼 국가보다 높은 등수를 가진 국가를 세줘야겠다고 생각했습니다. g, s, b라는 변수에 각각 내가 등수를 찾아야 할 국가의 금메달 수, 은메달 수, 동메달 수를 저장해주었습니다. 그리고 모든 국가를 한번씩 봐주면서 cnt를 늘려준 경우는 다음과 같습니다. 1. 금메달 수가 g변수보다 큰 경우 2. 금메달 수가 같으면서 은메달 수가 s변수보다 큰 경우 3. 금메달, 은메달 수가 같으면서 동메달 수가 b변수보다 큰 경우 이 세가지 경우에만 나보다 높은 등수를 가진 국가들이기에 이 국가들을 세주고 그 뒤 등수가 정답이 됩니다. 코드 small-j/Algorithm Contribute to small-j/..
[BOJ] 15922 - 아우으 우아으이야!!
문제 출처 [BOJ] 15922 - 아우으 우아으이야!! 풀이 수직선 위에 그려진 모든 선분의 길이를 겹쳐진 부분을 중복되어 더하지 않고 구하는 문제입니다. 현재 선분의 시작부분이 이전 선분의 끝나는 부분보다 작다면 두 선분은 겹쳐있는 것입니다. 따라서 이전 선분의 끝나는 부분을 현재 선분의 끝나는 부분과 비교하여 둘중 큰 값을 이전 선분의 끝나는 값으로 넣어주었습니다. 만약 현재 선분이 이전 선분과 겹치지 않는다면 새로 vector에 선분을 추가해주었습니다. 이와 같은 방식으로 선분을 추가해주어 마지막에 모든 선분의 끝나는 부분에서 시작하는 부분을 빼어 길이를 알아내 더해주어 답을 구했습니다. 코드 small-j/Algorithm Contribute to small-j/Algorithm developm..
[BOJ] 12764 - 싸지방에 간 준하
문제 출처 [BOJ] 12764 - 싸지방에 간 준하 풀이 준하는 모든 사람들이 항상 정해진 시간에 싸지방을 이용한다는 것을 알고 모든 사람이 기다리지 않고 싸지방을 이용할 수 있는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람들이 사용했는지를 알아내는 것이 목표입니다. 사람들이 컴퓨터를 이용하는 시간이 뒤죽박죽이기 때문에 sort함수를 이용해 정렬하여 가장 먼저 컴퓨터를 이용하는 사람들부터 낮은 수의 컴퓨터를 배정해주었습니다. 그리고 컴퓨터를 사용하기 시작한 사용자의 종료시간과 컴퓨터 번호를 우선순위 큐(A)에 저장하여 종료된 후 바로 다음 사람이 이용할 수 있도록 현재 사용자의 시작시간과 비교하였습니다. 만약 A라는 우선순위 큐에서 사람이 나오게 된다면 그 자리는 비게 되기 때문에 자리숫자를 저장하는 ..
[BOJ] 11812 - K진 트리
문제 출처 [BOJ] 11812 - K진 트리 풀이 자식을 최대 K개 가질 수 있는 K진 트리에 있는 노드들 중 주어진 두개의 노드 사이의 거리를 구하는 문제였습니다. 두개의 노드가 주어지면 해당 노드의 부모노드를 찾고, 부모노드의 부모노드를 찾는 과정을 쭉 반복하면서 루트노드인 1을 만날때 까지 저장해주어 저장해준 값을 비교하면서 부모노드가 달라지는 경우를 판단해 거리를 구해주었습니다. 부모노드를 찾는 수식은 다음과 같습니다. 부모노드 = (현재 노드 + K -2) / K 코드 small-j/Algorithm Contribute to small-j/Algorithm development by creating an account on GitHub. github.com