본문 바로가기

전체보기

[Level 2] 6. 숫자의 표현 6. 숫자의 표현 Algorithm - Level 2 - 풀이 복잡해보이지만 생각을 단순하게 하면 쉽다. 1. 3, 5, 7, 9 ... 의 숫자들은 1+2, 2+3, 3+4, 4+5 ... 와 같이 표현이 가능하다. -> 즉 2로 나눴을 때 나머지가 1이면 다음과 같은 표현이 가능하다 (단, 1은 제외) 2. 1+2+3, 2+3+4, 3+4+5 와 같은 표현이나, 1+2+3+4, 1+2+3+4+5와 같은 식을 표현하기 위해 이중 for문을 사용한다. 3. for문의 효율성을 위해 입력 n의 값의 절반까지만 접근한다. ( 이보다 큰 수는 연속되어 표현이 불가능하다.)123456789101112131415161718192021222324252627282930313233#include #include #in..
[Level 2] 5. 땅따먹기 5. 땅따먹기 Algorithm - Level 2 - 풀이 1. 위 문제는 이전에 풀었던 가장 큰 정사각형 찾기 문제와 풀이가 같다. -> Dynamic Programming, 점화식을 이용 2. 입력과 같은 크기의 배열을 선언하며 첫 행의 원소들은 입력과 같다. -> 따라서 입력의 1행부터 접근 3. 해당 배열을 DP라고 칭하며, DP는 입력값의 누적이 저장되는 배열이다. 4. 입력 1행에 있는 원소들을 DP의 0행에 있는 원소들 중 같은 열에 존재하지 않고 가장 큰 값을 찾아 더해 DP 1행에 저장한다. -> 이를 반복한다. 5. DP의 마지막 행에 존재하는 원소들 중 가장 큰 값이 최대값이다.12345678910111213141516171819202122232425262728293031#includ..
[Level 2] 4. 다음 큰 숫자 4. 다음 큰 숫자 Algorithm - Level 2 - 풀이 1. 이진수로 변환하여 접근하기 위해 string형으로 변환하는 것이 편리 # 방법. 1 2. 연속된 1과 0의 개수가 같다면 뒤에 0을 붙인다. -> ex) 1100 = 11000 3. 앞 숫자가 0이고 뒤 숫자가 1이면 그 위치를 바꿔준다. -> ex) 1001 = 1010 4. 3을 만족하면서 현 위치에서 뒤, 뒤에 존재하는 숫자가 1이고 맨 뒤가 0이라면 뒤, 뒤에 숫자를 0으로 바꿔주고 맨 뒤를 1로 바꿔준다. -> 10110 = 11001 @ stoi(string, index=0, base) -> string 타입을 int형으로 변환하되, base 진수로 인식하여 변경 1234567891011121314151617181920212..
[Level 2] 3. 올바른 괄호 3. 올바른 괄호 Algorithm - Level 2 - 풀이 ( 로 시작하여 ) 로 끝나야 한다. 따라서 ) 로 시작한다면 False. 또한 ( 와 ) 는 pair 이므로 ( 혹은 ) 하나만 존재하는 문자열도 False ( 을 만나면 count를 증가시키고, ) 을 만나면 count를 감소시킨다. + 최종 count가 0이라면 올바른 괄호이며, 0이 아니라면 올바른 괄호가 아니다. + 진행 도중 count가 0보다 작다는 것은 ( 으로 시작한 것이 아닌 ) 으로 괄호를 시작한 것으로 False를 리턴한다. 123456789101112131415161718192021222324252627#include#include using namespace std; bool solution(string s){ boo..
[Level 2] 2. 가장 큰 정사각형 찾기 2. 가장 큰 정사각형 찾기 Algorithm - Level 2 - 풀이 + 다중 중첩 for 문을 이용한 풀이123456789101112131415161718192021222324252627282930int solution(vector board){ int answer; int max = board.size()==board[0].size() ? board.size() : min(board.size(), board[0].size()); int hi=-1, hj=-1; while(1){ for(int a=0; a+(max-1)
[Level 2] 1. 124 나라의 숫자 1. 124 나라의 숫자 Algorithm - Level 2 - 풀이 3진법으로 보면 0 = 4, 1 = 1, 2 = 2가 되므로, 해당 수를 3진법으로 생각하여 계산하는 것이 편리. 각 자리에 + 3, + 6, + 9를 하면서 증가하는데 이 때 3을 나눈 수가 다음 자리의 수가 된다. 재귀함수를 이용하여 풀이.1234567891011121314151617181920212223242526272829303132333435#include #include #include using namespace std; string translation(string s, int n){ int count = (n-1) / 3; int tmp = n - (count * 3); if(count >= 1) s = translat..

티스토리툴바