문제 원문: https://www.acmicpc.net/problem/1003

 

1003번: 피보나치 함수

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

www.acmicpc.net

 

관련 개념: 피보나치 수열과 재귀 (수학 기초내용이라 접음, 수학적으로 잘 모르겠으면 보세요)

더보기

수열이란 수의 나열로 이해하면 좋다. (고교 수학 과정에 포함)

수학적으로, 피보나치 수열은 a₀ = 0, a₁ = 1의 초기값을 가지고 앞의 두 수를 더하여 뒤의 수를 구하는 수열이다. 그러니까 a₂ = 1이고, a₃ = a  + a₁ = 2이다.

이를 일반화하여 점화식으로 쓰면 a = aₙ₋₁ + aₙ₋₂로 표현할 수 있다.

 

이 점화식을 재귀기법을 활용하여 코드로 표현하면 문제 원문의 함수처럼 된다. 점화식을 그대로 코딩한 것이기 때문에 사람이 이해하기는 쉬우나 숫자가 커질수록 계산횟수가 기하급수적으로 커진다. 일반적으로 43 이상의 숫자는 연산 결과를 보기 어렵다.

 

제출 답안: http://boj.kr/e9d51a6ca6ff4f969254b1a92353c34c

l = [None] * 41
def fibo(n):
    if n == 0:
        l[0] = [1, 0]
    if n == 1:
        l[1] = [0, 1]
    if l[n] == None:
        l[n] = [fibo(n-1)[0] + fibo(n-2)[0], fibo(n-1)[1] + fibo(n-2)[1]] 
    return l[n]

t = int(input())
for i in range(t):
    a = fibo(int(input()))
    print(a[0], a[1])

 

해설:

재귀 방식 피보나치 함수에서 fibonacci(0)과 fibonacci(1)이 몇 번 출력되는지 구하는 문제이다.

 

사용되는 피보나치 함수 코드를 주므로 재귀에 대한 개념이 있다면 문제 이해가 어렵지 않다.

다만 입력 숫자의 범위는 40 이하이나 제한시간이 0.25초이기 때문에 메모이제이션 기법을 사용하지 않으면 시간초과가 뜬다. 그래서 문제 분류가 다이내믹 프로그래밍으로 되어있다.

 

메모이제이션(memoization)이란, 메모리에 저장한다는 뜻으로 컴퓨터가 동일한 연산을 많이 반복할 경우 동일 연산의 결과값을 저장해두고 활용하는 것을 말한다. 빈 배열을 미리 선언해두고 계산할 때 해당하는 값이 있는지 체크해서 없을 때만 새로 저장하면 된다.

 

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

[파이썬] 백준 2941: 크로아티아 알파벳  (0) 2023.07.26
머릿말  (0) 2022.12.07

문제 원문: https://www.acmicpc.net/problem/2941

 

2941번: 크로아티아 알파벳

예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z=

www.acmicpc.net

 

크로아티아 알파벳의 개수를 새는 문제다. 푸는 방법은 여러 가지가 있을 것으로 생각된다.

 

고려해야할 문자는 다음과 같다.

크로아티아 알파벳 변경
č c=
ć c-
dz=
đ d-
lj lj
nj nj
š s=
ž z=

 

 

제출 답안: http://boj.kr/8d45aab67c1345fa961657304e168d09
s = input()
a = len(s) - s.count('-') - s.count('=') - s.count('lj') - s.count('nj') - s.count('dz=')
print(a)

 

해설:

문자열 처리에 대해 연습할 수 있는 문제다.

여러 문자로 표현되는 알파벳들을 한 글자로 계산하여 글자수를 세어야 한다.

 

이론적으로는 표에 해당하는 알파벳을 모두 세어서 빼주면 될 거 같지만, 표현 상으로 dz= 안에 z=가 포함되기 때문에 이를 고려하여 문자열을 처리하여야 한다.

 

이 문자들은 몇 가지 규칙이 있다.

1. '=' 혹은 '-'를 사용 (lj, nj 제외)

2. dz=를 제외하면 2글자 표기

 

특정 문자들은 '=' 혹은 '-'를 포함하기 때문에 '='와 '-'를 세어서 글자수에서 뺄셈하여 모두 처리하였다. 이후 남는 알파벳은 lj, nj, dz=(혼자 3문자를 사용하기 때문에 한번 더 체크)다. 각각을 count() 함수로 세어 뺄셈하였다. 출력하면 끝.

 

 

첨언: 

replace() 함수를 이용할 수도 있으나 이때는 dz=와 z= 중 dz=를 꼭 먼저 처리해야한다. count() 함수를 이용한 이유는 처리 순서에 구애받지 않기 때문이었다. 

 

 

풀이 날짜: 20220312

'알고리즘 문제풀이' 카테고리의 다른 글

[파이썬] 백준 1003: 피보나치 함수  (0) 2023.08.04
머릿말  (0) 2022.12.07

ModuleNotFoundError: No module named 'BeautifulSoup'

ModuleNotFoundError: No module named 'bs4'

 

구글에서 자동완성될 정도로 흔한 오류인듯

 

과제 때문에 크롤러 만들 일이 생겨서 beautifulsoup4를 설치했다. 

(pip install bs4 명령어 사용, pip은 최신 버전)

 

인식을 못한다.

error screen

 

다만 이상한 게 spyder 상에서 자동완성으로 bs4나 beautifulsoup가 뜬다...... 어딘가에 설치가 되어있긴하다는 말이다.

 

시도한 해결책:

 

- pip uninstall bs4 beautifulsoup4 후 재설치 (일반적으로 이렇게 하면 된다는 블로그 글이 많은데 안 됨)

- python 기본 workspace로 파일 옮긴 뒤 실행 (해결 안 됨)

- python path 경로로 직접 와서 설치 (해결 안 됨)

- python 버전 변경 (1차적 원인)

- 환경 변수 재설정 (해결 안 됨)

 

원인:

1. python 버전이 여러 개

설치된 python 버전이 여러개인 것이 문제가 되었다.

 

내 경우 python 39와 python 311버전을 가지고 있는데, pip install이 모듈을 자동으로 311의 lib에 설치했다.

내가 평소에 쓰는 버전은 39. ide에서 311로 바꿈

 

*비슷한 케이스 (python 버전이 여러개): https://www.inflearn.com/questions/442380/bs4%EC%97%90%EB%9F%AC

 

다만 이것만 해서는 소용 없었음, 혹시나 해서 package의 절대경로를 환경변수 path에 추가해봤는데 이것도 안 됨

 

(해결 중... 일단 다른 pc로도 시도해볼 예정) 

 

 

급하게 c++로 http 구현을 할 일이 생겨 boost library를 사용하기로 함

 

파일 경로 확인 다 함

IncludePath에 있음

빌드해야 쓸 수 있는 라이브러리를 포함시키지 않았음

 

그럼에도 불구하고 No such file or directory가 뜸, json 뿐만이 아니라 boost lib 모든 파일이 인식이 안 됨

 

cygwin

 

시도해본 방법:

- vscode 프로퍼티 및 settings json 수정

- 헤더 파일 위치를 옮겨서 그 경로대로 import (헤더 간 의존성으로 인해 어려움)

- vscode 문제인가 싶어 cygwin으로 옮겨봄 (아닌 걸로 판명)

 

해결법: 아직...

증상

bat 파일 실행 후 vcpkg-configuration.json 과 vcpkg.json 이 없음

 

vcpkg가 classic style이라 발생하는 오류 같음 (baseline을 필요로 함)

 

미해결

 

git pull과 vcpkg update의 무한 루프
update and rerun 하면 may resolve 될 거라는데 gitignore에 포함된 항목이라 안 됨

 

해결 방법:

 

 

시도해본 방법:

- installed 폴더 삭제 후 재설치

- 전부 삭제 후 재설치

- 수동으로 vcpkg-configuration.json, vcpkg.json을 만들기 (empty file이라 오류)

- 수동으로 vcpkg-configuration.json, vcpkg.json을 만들기 (그럴듯하게 만들었는데 git fetch 못해서 오류남)

- vcpkg update (json 파일 없어서 불가능)

 

참고할 블로그

https://decovar.dev/blog/2022/10/30/cpp-dependencies-with-vcpkg/

 

Managing dependencies in a C++ project with vcpkg | Declaration of VAR

 

decovar.dev

 

*vcpkg 설치에 참고한 블로그: https://cheongpark.tistory.com/15

 

백준 문제 풀었던 거 올립니다. 그게 다 끝나면 프로그래머스나 leetcode도 올립니다.

 

개인적으로 했던 문제설명이나 스스로 만들었던 자료들을 버리기 아까워서 정리해봅니다.

직접 코딩하거나 핸드아웃 제작했던 자료들만 공개하며, 다른 루트로 제공받은 자료는 공개하지 않으므로 비밀유지 등에 어긋나지 않습니다.

 

이 탭은 기초 단계, 초등생도 이해할 수 있는 코딩을 목표로 합니다. 

 

최근 2년 간 강남에 있는 코딩 학원에서 파트타임으로 일을 하다가, 슬슬 제대로 취업 준비를 해야겠다 싶어서 사직 요청을 했습니다.

 

학원 일을 하면서 커뮤니케이션이라던가 이런저런 대처 능력은 많이 늘었지만 아무래도 어린 학생 대상 강의고 저는 대학생이었다보니 깊은 내용으로 들어갈 일이 드뭅니다.

 

수업을 위한 공부와 관심분야에 대한 공부를 둘 다 하기가 어렵더라고요. 사실 전공을 살린 활동을 많이 한 것도 아니기도 하고요.

 

 

그래서 일단 토이프로젝트로 3학년 때 했던 안드로이드 프로젝트 팀플 코드를 활용해서 앱을 완성하기로 했습니다.

작업 순서는 다음과 같습니다. (새로 적용할 방식이 있다면 바뀔 수 있습니다. 2022-12-02 기준) 

 

0. 제출했던 최종 보고서, 기동 영상 분석, git fork 등

1. 필수 구현했어야 하지만 시간부족/다른 팀원 파트 등 미구현되었던 파트 구현

2. 시간 문제로 제외되었던 편의 기능 구현

3. 시중 어플리케이션과 차이 나는 부분 분석

n. 중간에 새로운 개념이 있다면 보강하며 진행

 

 

코틀린 공부도 해봐야하나 싶다가도, 그래도 이미 알고 있는 자바로 할 수 있는 곳까지 완성해보는 경험이 다른 것을 배울 때도 도움이 될 것이라고 판단했습니다.

 

아직 인수인계 중이기 때문에 일지 업데이트는 12월 말부터 시작될 것 같습니다.

                    JSONObject json = thread.getStatus();
                    //json 파싱해서 ui에 삽입
                    if(json != null){
                        tempNow.setText(json.optDouble("currentTemp", -1.0));
                        humidNow.setText(json.optDouble("currentHum", -1.0));
                    }

(내 코드 일부)

 

플랫폼: android studio

 


오류 현상: 

다른 스레드로부터 json 오브젝트를 받아와서 ui를 갱신하는 코드를 작성 중에, 뜬금없이 setText() 메소드의 인자에 오류가 났다. 살펴보니 int로 casting을 하라고 한다. 편집기가 내 의도와 다르게 인식한 거 같다.

 

오류 화면


사유:

setText() 메소드는 인자로 resId 값(int 형), char 배열, CharSequence 인터페이스 등을 받을 수 있다.

 

한편 resId 값이 아니라 직접 int 값을 출력해야하는 경우가 있고, 나처럼 double 형을 출력해야하는 경우가 있을 것이다.

 

내 경우 double 형의 데이터를 문자열 캐스트 없이 입력했고(...) double은 숫자 자료형이라 편집기에서 int로 캐스트 하는 것이 내 의도에 맞다고 판단한 것 같다.

 


해결책:

int, double 등 숫자 자료형인 경우 모두 적용된다.

 

1. String.valueOf() 메소드 사용

string 데이터로 바뀐다. 아주 잘 됨.

 

2. 빈 문자열과 concatenate해서 인자로 넣는다.

setText("" + 1.0) 등의 형식으로 작성하면 오류가 나지 않는다. 단순 데이터 외에 출력할 내용이 더 있다면 유용하게 쓸 수 있는 방법.



그외 시도 방법: .

+ Recent posts