SyLab

안녕하세요, 오늘은 백준 알고리즘 사이트의 문제 중 9095번 1, 2, 3 더하기 문제를 풀어보려합니다. 먼저 문제부터 보겠습니다! 어떤 정수 n이 주어졌을 때, 이 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제입니다. 어떻게 접근해야할까요? 저는 DP(Dynamic Programming)로 접근해보겠습니다. 이 문제는 테스트 케이스 1개 이상이고 sub problem으로 main problem을 해결할 수 있으므로 DP로 접근하는 것이 바람직해보입니다. 정수 n이 1일 경우, 숫자 1에서 정수 1을 만들 수 있는 경우의 수는 1가지, 숫자 2에서 정수 1을 만들 수 있는 경우의 수는 0가지, 숫자 3에서 정수 1을 만들 수 있는 경우의 수는 0가지, 총 1가지 정수 n이 2일 경우, 숫자..

안녕하세요? 오늘은 백준 알고리즘 사이트의 문제 중 하나인 1463번 '1로 만들기'를 풀어보려 합니다. 문제 부터 보시겠습니다. 문제의 핵심은 주어진 3개의 연산을 사용하여 N을 1로 만들수 있는 최소의 연산 개수를 구하라는 것인데요? 어떻게 풀면 좋을까요?? 먼저 문제의 감을 잡기 위해 하나씩 써보겠습니다. 입력이 1일 때, 연산의 횟수는 0입니다. 입력이 2일 때, 연산의 횟수는 -1을 하면 되므로 1입니다. 또는 /2를 해도 1입니다. 입력이 3일 때, 연산의 횟수는 /3을 하면 되므로 1입니다. 입력이 4일 때, 연산의 횟수는 -1하면 3이고 이를 /3 해주면 되므로 2입니다. 또는 /2를 하여 2를 만든 다음, -1를 빼줘도 2이고, /2를 하여 2를 만든 다음 /2를 해도 2입니다. 자, 이..

안녕하세요? 오늘은 백준 알고리즘 사이트에 있는 문제 중 11403번 경로찾기 문제를 풀어보겠습니다. 문제부터 보시겠습니다.i에서 j로 가는 경로가 있으면 1, 없으면 0을 저장하고 모두 출력하는 문제입니다.정점의 인덱스가 0부터 시작한다고 가정하고 예제 입력1을 보시면 i가 0일 때, 1로 갈 수 있고 i가 1일 때, 2로 갈 수 있고, i가 2일 떄, 0으로 갈 수 있습니다.즉 i가 0일 때, 0, 1, 2 모두 갈 수 있습니다. 마찬가지로 나머지 행까지 모두 계산하면 예제 출력 1과 같은 맵을 얻을 수 있습니다.저는 이 문제를 DFS 알고리즘을 사용하여 풀었습니다. 갈 수 있는 정점을 모두 들리고 다시 원점으로 돌아오면 탐색이 종료되도록 구현하였습니다. 다시 원점으로 돌아온다는 개념을 visited..

안녕하세요? 오늘은 백준 알고리즘 사이트 문제 중 하나인 10448번 유레카 이론을 풀어보겠습니다. 먼저 문제를 보겠습니다. 삼각수(triangle number)는 문제에서 보여지듯이 입니다. 그리고 가우스는 최대 3개 삼각수의 합으로 모든 자연수를 표현할 수 있다고 증명하였습니다. 그리고 이 이론은 유레카 이론으로 알려져왔다고 합니다. 문제는 어떠한 수가 주어졌을 때, 이 수가 3개의 삼각수로 표현이 가능한지 알아보고 표현이 가능하면 1, 가능하지 않다면 0을 출력하는 것입니다. 제가 접근한 방식은 문제에서 주어지는 입력 K는 3에서 1000사이의 값이기 때문에 1000 이상의 값은 무의미 하다는 것입니다. 즉, 전 1에서부터 1000사이의 삼각수를 구하면 되고 그 수들을 가지고 가능한 케이스를 검사하..

안녕하세요? 오늘은 백준 알고리즘 사이트에 있는 문제 중 하나인 13235번 팰린드롬을 풀어보겠습니다. 문제 번호가 13231 이었으면 더 의미가 있었을 텐데 아쉽습니다... 하하... 농담은 이정도로 하고 본격적으로 문제를 풀어보겠습니다. 팰린드롬이란 문제에서 설명하듯이 뒤로 읽으나 앞으로 읽으나 똑같은 단어를 말하는데요, 이는 Mirror alphabet과 혼동할 수 있지만 정확히는 다른 용어입니다. 위키백과에서는 이렇게 설명하고 있네요 "회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다." 따라서 주어진 문장이 팰린드롬이면 true를 아니면 false를 출력하는 문제입니다. 제가 이 문제..

안녕하세요? 오늘은 백준 알고리즘 사이트에 게시된 문제 중 하나인 14500번 테트로미노 문제를 풀어보겠습니다. 먼저 문제를 읽어보겠습니다. 이 문제를 처음 봤을 때, 어릴 적 추억이 떠올랐습니다. 테트리스는 지금까지고 인기있는 게임인데요, 다음에 테트리스 게임과 봇을 만들어서 구현 방법과 알고리즘에 대해 포스팅하도록 하겠습니다. 간단하게 문제의 요지를 적는다면, 입력으로 NxM의 여러 숫자가 포진되어 있는 맵이 주어지고 각각의 테트로미노가 맵에 놓였을 때 생기는 테트로미노와 맵과의 교집합의 최대값을 구하라는 문제입니다. 제가 사용한 알고리즘은 다음과 같습니다. 이 문제가 다소 까다로운 이유는 이 테트로미노가 대칭과 회전이 가능하다는 것입니다. 전 이 문제를 모든 테트로미노의 모양을 맵에 대입해서 결과값..