본문 바로가기

반응형

SW Expert Academy

(19)
[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..
[SW Expert Academy] 코드 배틀!! 처음으로 해보는 1등! 허걱스 4751. 다솔이의 다이아몬드 장식 SW Expert Academy는 문제에 저작권이 걸려있기 때문에 링크로 대신하겠습니다! 문제를 푸는 방법은 생각보다 간단합니다!글자가 있는 위치를 기준으로 #을 찍어주는 함수를 만들면 됩니다! 이렇게 말이죠! 코드 12345678910111213141516171819202122232425262728293031323334353637383940#pragma once#include#include char str[51];char res[5][502]; void draw(int r, int c) { res[r - 2][c] = res[r - 1][c - 1] = res[r - 1][c + 1] = res[r][c - 2] = res[r][c + 2] = res[r + 1][c..
[SW Expert Academy] 4050. 재관이의 대량 할인 4050. 재관이의 대량 할인클릭시 문제로 이동합니다! SW Expert Academy는 저작권이 걸려있기 때문에 링크로 대체합니다! 어떻게 풀까? 생각보다 직관적으로 풀 수 있습니다. 먼저 알아야 할 것은가장 적은 돈을 내기 위해서는 가장 값이 비싼 물건들을 할인 받아야 한다는 것이죠!즉, 더 비싼 물건 2 개를 골라야 한다는 것입니다! 그렇다면, 어떤 물품의 집합에서 3 개를 골라서 가장 많이 할인을 받는 방법을 생각해봅시다! 당연하게도 가장 비싼 물건 3개를 하나의 조합으로 선택하고, 이 중에서 가장 싼 것을 할인받는 것이죠!그리고.. 나머지도 마찬가지 방법으로 해결될 것입니다. 결국 이 문제는 정렬을 해서 3번째 물건의 가격들을 빼면 풀리는 문제입니다! 코드 123456789101112131415..
[SW Expert Acade] 4616. 점프점프! 개굴이의 점핑! 4616. 점프점프! 개굴이의 점핑! SW Expert Academy는 문제의 무단 복제가 금지되어 있기 때문에 링크로 대체하겠습니다! 어떻게 풀까? 동적 계획법에서 가장 중요한 것은 어떠한 규칙으로 점화식을 만들까에 대한 것이죠!연꽃의 규칙을 발견하는 것이 가장 중요합니다!연꽃 f1에서 연꽃 f2로 이동하는 경우를 생각해봅시다.f1에서 f2로 이동하면, 결국 f2에서 f1으로 올 방법은 사라집니다!왜냐하면, 이동했다는것 자체가 바로 x나 y가 증가했다는 것을 의미하기 때문입니다!x나 y가 계속해서 증가해야 이동할 수 있는데, 더 작은 f1으로는 이동할 방법이 사라지는 것이죠! 이를 이용해서 연꽃을 한 번 정렬하면, 1번 연꽃부터 n번 연꽃까지 연꽃마다 갈 수 있는 연꽃으로 딱 한번씩만 이동시키면 답이 ..
[SW Expert Academy] 괄호 짝짓기 괄호 짝짓기 SW Exeprt Academy의 문제들은 무단복제가 금지되어있기 때문에 링크로 대체합니다. 어떻게 풀까? 대표적인 스택 활용 문제입니다. 열린 괄호의 경우에는 모두 스택에 저장합니다.그리고, 닫힌 괄호가 나타나면 스택의 맨 위의 괄호와 비교합니다. 만약, 스택의 맨 위의 열린 괄호와 현재 나타난 닫힌 괄호가 매칭이 되지 않는다면 제대로 맞지 않는 괄호겠죠! 또한, 마지막에 스택 사이즈도 확인해야 합니다.스택 사이즈가 0이 아니라면, 열린 괄호가 많이 남아있다는 것이겠죠! 이 상황도 괄호의 짝이 맞지 않는 경우입니다. 간단한 예시 문제 2개를 풀어보겠습니다. 열린 중괄호이기 때문에 스택에 넣습니다.마찬가지로 열린 대괄호이기 때문에 스택에 넣습니다.마찬가지로 열린 소괄호이기 때문에 스택에 넣습..
[SW Expert Academy] 길찾기 길찾기 SW Expert Academy는 문제 복제가 금지되어 있기 때문에 링크로 대체하겠습니다. 어떻게 풀까? 대표적인 DFS / BFS 문제입니다.저 같은 경우는 그냥 시작점에서 큐를 돌려서 BFS를 이용해서 풀었습니다! 0번 노드에서 시작해서 0번 노드에서 이어지는 노드들을 모두 큐에 넣은 후에 방문 했다는 것을 체크해 둡니다.만약, 99번 노드가 나온다면 바로 연결되어있다는 것으로 끝내주면 됩니다.하지만 큐가 빌 때까지 99번 노드를 찾을 수 없다면, 시작 노드에서 끝 노드로 갈 수 없다는 것이 될 것입니다! 문제를 하나 풀어보겠습니다. 큐에 시작점인 0을 넣고, 0번을 방문 했다고 체크 합니다. 큐의 가장 위에 있는 0번 노드가 시작 노드가 됩니다.0번 노드가 가리키는 1번과 2번 노드를 큐에 ..

반응형