Skip to content

Commit d6d2e35

Browse files
Do-hoDo-ho
authored
Merge pull request boost-algorithm#48 from Do-ho/Do-ho
13주차 업로드
2 parents 27d8160 + fcb5fbb commit d6d2e35

146 files changed

Lines changed: 5701 additions & 20 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎README.md‎

Lines changed: 25 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -12,26 +12,34 @@
1212

1313
## :ledger: 진행방식
1414

15-
* 매주 하나의 주제(DP, BFS 등)를 정해서 문제풀이
16-
* 매주 한명당 1문제씩 문제 선정 후 업로드
17-
* 주마다 코드 및 설명을 업로드
18-
* 자신이 사용하고 싶은 언어로 풀이
19-
* Github 활용
20-
* Repository를 Fork해온다.
21-
* 문제를 풀고 **문제 단위**로 commit을 한다.
22-
* ```src/개인 폴더/```에 업로드한다.
23-
* 각자 브랜치로 PR을 보낸다.
24-
* 코드 리뷰가 끝나고 master Branch로 Merge한다.
15+
- 매주 하나의 주제(DP, BFS 등)를 정해서 문제풀이
16+
- 매주 한명당 1문제씩 문제 선정 후 업로드
17+
- 주마다 코드 및 설명을 업로드
18+
- 자신이 사용하고 싶은 언어로 풀이
19+
- Github 활용
20+
- Repository를 Fork해온다.
21+
- 문제를 풀고 **문제 단위**로 commit을 한다.
22+
- `src/개인 폴더/`에 업로드한다.
23+
- 각자 브랜치로 PR을 보낸다.
24+
- 코드 리뷰가 끝나고 master Branch로 Merge한다.
2525

2626
## :green_book: Week Study
2727

28-
| | 1 | 2 | 3 | 4 |
29-
| ----- | :----------------------------------------------------------: | :----------------------------------------------------------: | :----------------------------------------------------: | :----------------------------------------------------------: |
30-
| 1주차 | [요세푸스 문제](https://www.acmicpc.net/problem/1158) | [에디터](https://www.acmicpc.net/problem/1406) | [풍선 터뜨리기](https://www.acmicpc.net/problem/2346) | [이진 탐색 트리](https://www.acmicpc.net/problem/2957) |
31-
| 2주차 | [절댓값 힙](https://www.acmicpc.net/problem/11286) | [위장](https://programmers.co.kr/learn/courses/30/lessons/42578) | [트리 순회](https://www.acmicpc.net/problem/1991) | [이진 탐색 트리 - 연장](https://www.acmicpc.net/problem/2957) |
32-
| 3주차 | [자동완성](https://programmers.co.kr/learn/courses/30/lessons/17685) | [문자열 압축](https://programmers.co.kr/learn/courses/30/lessons/60057) | [그룹 단어 체커](https://www.acmicpc.net/problem/1316) | |
33-
| 4주차 | [스타트 택시](https://www.acmicpc.net/problem/19238) | [자동완성 - 연장](https://programmers.co.kr/learn/courses/30/lessons/17685) | | |
34-
| 5주차 | [숨바꼭질](https://www.acmicpc.net/problem/1697) | [바이러스](https://www.acmicpc.net/problem/2606) | [토마토](https://www.acmicpc.net/problem/7569) | |
28+
| | 1 | 2 | 3 | 4 |
29+
| ------ | :----------------------------------------------------------: | :----------------------------------------------------------: | :-----------------------------------------------------: | :----------------------------------------------------------: |
30+
| 1주차 | [요세푸스 문제](https://www.acmicpc.net/problem/1158) | [에디터](https://www.acmicpc.net/problem/1406) | [풍선 터뜨리기](https://www.acmicpc.net/problem/2346) | [이진 탐색 트리](https://www.acmicpc.net/problem/2957) |
31+
| 2주차 | [절댓값 힙](https://www.acmicpc.net/problem/11286) | [위장](https://programmers.co.kr/learn/courses/30/lessons/42578) | [트리 순회](https://www.acmicpc.net/problem/1991) | [이진 탐색 트리 - 연장](https://www.acmicpc.net/problem/2957) |
32+
| 3주차 | [자동완성](https://programmers.co.kr/learn/courses/30/lessons/17685) | [문자열 압축](https://programmers.co.kr/learn/courses/30/lessons/60057) | [그룹 단어 체커](https://www.acmicpc.net/problem/1316) | |
33+
| 4주차 | [스타트 택시](https://www.acmicpc.net/problem/19238) | [자동완성 - 연장](https://programmers.co.kr/learn/courses/30/lessons/17685) | | |
34+
| 5주차 | [숨바꼭질](https://www.acmicpc.net/problem/1697) | [바이러스](https://www.acmicpc.net/problem/2606) | [토마토](https://www.acmicpc.net/problem/7569) | |
35+
| 6주차 | [쿼드트리](https://www.acmicpc.net/problem/1992) | [색종이 만들기](https://www.acmicpc.net/problem/2630) | [종이의 개수](https://www.acmicpc.net/problem/1780) | |
36+
| 7주차 | [달이 차오른다, 가자.](https://www.acmicpc.net/problem/1194) | [러버덕을 사랑하는 모임](https://www.acmicpc.net/problem/18233) | [막대기](https://www.acmicpc.net/problem/1094) | [스타트와 링크](https://www.acmicpc.net/problem/14889) |
37+
| 8주차 | [통나무 건너뛰기](https://www.acmicpc.net/problem/11497) | [신입 사원](https://www.acmicpc.net/problem/1946) | [동전 0](https://www.acmicpc.net/problem/11047) | |
38+
| 9주차 | [1, 2, 3 더하기](https://www.acmicpc.net/problem/9095) | [평범한 배낭](https://www.acmicpc.net/problem/12865) | [2×n 타일링 2](https://www.acmicpc.net/problem/11727) | |
39+
| 10주차 | [다리 놓기](https://www.acmicpc.net/problem/1010) | [계단 오르기](https://www.acmicpc.net/problem/2579) | [RGB 거리](https://www.acmicpc.net/problem/1149) | [평범한 배낭 - 연장](https://www.acmicpc.net/problem/12865) |
40+
| 11주차 | [열차 시간표](https://www.acmicpc.net/problem/12731) | [정수 삼각형](https://www.acmicpc.net/problem/1932) | [팰린드롬 만들기](https://www.acmicpc.net/problem/1254) | |
41+
| 12주차 | [ATM](https://www.acmicpc.net/problem/11399) | [회문](https://www.acmicpc.net/problem/17609) | | |
42+
| 13주차 | [미로탐색](https://www.acmicpc.net/problem/2178) | [암호코드](https://www.acmicpc.net/problem/2011) | [떡먹는호랑이](https://www.acmicpc.net/problem/2502) | [촌수계산](https://www.acmicpc.net/problem/2644) |
3543

3644
## :blue_book: Additional Study
3745

@@ -40,8 +48,6 @@
4048
| 자료구조 | [괄호](https://www.acmicpc.net/problem/9012) | [쇠막대기](https://www.acmicpc.net/problem/10799) | [스택 수열](https://www.acmicpc.net/problem/1874) |
4149
| BFS/DFS | [DFS와 BFS](https://www.acmicpc.net/problem/1260) | | |
4250

43-
44-
4551
## :raising_hand: Contributors
4652

4753
| [grap3fruit](https://github.com/grap3fruit) | [**kyu9341**](https://github.com/kyu9341) |

‎src/Do-ho/dfsbfs/boj_2178_미로탐색/README.md‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
# 미로 탐색
2+
3+
- 31782KB, 132ms
4+
- 너비 우선 탐색으로 해결
5+
6+
```
7+
import sys
8+
from collections import deque
9+
10+
D = [(1, 0), (0, 1), (-1, 0), (0, -1)]
11+
12+
N, M = map(int, sys.stdin.readline().strip().split())
13+
MAZE = deque()
14+
for _ in range(N): MAZE.append(sys.stdin.readline().strip())
15+
16+
q = deque()
17+
visited = [[False for _ in range(M)] for _ in range(N)]
18+
q.append((0,0,1))
19+
visited[0][0] = True
20+
21+
while q:
22+
tx, ty, moves = q.popleft()
23+
if(tx == N-1 and ty == M-1):
24+
sys.stdout.write(str(moves)+'\n')
25+
break
26+
for DIR in D:
27+
nx, ny = [tx + DIR[0], ty + DIR[1]]
28+
if(nx < 0 or nx >= N or ny < 0 or ny >= M): continue
29+
if(MAZE[nx][ny] == '0' or visited[nx][ny]): continue
30+
q.append((nx, ny, moves+1))
31+
visited[nx][ny] = True
32+
```

‎src/Do-ho/dfsbfs/boj_2178_미로탐색/boj_2178.py‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
import sys
2+
from collections import deque
3+
4+
D = [(1, 0), (0, 1), (-1, 0), (0, -1)]
5+
6+
N, M = map(int, sys.stdin.readline().strip().split())
7+
MAZE = deque()
8+
for _ in range(N): MAZE.append(sys.stdin.readline().strip())
9+
10+
q = deque()
11+
visited = [[False for _ in range(M)] for _ in range(N)]
12+
q.append((0,0,1))
13+
visited[0][0] = True
14+
15+
while q:
16+
tx, ty, moves = q.popleft()
17+
if(tx == N-1 and ty == M-1):
18+
sys.stdout.write(str(moves)+'\n')
19+
break
20+
for DIR in D:
21+
nx, ny = [tx + DIR[0], ty + DIR[1]]
22+
if(nx < 0 or nx >= N or ny < 0 or ny >= M): continue
23+
if(MAZE[nx][ny] == '0' or visited[nx][ny]): continue
24+
q.append((nx, ny, moves+1))
25+
visited[nx][ny] = True

‎src/Do-ho/dfsbfs/boj_2644_촌수계산/README.md‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
# 촌수 계산
2+
3+
dfs로 풀어버리자~~~
4+
5+
근데 ... exit()를 쓰면 런타임 오류가 나옴.. ㅠㅠ

‎src/Do-ho/dfsbfs/boj_2644_촌수계산/boj_2644.py‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
import sys
2+
from collections import deque
3+
4+
n = int(sys.stdin.readline())
5+
a, b = map(int, sys.stdin.readline().rstrip().split())
6+
m = int(sys.stdin.readline())
7+
8+
r = {}
9+
10+
for _ in range(m):
11+
x, y = map(int, sys.stdin.readline().rstrip().split())
12+
try: r[x].append(y)
13+
except: r[x] = [y]
14+
try: r[y].append(x)
15+
except: r[y] = [x]
16+
17+
def dfs():
18+
q = deque()
19+
q.append((a, 0))
20+
visited = [False for _ in range(n+1)]
21+
22+
while(q):
23+
target, chon = q.pop()
24+
if(target == b):
25+
return chon
26+
for item in r[target]:
27+
if(visited[item]): continue
28+
q.append((item, chon+1))
29+
visited[item] = True
30+
return -1
31+
32+
print(dfs())

‎src/Do-ho/dp/boj_1010_다리놓기/README.md‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
# 다리 놓기
2+
3+
f(1, 1) = 1
4+
f(1, 2) = 2
5+
f(1, 3) = 3
6+
~~
7+
8+
f(2, 2) = f(1, 1)
9+
f(2, 3) = f(1, 2) + f(1, 1)
10+
f(2, 4) = f(1, 3) + f(1, 2) + f(1, 1) = f(1, 3) + f(2, 3)
11+
f(3, 3) = f(2, 2)
12+
f(3, 4) = f(2, 3) + f(2, 2)
13+
f(3, 5) = f(2, 4) + f(2, 3) + f(2, 2) = f(2, 4) + f(3, 4)
14+
15+
따라서 점화식
16+
17+
f(n, k) = f(n-1, k-1) + f(n, k-1)
18+
= f(n, k-1) + f(n-1, k-1)
19+

‎src/Do-ho/dp/boj_1010_다리놓기/boj_1010.py‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
import sys
2+
3+
D = [[0 for _ in range(30)] for _ in range(30)]
4+
5+
def f(i, j):
6+
if j<i: return 0
7+
if i==1: return j
8+
if i==j: return 1
9+
return D[i][j-1] + D[i-1][j-1]
10+
11+
for i in range(30):
12+
for j in range(30):
13+
D[i][j] = f(i, j)
14+
15+
T = int(sys.stdin.readline())
16+
17+
for _ in range(T):
18+
[N, M] = map(int, sys.stdin.readline().split())
19+
sys.stdout.write(str(D[N][M])+"\n")

‎src/Do-ho/dp/boj_1149_RGB거리/README.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
# RGB거리
2+
3+
순차적으로 2차원 D에 저장하면서 마지막 3개의 값을 비교하자

‎src/Do-ho/dp/boj_1149_RGB거리/boj_1149.py‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
import sys
2+
3+
T = int(sys.stdin.readline())
4+
D = [[0, 0, 0] for _ in range(T)]
5+
S = []
6+
7+
for _ in range(T):
8+
S.append(list(map(int, sys.stdin.readline().split())))
9+
10+
D[0] = S[0]
11+
12+
for i in range(1, T):
13+
D[i][0] = S[i][0] + min(D[i-1][1], D[i-1][2])
14+
D[i][1] = S[i][1] + min(D[i-1][0], D[i-1][2])
15+
D[i][2] = S[i][2] + min(D[i-1][0], D[i-1][1])
16+
17+
sys.stdout.write(str(min(D[T-1])))

‎src/Do-ho/dp/boj_11727_2n타일링2/README.md‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
# 2*n 타일링 2
2+
3+
2*1일때 (1)
4+
5+
2*1타일 1개
6+
7+
2*2일때 (3)
8+
2*1타일 2개
9+
1*2타일 2개
10+
2*2타일 1개
11+
12+
2*3일때 (6)
13+
이전까지의 타일 + 2*1
14+
이전전까지의 타일 + (2*2, 1*2타일 2개)
15+
16+
2*4일때 (12)
17+
이전까지의 타일 + 2*1
18+
이전전까지의 타일 + (2*2, 1*2타일 2개)

0 commit comments

Comments
 (0)