본문 바로가기
반응형

알고리즘 문제풀이

 (66)
[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 번을 가지고 연구를 하겠습니다! 자! 이제 어떻게 답을 찾아가는지 생각해봅시다! 우선, 위와 같은 상황에서 디피를 만들면 이전에 뽑은 수들을 하나하나 다시 비교하면서 승점이 어떻게 되는지 확인하려면, 정렬을 하는것이 좋아보입니다.왜냐하면, 정렬을 한 상태라면 '이..
[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를 ..
[알고스팟] 지니어스 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)GENIUS20000ms65536kb751177 (23%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제MP3 플레이어에 들어 있는 곡들을 전부 셔플 모드로 들을 때 최대의 문제점은 서로 어울리지 않는 노래들이 갑자기 나올 수 있다는 것입니다. 끈적한 애시드 재즈를 듣고 있다가 갑자기 시끄러운 데스 메탈이 나오는 것만큼 분위기를 깨는 것도 없지요. 때문에 전세계에서 가장 잘 나가는 MP3 플레이어를 생산하는 오렌지 사에서는 이번에 지니어스라는 기능을 출시했습니다. 지니어스는 MP3 플레이어에 들어 있는 곡들을 셔플 모드로 들을 때 잘 어울리는 것끼리 순서대로 재생되도록 해 줍니다.태윤이는 오렌지 사의 새 MP3 플레이어를..
[알고스팟] 회전초밥 문제 링크 회전초밥문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)SUSHI8000ms65536kb1899628 (33%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제문제 풀이 내기에서 모인 벌금이 많이 쌓여서 알고스팟 운영진들은 회식을 하러 회전초밥집에 갔습니다. 회전초밥집에 들어선 운영진들은 초밥은 먹지 않고 전략 회의를 시작했습니다. 회전초밥집에는 n종류의 메뉴가 있는데, 운영진들은 각 메뉴에 대해 선호도를 매겼습니다.초밥계란연어장어대뱃살스테이크후라이드 치킨가격25003000400050001000015000선호도791012201운영진들은 주어진 예산 안에서 선호도의 합을 최대한으로 하도록 초밥을 먹고 싶습니다. 각 종류의 초밥은 무한정으로 공급된다고 가정합..
반응형

티스토리툴바