오늘의 알고리듬 문제풀이

Intro

• 오늘도 알고리듬 2문제를 풀었다. 첫번째 문제는 이진수 더하기였고 두번째문제는 연속된 수의 합이었다. 내가 시도한 것들과 내 생각의 흐름을 보기위해 두문제를 어떻게 접근했는지 남기고자한다.

이진수 더하기

• 두 이진수가 String으로 주어지고 이 둘의 합을 구해 이진수 String으로 return 해주면되는 간단한문제.
• 내가 접근한방식은 컴퓨터에서 shift해주는것처럼 나도 그렇게 구현해보고싶어서..! 일단, 두 이진수의 길이가 같은지 체크 후 다르다면 0으로 채워준다. 그런데 이렇게되면 제대로된 이진수 계산이 성립하지않는다. 짧은길이의 이진수 string값을 뒤집어줘야 정상적으로 계산값이 출력될것이다. 이 작업 후 두 string의 값을 length의 마지막에서부터 가져와 비교한다. 그런데 shift가 일어날 상황도 생각해야하므로 shift라는 bool변수를 선언하고 shift가 일어날때 true로 해준 후 true -> 1, false -> 0 으로 바꿔서(C#에서는 자동으로 숫자로 바뀌던데 kotlin에서는 안되더라..) string값을 합치면 아래와같은 경우의 수가 생긴다.
  • "000" -> "0" (isShift = false)
  • "001" -> "1" (isShift = false)
  • "010" -> "1" (isShift = false)
  • "011" -> "0" (isShift = true )
  • "100" -> "1" (isShift = false)
  • "101" -> "0" (isShift = true )
  • "110" -> "0" (isShift = true )
  • "111" -> "1" (isShift = true )
• 맨 마지막 수가 bitshift여부이고, 이것에따라 해당자리수의 값을 0으로할지 1로할지 결정한다. 그리고 이렇게 계산하다가 자리수가 올라가게 될 경우의 수까지 체크해 추가해주면 끗! 이라고 생각했는데.. 내가 경우의 수를 다 파악하지 못해서 프로그램이 정상동작하지 않았다. 그래서 결국 그냥 string값을 10진수로 바꾸어 계산한 후 이것을 2진수로 바꾸고 그것을 .toString()해서 해결했다.
• 그 후 이참에 2진수에대해 한번더 정리해보자 하다가 발견한 좋은 자료가있었다. 여기에서는 컴퓨터가 2진수를 사용하고 논리회로를 사용하여 연산을 수행하는 것을 설명하는 내용이었다. 오랜만에 1학년 수업시간으로 시간여행하고온 기분이다 ㅎㅎ

연속된 수의 합

• 두개의 정수 num 과 total이 주어진다. num은 연속된 숫자의 개수이고, total은 연속된 숫자의 합을 뜻한다. 연속된 숫자를 오름차순으로 배열에 담아 return하는게 문제이다. 예를들어 total이 12이고 num이 3일때 연속된 세 숫자는 [3,4,5]가 되는것이다.
• 처음에 어떻게 접근할까 고민했다. 첫번째시도는 num과 total을 나눠 뭔가 공통된 규칙을 찾아보는것이었다. 이건 실패! 안나온다.
• 두번째로 연속된 숫자의 합에관한 공식을 찾다가 아래와같이 정리되었다.
  • total = a + (a+1) + (a+2) + ... (a + n)
  • total = num a + ((num (num - 1)) / 2)
  • a = total - (total - ((num * (num - 1)) / 2)) / num
• 왜 이렇게 구했냐면..! 연속된 수라는것은 결국 어떤 수 a 에 1씩 계속 더해지는거니까 위와같이 정리가 가능했고, 여기서 a 뒤에 늘어나는 숫자는 결국 num - 1만큼 더해지는것을 알 수 있다(직접 종이에 써보면서하면 이해가 쉬운데 여기에 글로 적으려하니 어렵게 느껴진다..)
• 이렇게 찾은 a를 num번 만큼 더해주어 IntArray에 넣어주면 끗!

Outro

• 내가 접근한 방법을 이렇게 정리할때 내 생각을 내가 직접 볼 수 있어서 참 좋다.
• 풀면서 점점 더 컴퓨터스럽게 생각이 바뀌어가길 기대해본다..!