백준 [단계별로 풀어보기]: 다시 풀어볼 문제

단계5 : 문자열

1. BOJ 2908 / print(max(''.join(reversed(n)), ''.join(reversed(m)))) # n=int(n[::-1]) 뒤집기

2. BOJ 5622 / for idx, val in enumerate(dial):

 

단계6 : 심화 1

1. BOJ 2444 / for i in range(n,0,-1): #역순출력: range(start,end,-1)

2. BOJ 10988

3. BOJ 1157 / cnt = [s.count(i) for i in t] # s=input().lower(), t=set(s)

4. BOJ 2941 / w = w.replace(i,'/')

5. BOJ 1316 / if s[j] in s[j+1:]: #s[j+1:] : j+1부터 마지막까지

 

단계7 : 2차원 배열

1. BOJ 2738 / for i in range(n): for j in range(m): a[i][j]+b[i][j] #n행m열

2. BOJ 2566

3. BOJ 10798 / for i in range(15): for j in range(5): if i < len(mat[j]): ans += mat[j][i]

4. BOJ 2563 / ans += paper[i].count(1) #x축 기준, x=i일 때, 1의 개수의 총합

 

단계8 : 일반 수학 1 

1. BOJ 2745 / ans += b**i * num.index(n[i]) # int(num, b) <- b진법 숫자num을 10진법으로 변환

2. BOJ 1100 / num = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; ans += num[n%b]; n //= b

3. BOJ 2292 / while n > a: a += 6*k; k += 1 # a = 1; k = 1일때, 등차수열 구하는 반복문

4. BOJ 1193 / ★★★ / loop문

5. BOJ 2869 / d = a-b; h = v-b #d: 하루에 올라갈 수 있는 거리, h:올라가야 할 거리

 

단계9: 약수, 배수와 소수

1. BOJ 9506 / print(n,'=',' + '.join(str(i) for i in arr)) #출력값 join함수 활용

2. BOJ 1978 / if i % j == 0: if j == i: cnt += 1 break #숫자가 i에 도달하지 못하고 중간에 나누어지면 두번째 for문을 break

3. BOJ 2581 / if cnt == 0: p.append(i) #cnt가 0인 값만 소수

 

단계10 : 기하: 직사각형과 삼각형

1. BOJ 3009 / if a.count(a[i]) == 1: x = a[i] #원소의 개수 세기 arr.count() : 5 5 7중 1개인 것 선택

2. BOJ 14215 / print(2*(sum((a,b,c))-max(a,b,c))-1)

---

단계11 : 시간 복잡도

1. BOJ 24265 / 등차수열 합

2. BOJ 24267 / https://dev-mandos.tistory.com/124 https://developer-project.tistory.com/336

3. BOJ 24313

 

단계12 : 브루트 포스

1. BOJ 2231 / for i in range(1, int(n)+1): m = list(map(int, str(i))) #생성자i가 없더라도 푸는 법

2. BOJ 19532 / np.linalg.inv(x) #x의 역행렬 np.dot(a,b) #행렬의곱(=내적) <- 참고 : https://rfriend.tistory.com/380

3. BOJ 1018 / if (i+j) % 2 == 0: if ori[i][j] != 'w': w += 1 else: b += 1 #4중for문으로 8x8로 자르고, 짝/홀 일때 색 다르게

4. BOJ 2839 / 완탐풀이, DP풀이 같이 확인

 

단계13 : 정렬

1. BOJ 10989 / for i in range(len(cnt)): for _ in range(cnt[i]): print(i) # <------ 계수정렬 : count[i]의 i 개수 만큼 출력

2. BOJ 11650 / ans.sort(key=lambda x:(x[0], x[1])); for i,j in ans: print(i,j) #sort()함수 내 key=lambda식 / 이중배열 벗기기

2. BOJ 18870 / dic = {s[i]:i for i in range(len(s))}; for i in x: print(dic[i], end=' ') #s[i] : 중복제거한 list값을 key값으로 갖는 dictionary을 선언하고, list의 원소를 dic의 index에 넣는 for문 작성

 

단계14 : 집합과 맵

1. BOJ 10815 / dic = {n_arr[i]:0 for i in range(n)} #시간초과 시 dict or set으로 변경

2. BOJ 7785 / if state == 'enter': dic[name] = state; elif state == 'leave': del dic[name] #dic[key] = value & del[key]

3. BOJ 1620 / if ans.isdigit():print(dic[int(ans)]); elif ans.isalpha():print(index[ans])  #name = input(); dic[i] = name; index[name] = i <------- dic와 index 두 개의 딕셔너리로 받기

4. BOJ 10816 / dic = {} for i in n_arr: if i in dic: dic[i] += 1 else: dic[i] = 1 #list원소 i가 dic에 있다면, dic[i]값 +1하기

5. BOJ 1269 / a|b a&b a-b a^b a<=b a>=b

6. BOJ 11478 / for i in range(len(s)): for j in range(i,len(s)): set.add(s[i:j+1]) #다른 부분 문자열

 

단계15 : 약수, 배수와 소수 2

1. BOJ 1934 / def lcm(a,b): return a*b/gcd(a,b) #최소공배수 a*b/gcd(a,b)

2. BOJ 1735 / #기약분수: 분자와 분모의 최대공약수로 나눠주어야

3. BOJ 2485 / cnt = 0; for i in temp: cnt += i//n -1; print(cnt) #temp: 간격 <--- 95%이상 풀었으니까 확신 갖고 풀기

4. BOJ 4134 / for i in range(2,int(a**0.5)+1): if a%i == 0: return False #정수론에서, 임의의 양수 M이 합성수이면 √m 보다 작거나 같은 약수를 가진다.

5. BOJ 4948 / num = [1]*(123456*2+1) #def로 풀면 시간초과 발생 따라서, dp형식으로 풀이

6. BOJ 17103 / ★★ / #1)소수배열 2)for문(i의 배수) 3)i가 소수면 (합-i)도 소수

7. BOJ 13909 / BruteForce처럼 일단 규칙성을 찾아가는 방식으로 문제풀이 할 것

 

단계16 : 스택, 큐, 덱

1. BOJ 4949 / for _ in range(len(c)//2+1): c = c.replace('()','') c = c.replace('[]','') #괄호 짝 개수만큼 제거 <---- 여기 참고

2. BOJ 12789 / st = [] temp = 1 for i in arr: st.append(i) while st and st[-1]==temp: st.pop() temp += 1

3. BOJ 11866 / q.rotate(-k)와 print('<'+ ', '.join(ans) +'>') #q.rotate(-k): 오른쪽방향 k칸회전 / ""+""은 공백 없음(but "",""는 발생)

4. BOJ 2346 / q = dq(enumerate(map(int, input().split()), start=1)) #dq()안 enumerate()하기 / 원소 +/-별로 나눠 회전

원판에서, 양수가 적혀 있을 경우에는 오른쪽으로 이동 = 시계반대방향으로회전

 

단계19 : 조합론

1. BOJ 1010 / def fac(x): cnt = 1 for i in range(1, x+1): cnt *= i return cnt #import math math.factorial()로 대체 가능

 

단계20 : 심화 2

1. BOJ 25192 / if s !='ENTER': if s not in ans: cnt += 1 ans.add(s) #입력값이 ENTER가 아니면서, 집합에 없을때 cnt +1

2. BOJ 26069 / if s1=='CC' or s2=='CC': ans.add(s1) ans.add(s2) if s1 in ans or s2 in ans: ans.add(s1) ans.add(s2) #인덱스보다 변수 여러개

3. BOJ 2108 / ★★ / from collections import Counter as c #c(list).most_common() 혹은 dict() 사용

---

단계21 : 재귀

1. BOJ 25501 / #팰린드롬, global변수, 재귀(변수 여러개)

2. BOJ 24060 / IndexError: list index out of range??? #병합정렬, 

3. BOJ 4779 / #칸토어집합, 재귀활용한 규칙성찾기, 함수호출(def)vs출력(print : 문자열("") 사라짐)

4. BOJ 2447 / def star(n): if n==1: return ['*'] a = star(n//3) for i in a: arr.append(i*3) #n=1일때, return값을 잘 잡아주어야

5. BOJ 11729 / def hanoi(n, s, e): if n==1: print(s,e) else: hanoi(n-1, s, 6-s-e) #하노이탑:1,2,3단계로 나눠서 구분

 

단계22 : 백트래킹

1. 

 

단계23 : 동적 계획법 1

1.

2. BOJ 1011 / H사 기출(k가 1 or 2) / 

 

단계24 : 누적 합

1. 

 

단계25 : 그리디 알고리즘

1. 

 

단계26 : 분할 정복

1. 

 

단계27 : 이분 탐색

1.

 

단계28 : 우선순위 큐

1. 

 

단계29 : 동적 계획법 2

1.

 

단계30 : 스택 2

1.

---

단계31 : 그래프와 순회

1.