알고리즘을 좋아하는 나

k-1층의 1~b호 까지의 사람들이 k층 b호에 살아야 된다.

0층 i호에는 i명이 산다.

배열이

1 2 3 4 5

1 3 6 10 15

이런식으로 만들어진다.

위에서 부터 0층 1층 으로 계산했을때

d[i][j] = d[i-1][j] + d[i][j-1] 이다.

그래서 처음 입력받기 전에 초기화해주고 

입력받는 값으로 배열에 대입해서 출력하면 된다.

H * W 호텔에서 N번째 사람이  어디에 들어가는지 구하는 문제.

첫 번째 문제를 푼 아이디어는

(N/H+1)*100+N/H+1

이였다. 

일단 내가 W에 대해 아무것도 작성하지 않은 이유는 굳이 W까지 해서 계산할 필요 없이 나눈값 + 1이 들어가기 때문이다.

근데 이 풀이는 N과 H가 같으면 출력이 잘못된다.

그래서 반복문으로 N에 H를 빼면서 W를 1씩 더해주면서 호수를 구해줬다.

코드를 보는게 이해가 더 쉽게 될 것이다.

1 1

2 1 1

3 1 1 1

4 1 2 1

5 1 1 2 1

6 1 2 2 1

7 1 1 2 2 1

이동 거리는 이런식으로 된다.

idx    이동횟수

1         1

2        2

3        3

5        4

7        5

y에 이동해야 되는 거리를 넣어두고

pos에 현재 위치를 담았다.

처음에는 무조건 1을 이동해야 돼서 초기값이 1이다.

while loop을 돌때 i++/2를 해준 이유는 

9를 예로들면

1 2 3 2 1 인데

pos의 값이

1

while loop 시작

2

3

5

7

10

끝

이다.

i의 값을 구하면 5다.

결론적으로는

1 2 3 2 1

인것을

1 1 2 2 3 로 하는거다.

3을 예로들면

1 2 3 이 된다.

1 1 1 ㅇㅇ

끝.

다른 블로그를 많이 참고했다.

3개의 풀이가 나왔다.

1. 시간초과

하나씩 다 더해줌

2. 런타임

2차원 배열을 만들어서 무게별로 나누고 또 거기에서 컬러별로 나눴음

2000 * 2e5 * 4 = 1G가 넘어가서 런타임 에러

3. 정답

블로그를 조금 참고했지만, 짜고나니 거의 똑같게 나옴...

total 스코어 idea를 참고함.

문제를 2가지 방법으로 풀었다.

첫 번째 방법은 노트를 없이 풀었는데, 문제를 잘 못 이해해서 시간초과가 났고,

두 번째 풀이는 메모이제이션을 이용해 코드를 작성했다.

1보다는 2를 먼저 채우는 방식으로 짰다.

Segment Tree

BOJ에 있는 블로그를 보고 공부했다.

일단 노트에 트리를 그리면서 어떤식으로 작동하는지 알게됐고, 아직 익숙하지 않다.

재귀함수 덩어리.

음 보물찾기 문제.. BFS

BFS를 사용하며 visited를 잘못써서 시간초과가 났었고, for문을 break하는걸 넣어놓고 안빼서 계속 틀렸었다.

2005년도 초등생은 BFS를 할줄 안다니.. 대단하네

알고리즘 스터디 자료를 준비중에 ADT라는 용어를 접했다.

ADT는 Abstract-Data-Type이다.

말 그대로 추상 자료형.

Wallet이라는 자료형을 선언했다.

그 Wallet을 기반으로 연산의 종류가 있을것이다.

그것도 자료형 정의의 일부다.

자료의 ADT는

기능들이다.

기능들 말고도 구조체의 정의도 넣을 수 있다.

근데 ADT에는 필요한 정보들만 넣는것이 좋다.

리스트

• 순차 리스트
• 연결 리스트

둘의 ADT가 같을 수 있다.

ADT에 표준은 없다.

생각은 모두 자유롭게 할 수있고, 그것을 코드로 옮길 수 있다.

위 둘의 리스트의 공통점은

선형구조다.