어셈블리어 역시 사람이 이해하기 어려워 사람의 언어로 구현한 고급언어가 생겨나게됨

컴파일 : 고급언어(C/C++/Java)를 기계어로 변환하는 과정

플랫폼 독립성 : 운영체제나 하드웨어에 상관없이 JVM (Java Virtual Machine)만 있다면 동일하게 실행될수있는 특성

이게 가능한 이유는 바이트 코드가 있기 때문인데,

바이트 코드 : 가상머신이 이해할수있도록 중간 코드로 컴파일한 것

원시코드에서는 컴파일되지만 가상머신에서 실행될땐 인터프리터로 해석

컴파일러(compiler)

전체 파일을 스캔하여 한꺼번에 번역한다. 초기 스캔시간이 오래 걸리지만, 한번 실행 파일이 만들어지고 나면 빠르다. 기계어 번역과정에서 더 많은 메모리를 사용한다. 전체 코드를 스캔하는 과정에서 모든 오류를 한꺼번에 출력해주기 때문에 실행 전에 오류를 알 수 있다. 대표적인 언어로 C, C++, JAVA 등이 있다.

인터프리터(interpreter)

프로그램 실행시 한 번에 한 문장씩 번역한다. 한번에 한문장씩 번역후 실행 시키기 때문에 실행 시간이 느리다. 컴파일러와 같은 오브젝트 코드 생성과정이 없기 때문에 메모리 효율이 좋다. 프로그램을 실행시키고 나서 오류를 발견하면 바로 실행을 중지 시킨다. 실행 후에 오류를 알 수 있다. 대표적인 언어로 Python, Ruby, Javascript 등이 있다.

자바언어 -> 바이트 코드로 컴파일 -> JVM의 인터프리터를 사용해 기계어로 번역

그러면 가상머신에서 인터프리터로 해석하는데 C/C++보다 느려지는거 아닌가?

그래서 나온게 JIT(Just In Time) 컴파일

인터프리터에서 같은 부분을 계속 해석하는것 대신 캐싱해 사용한다

백준을 풀면서 항상 시간초과나오면 PYPY써라 했었는데 PYPY도 JIT컴파일을 사용하여 인터프리터라 느리다는 단점이 있던 파이썬을 개선한 언어였다

참고 : https://www.youtube.com/watch?v=OxvtGYvVkRU

JDK (Java Development Kit) 자바 프로그램을 개발 및 실행 - 개발자 - 자바 컴파일러, JRE 포함

JRE (Java Runtime Environment) - JVM, 라이브러리 클래스 포함 자바 프로그램을 실행만 - 사용자

끼야호

골드까지 달려보자고..!

특정값을 입력받아 1,2,3의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램이다

3가지로 나누어보자

마지막에 1을 더해 특정값으로 만드는경우는 n-1을 만드는 경우의 수와 같다 마지막에 2를 더해 특정값으로 만드는경우는 n-2를 만드는 경우의 수와 같다 마지막에 3을 더해 특정값으로 만드는경우는 n-3을 만드는 경우의 수와 같다

n = int(input())


memo = {1:1, 2:2, 3:4} # 1,2,3을 만들수있는 경우의수

def plus(n):
  if n in memo:
    return memo[n]
  memo[n] = plus(n-1) + plus(n-2) + plus(n-3)
  #마지막에 1,2,3을 더하는 경우
  return memo[n]


for i in range(n):
  a = int(input())
  print(plus(a))

해당 글은 직접 공부한 내용을 정리한 글입니다 어설픈 코딩실력은 너그럽게 봐주시고 조언은 항상 환영입니다..!

이해를 위해 전 문제를 보고오자!

11726번 2xn 타일링

으악 이번에는 2x2타일이 하나 추가되었다

그렇다면 2x2를 만들때는

이렇게 3가지 경우가 있으니 초기값을 수정해주자

2xn의 직사각형을 채우는 경우의 수는 마찬가지로 2x(n-1)의 경우와 2x(n-2)경우에서

두가지를 붙이는 경우의수가 존재하기때문에 (2x1타일 두개는 2x(n-1)연산에 포함) *2를 해주면 되겠다

nemo = {1:1,2:3} #초기화값

def nemo2(n):
  if (n in nemo):        #전에 계산한경우 결과값 리턴
    return nemo[n]

  nemo[n] = nemo2(n-1) + nemo2(n-2)  * 2        #2x(n-2)에서 2x2모양이 두개이므로  *2
  return nemo[n]


n = int(input())
print(nemo2(n) % 10007)

해당 글은 직접 공부한 내용을 정리한 글입니다 어설픈 코딩실력은 너그럽게 봐주시고 조언은 항상 환영입니다..!

2xn 사이즈의 직사각형을 1x2, 2x1사이즈의 타일로 채우는 경우의수를 구하는 문제이다

먼저 2x1 직사각형을 채우는 경우의 수는 몇개일까?

2x1 사이즈의 블럭 하나를 놓는 경우뿐이다

그렇다면 2x2 직사각형은?

1x2사이즈 두개, 2x1사이즈 두개 이렇게 2가지 경우가 있다

그다음으로 2x3은?

2x1사이즈에 2x2를 만드는 두가지 방법을 붙이거나

2x2로 만들어진 직사각형에 2x1을 붙이는 방법이 있다!

그렇다면 2xn의 직사각형을 만드는 경우의 수는

2x(n-2)직사각형에 2x2사이즈를 더해 만든경우와

2x(n-1)직사각형에 2x1사이즈를 더해 만든 경우 두개를 합하면 나오지 않을까?

nemo = {1:1,2:2}  # 2x1,2x2 사이즈를 만드는 경우의수

def nemo2(n):
  if (n in nemo):    #전에 계산한 적이 있다면 결과값 리턴
    return nemo[n]

  nemo[n] = nemo2(n-1) + nemo2(n-2)        #2x(n-2)에서 1x2 사이즈 블럭두개
  return nemo[n]                        #2x(n-1)에서 2x1 사이즈 블럭하나


n = int(input())
print(nemo2(n) % 10007)

어? 그런데 2x(n-2)에서 블럭을 2x1두개랑 1x2두개를 붙이는 경우 두개아닌가요??

그 경우는 2x(n-1)에서 2x1사이즈 블럭하나 붙인 경우에 포함되어있다!

마치며

굳

해당 글은 직접 공부한 내용을 정리한 글입니다 어설픈 코딩실력은 너그럽게 봐주시고 조언은 항상 환영입니다..!

오늘 풀어본 문제는 이친수이다

문제에도 나와있듯이 두가지 조건이있다

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두번 연속으로 나타나지않는다.

그러면 우리는 어떻게 n자리수의 이친수를 구해야할까?

두가지로 나누어서 계산해보면 된다 n-1자리수에서의 1로 끝나는 수 와 0으로 끝나는 수의 개수를 알아야한다.

이 이유는 1로 끝나면 조건 2에 의해 또 1이 나오지 못함으로 무조건 0이 붙는다 0으로 끝나게 되면 1과 0 둘다 뒤에 올수있다!

memo = {1:[1,0,1], 2:[1,1,0]}   #1,2자리수의 이친수

def lee(n):   #이전에 계산한 적이 있다면 바로 결과 리턴
  if n in memo:
    return memo[n]

  tmp = lee(n-1)
  memo[n] = [0,0,0]


  memo[n][0] = tmp[1] *2 + tmp[2]   
  #결과값은 마지막수가 0일때 *2 + 마지막수가 1일때 / 0일때는 1과 0이 둘다올수있기 때문에 *2
  memo[n][1] = tmp[1] + tmp[2]
  #마지막숫자가 0일때의 경우는 0으로 끝난수와 1로끝난수의 더하기
  memo[n][2] = tmp[1]
  #마지막숫자가 1일떄의 경우는 0으로 끝난 수 밖에 없다

  return memo[n]
print(lee(int(input()))[0])   #결과 출력

각 리스트값의 의미는 n자리수의 이친수개수,0으로끝난 이친수, 1로끝난 이친수를 뜻한다!

마치며...

동적프로그래밍을 처음엔 이해하기 어려웠지만 지금이제 문제푸는게 재밌네용 Dp문제 푼거 두개더있는데 문제푸느라 글을 못올렸다... ㅋㅋㅋ

오늘 연등때 올릴게요!!

아 맞다 실버3찍음 ㅋ

해당 글은 직접 공부한 내용을 정리한 글입니다 어설픈 코딩실력은 너그럽게 봐주시고 조언은 항상 환영입니다..!

기껏해야 평일 개인정비 1시간 반이랑 주말이 전부다 하지만 주말엔 놀아야하고 코딩공부하는게 쉽진않은거같다

사실 지금까지 군복무하면서 폰만보고 놀았던거같은데

주변을 보면 열심히하는 사람들이 많다

선임분중에는 매일 주말도 포함해서 개인정비/연등 시간을 통해 자격증공부

동기중에는 블로그를 4월에 시작해서 꾸준하게 포스팅한 결과 엄청 유명해졌더라구

그래서 나도 저렇게 열심히 해봐야겠다 라는 생각이들어 일주일에 한번이라도 본인이 푼 알고리즘 문제를 설명하는것처럼 글을 써볼 생각!

아무튼 화이팅..!

오늘 푼 문제는 DP라고 불리는 동적 프로그래밍 문제이다

복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법

정의는 위와같은데, 피보나치 수열을 보고 이해해보자

첫항과 두번쨰 항을 각각 1로 두고 n이 3이상일때는 그전항과 전전항을 더하는 수열이다

그럼 F3는 결과가 어떻게 나올까?

위에 식으로 보면 F3 = F2 + F1 에서 F1과 F2는 1이므로 F3은 2가된다

이렇게 F4 = F3 + F2 F5 = F4 + F3 ...

계속 이어나가게된다

그러면! 이수열을 코드로 짜보자

def fib(n):
    if n <= 1:    #F1은 1
        return 1
    elif n == 2:    #F2도 1
        return 1
    else:
        return fib(n-1) + fib(n-2) #Fn = Fn-1 + Fn2 / n이 3이상일때만 연산


n = int(input("n을 입력하세요: "))
print(f"fib({n}) = {fib(n)}")

이렇게 되면 예를 들어 n이 5이면 fib(3) + fib(4) 를 계산해야하므로 fib(3)과 f(4)값이 연산되어 더한후 fib(5)의 값이 나오게된다

fib(5)라는 계산을 fib(3)과 fib(4)로 나누어서 계산하고 fib(3)과 fib(4)도 나누어서 계산하고

이것이 동적 프로그래밍이다.

하지만 위코드에는 문제점이 있다..!

무엇이 문제일까??

위에서 말했다 싶이 fib(5)라는 항을 fib(4)와 fib(3)을 더한 값으로 나눠서 계산한다고 했다. 그러면 그 다음 항인 fib(6)은???

fib(6)도 fib(5)와 fib(4)의 값을 더한것으로 적용되는데 fib(5)와 fib(4)를 다시 처음부터 계산해야하는 것이다!!!

위그림과 같이 특정 함수를 호출하면 똑같은 계산이 빈번한걸 볼수있다

그러면 또 fib(3)다시계산하고... fib(2)도 다시계산하고... 코드의 실행시간이 기하급수적으로 늘어나게된다

그럼 어떻게 하면 될까??

방법은 간단하다 우리가 한 계산을 저장하면 된다!

저장하면 굳이 계산을 다시 할 필요가 없기 때문이다

우리는 이걸 "Memoization"이라고 한다

memo = {1: 1, 2: 1}  # F1과 F2의 초기값을 설정

def fib(n):
    if n in memo:  # 이미 계산된 값이 있으면 반환
        return memo[n]
    else:
        memo[n] = fib(n-1) + fib(n-2)  # 값이 없으면 계산 후 저장
        return memo[n]

n = int(input("n을 입력하세요: "))
print(f"fib({n}) = {fib(n)}")

이렇게 메모를 이용하면 실행시간이 줄어들게 된다!

백준 1003번 피보나치 함수

간단하게 말해서 위 문제는 특정 함수가 실행되면 그 함수의 값을 계산할때 fib(0)과 fib(1)이 사용되는 횟수를 반환하게 하라는 문제이다

memo = {0:[0,1,0],1:[1,0,1]} #초기값

def fib(n):
  if n in memo:   #전에 계산된 값이라면,
    return memo[n]    #바로 그값을 리턴

  else:   #처음 계산하는 것이라면,
    tmp = fib(n-1) + fib(n-2)   #두 값과 실행횟수를 리스트에서 넣어
    memo[n] = [0,0,0]

    #메모에 넣어준다
    memo[n][0] = tmp[0] + tmp[3]    #tmp 인덱스 0과 3은 함수계산값
    memo[n][1] = tmp[1] + tmp[4]    #tmp 인덱스 1과 4는 각함수의 0실행횟수를 더함
    memo[n][2] = tmp[2] + tmp[5]    #tmp 인덱스 2과 5는 각함수의 1실행횟수를 더함

    return memo[n]


n = int(input())
for i in range (n):
  n1 = int(input())
  print("%d %d"%(fib(n1)[1],fib(n1)[2]))

나는 메모설정을 키값에는 fib(n)의 n값을, 벨류값에는 리스트로 [결과값,0출력횟수,1출력횟수] 순으로 설정했다

마치며...

알고리즘 공부를 시작하면서 동적 프로그래밍 먼저 풀고있는데 처음 이해할때에는 머리가 너무아팠는데 또 이해하고 보니까 괜찮을거같기두

해당 글은 직접 공부한 내용을 정리한 글입니다 어설픈 코딩실력은 너그럽게 봐주시고 조언은 항상 환영입니다..!

오늘도 열심히 공부하면서 Velog작성할 내용을 정리하던 도중...

오류를 발견하게 되었다!

❗️ 문제점

잘 모르겠지만 들여쓰기에서 오류가 난듯하다...😮‍💨

🔑 해결방법

Mac : command + shift + p Window : Control + shift + p

들여쓰기를 공백으로 변환 (Convert Indentation to Spaces)

🔒 원인

Velog에서 작성한 코드를 복붙해서 VSCode로 옮겼는데

붙여놓는 도중 띄어쓰기(Space)와 탭(TAB)이 혼동되었던것 같다 🥲

📘Reference

https://stackoverflow.com/questions/52224313/unexpected-indentation-in-visual-studio-code-with-python

안녕하세요 처음 글써보는 인공지능공학과 2학년 학부생입니다!

시작하게된 계기

대학생이 되고 드디어 어렸을때부터 관심있어 했던 코딩을 본격적으로 배우게되었는데,

역시나 취미로 할때보다 배우는 양도 많고, 어려운 문제도 많이 접하다보니 프로그래밍의 기본적인 내용조차 까먹거나 헷갈려하는 나를 발견... 귀찮아서 안하는경우도...

그래서 대학생활하면서 진행했던 프로젝트, 코드쓰면서 나온 오류내용등 여러가지를 작성해보려구 Velog를 개설했어요! ( 주로 쓰는 언어는 Python )

일단 하루에 한문제씩 풀었던 백준문제를 올리는걸 목표로!! 또 요즘 노션도 써보고싶긴한데 너무어려워서 ㅠ

아무튼! 열심히,꾸준하게 써볼테니 앞으로 잘부탁드립니다..!

print("안녕하세요!")

System.out.println("앞으로 잘부탁드려요 :D");