본문 바로가기
반응형

알고리즘

 (104)
[SW Expert Academy] Code Battle! 매주 화요일에 열리는 코드 배틀!오늘도 참여했습니다.언제나처럼 2 문제를 풀었습니다. 핫핫 SW Expert Academy의 문제는 무단 복제가 금지되어 있기 때문에 링크로 대체합니다!클릭시 이동합니다!! No. 1 이진 문자열 복원 어떻게 풀까? 해당 문제는 00, 01, 10, 11의 개수가 주어졌을 때, 만들 수 있는 이진 문자열을 아무거나 출력하면 됩니다!두 문자 00, 01, 10, 11을 1번 문자, 2번 문자, 3번 문자, 4번 문자라고 하겠습니다! 문자열을 이어보면, 이진 문자열의 끝에 따라서 다음에 몇 번 문자가 오는지 알 수 있습니다. 그림에서 보듯이, 문자의 끝이 1이라면 뒤에 10 혹은 11이 와야합니다!문자의 끝이 0이라면, 00, 01 문자가 와야합니다. 또한, 1번, 2번, 3..
[BOJ] 14925. 목장 건설하기 목장 건설하기클릭시 이동합니다.어떻게 풀까!? 이 문제는 DP 알고리즘 입니다! 정사각형이 어떻게 만들어지는지 알면 점화식을 통해 구할 수 있는 문제이죠! 3x3 에서 정사각형은 어떻게 만들어 질까요?? (i, j)에 3x3의 사각형을 만들 수 있는 경우를 살펴보겠습니다! 3x3 정사각형을 만들 수 있다면, (i, j-1) 에는 2x2의 정사각형을 만들 수 있습니다! 마찬가지로, (i-1, j)에도 2x2의 정사각형을 만들 수 있죠! 그리고! (i-1, j-1)에도 2x2 정사각형을 만들 수 있습니다! 반대로, (i-1, j-1)과 (i-1, j), (i, j-1)에 2x2 정사각형을 만들 수 있다면, (i, j)에는 3x3의 정사각형을 만들 수 있다는 것을 알 수 있습니다! 그럼, 다른 경우를 봅시다!..
[SW Expert Academy]4301. 콩 많이 심기 [SW Expert Academy] 4301. 콩 많이 심기 4301. 콩 많이 심기 4301. 콩 많이 심기 누군가가 많이 떠오르는 문제입니다. 어? 왜 두 번 써지지???누군가가 많이 떠오르는 문제입니다. 어? 왜 두 번 써지지??? SW Expert Academy의 문제는 저작권 때문에 링크로 대체하겠습니다!SW Expert Academy의 문제는 저작권 때문에 링크로 대체하겠습니다! 어떻게 풀까?!어떻게 풀까?! 처음에는 굉장히 복잡했지만, 단순하게 풀 수 있다는 것을 깨달았습니다...처음에는 굉장히 복잡했지만, 단순하게 풀 수 있다는 것을 깨달았습니다... 그림으로 보시면 여러분도 금방 풀이법을 떠올리실 수 있을 것입니다!그림으로 보시면 여러분도 금방 풀이법을 떠올리실 수 있을 것입니다! 자 우선, n = 3 , m = 4인 경우를 생각해보겠습니다.자 우..
[SW Expert Academy] 5170. 상원이의 직선 긋기 게임 5170. 상원이의 직선 긋기 게임 SW Expert Academy의 문제는 무단 복제가 금지되어있기 때문에 링크로 대체합니다!클릭시 이동합니다! 어떻게 풀까? 가장 쉽게 떠오르는 방법은 역시 모든 점을 그려보는 것이죠!모든 점을 그리면서 중복되는 기울기는 그리지 않는 형식으로 가면 됩니다! 그렇다면 기울기는 어떻게 체크할까요?double을 사용해서 실수로 체크할 수도 있지만, 분모가 0이 되는 순간 처리하기가 너무 애매해집니다.또한, 이전의 자료들을 저장하기 위해서는 set과 같은 자료구조의 힘을 빌려야하죠! 생각보다 간단하게 실수를 저장하는 방법이 있습니다!바로, 분수 형태를 이용하는 것이죠! 2차원 배열을 사용해서 check[분자][분모] 형태로 저장하는 방법입니다!단, 이렇게 저장할 경우에는 약간..
[SW Expert Academy] 4701. 경시대회 매니저의 고민 4701. 경시대회 매니저의 고민 SW Expert Academy의 문제들은 저작권이 있기 때문에 링크로 대체합니다!클릭시 이동합니다!! 어떻게 풀까? 이 문제는 경우의 수를 구하는 문제입니다!전에 있던 경우의 수가 어떻게 해서 다음의 경우의 수에 영향을 줄지 잘 생각해서, 이를 점화식으로 표현하는 것이 중요합니다. 더 간단히 요약하면, DP라는 것이죠! 과연, 이전의 어떤 경우에서 DP를 구할 수 있을까요!? 자! 홈페이지의 테스트 케이스 1 번을 가지고 연구를 하겠습니다! 자! 이제 어떻게 답을 찾아가는지 생각해봅시다! 우선, 위와 같은 상황에서 디피를 만들면 이전에 뽑은 수들을 하나하나 다시 비교하면서 승점이 어떻게 되는지 확인하려면, 정렬을 하는것이 좋아보입니다.왜냐하면, 정렬을 한 상태라면 '이..
[SW Expert Academy] 오랜만에 하는 코드 배틀! 그렇다고 합니다. 휴가는 필요없습니다!코드 배틀이야 말로 진정한 피서지인 것을! 뇌가 서늘해지는 그 곳 코드배틀에서 멘붕을 겪어봅시다! SW Expert Academy의 문제들은 외부 공개가 금지되어있기 때문에 링크로 대체합니다!! 5215. 햄버거 다이어트 어떻게 풀까? 모든 경우의 수를 확인해서 최고의 칼로리를 구하는 문제입니다!이전에 bit를 이용해서 모든 부분집합을 구하는 경우를 올려드린적이 있습니다! 해당 문제는 이를 이용해서 햄버거와 칼로리를 모두 계산해보면 해결할 수 있습니다! 1. 모든 부분 집합을 만들어본다.2. 칼로리가 주어진 조건보다 넘으면 무시!, 같거나 작으면 최대 만족도 갱신! 비트를 이용하여 부분집합을 만드는 법을 알고싶으시면 아래 링크를 클릭하세용! http://sangdo9..
[BOJ] 친구 네트워크 친구 네트워크문제 링크 어떻게 풀까? 이 문제는 disjoint set과 해쉬를 이용해서 문제를 풀면 됩니다! 위 두개의 방법에 대해서는 나중에 또 올리도록 하겠습니다! 문제를 푸는 방법을 알려드리겠습니다!disjoint set과 해쉬의 자세한 설명은 생략하겠습니다!분명! 언젠가 이 방법들에 대해 자세히 설명하는 날이 올 것입니다.. 흑!링크 꼭 달아드릴게요 우선, disjoint set을 하기 위해서 각각의 아이디를 해쉬를 통해서 인덱스에 저장해 놓는 것이 중요합니다!그리고, disjoint set을 이용해서 입력받은 두 아이디를 집합으로 만들고, 만들어진 집합의 크기를 출력하시면 문제가 풀리게 됩니다! 예제를 통해서 설명해 드리겠습니다! 처음에 해쉬는 모두 empty 상태이고, 집합은 -1로 초기화 ..
[SW Expert Academy] 호둥이의 단어 찾기 4753. 호둥이의 단어 찾기 SW Expert academy 문제는 저작권 문제가 있기 때문에 링크로 대체하겠습니다! 이 문제에서 가장 중요한 부분은 1. 사전 순으로 탐색한다.2. 둘이 다른 구간을 만나거나 똑같으면 종료된다.3. 만약, 사전에 단어가 있다면 뒤의 단어들은 사용하지 않는다.입니다. 저는 문제를 풀 때 트라이를 활용하면 될 것 같다고 생각했습니다! 우선 트라이는 위 그림과 같이 문자열의 알파벳을 하나하나 저장하는 구조입니다! a와 b를 저장한 것을 구분하기 위해 테두리를 두껍게 했습니다! 그럼 이와 같은 트라이를 어떻게 활용하면 이 문제를 해결할 수 있을까요?! 1 4 abc abd a ab 3 abcd a ab 위 입력을 예시로 설명해드리도록 하겠습니다! 테스트 케이스에서 abcd를 ..
반응형

티스토리툴바