08-03 (수)
프로그래머스 lv2
숫자의 표현
https://school.programmers.co.kr/learn/courses/30/lessons/12924?language=python3
어떤 수를 연속된 자연수의 합으로 만들 수 있는 경우의 수를 구하는 문제.
dp를 이용하거나 완전탐색을 이용하여 풀 수 있지만 테스트 케이스에서 완전탐색만 사용해도 풀 수 있게 돼 있음. 완전탐색을 하는 경우에도 조건을 잘 넣으면 경우의 수를 반이상 줄일 수 있는 것을 상기할 수 있는 문제. 등차수열의 합 공식 유도를 오랜만에 했다.
프로그래머스 lv2
모음사전
https://school.programmers.co.kr/learn/courses/30/lessons/84512
경우의 수를 대략적으로 계산 후 O(n)의 시간복잡도로도 넉넉할 것 같아서 완전탐색으로 풀이 방향을 정했다
프로그래머스 lv2
다음 큰 숫자
https://school.programmers.co.kr/learn/courses/30/lessons/12911
2진수 상태에서 완전탐색을 처음에 생각했다가 경우의 수가 너무 많이 나와서 정수에서의 완전탐색을 생각했는데 금방 풀렸다. 또한 bin() 함수와 String.count() 함수를 알게됐다.
08-07 (일)
프로그래머스 lv2
게임 맵 최단거리
https://school.programmers.co.kr/learn/courses/30/lessons/1844
처음에 dfs로 문제를 풀었다가 효율성 검사에서 에러가 나서 질문하기 영역을 확인해보니 최단거리는 dfs가 아닌 bfs로 해야 속도가 빠르다는 댓글을 보았다. bfs가 더 빠른 이유를 대충 훑어보고 바로 bfs로 바꾸어 풀었더니 통과됐다. Dfs, Bfs의 기본적인 특징들을 까먹어서 문제 푸는데 시간을 많이 써버렸다.
08-09 (화)
프로그래머스 lv2
영어 끝말잇기
https://school.programmers.co.kr/learn/courses/30/lessons/12981
조건문을 잘 조합해서 푸는 문제
프로그래머스 lv2
n개의 최소공배수
https://school.programmers.co.kr/learn/courses/30/lessons/12953
gcd, lcm을 활용하는 문제. 스택을 이용해 숫자를 2개를 pop해서 최소공배수를 push하는 식으로 스택 사이즈가 1이 될때까지 반복했다.
프로그래머스 lc2
올바른 괄호
https://school.programmers.co.kr/learn/courses/30/lessons/12909
스택을 활용하여 괄호를 없앤다.
08-11 (목)
프로그래머스 lv2
배달
https://school.programmers.co.kr/learn/courses/30/lessons/12978
다익스트라 알고리즘을 통해 한 노드로부터 다른 노드의 최단거리를 구하는 문제.
08-13 (토)
프로그래머스 lv2
[1차] 캐시
https://school.programmers.co.kr/learn/courses/30/lessons/17680
- 꼭 다시 풀기
LRU(least recent used) 알고리즘을 이용해 캐싱을 통한 성능을 개선하는 문제이다. cache size를 확인하는 조건문을 먼저 넣어서 초기에 캐시가 다 차기 전에 똑같은 값이 캐시 리스트에 들어가는 문제가 발생했다. 따라서 캐시에 값이 있는지 확인하는 조건문을 먼저 넣어서 문제를 해결해야 했다.
08-14 (일)
프로그래머스 lv2
JadenCase 문자열 만들기
https://school.programmers.co.kr/learn/courses/30/lessons/12951
제이든케이스 문자열을 만드는 문제. 단어 사이 공백이 모두 제대로 들어가기 위해 split을 그냥 쓰는게 아니라 split(' ')을 써서 다시 join할 때 공백 개수를 살려줘야 했던 문제.
08-17 (수)
프로그래머스 lv2
메뉴 리뉴얼
https://school.programmers.co.kr/learn/courses/30/lessons/72411
dictionary, tuple, itertools, counter 와 같은 기본적인 라이브러리들을 사용하면 쉽게 풀 수 있는 시뮬레이션 문제.
08-27 (토)
프로그래머스 lv2
전력망을 둘로 나누기
https://school.programmers.co.kr/learn/courses/30/lessons/86971
union-find 혹은 완전탐색을 통해서 풀 수 있는 문제.
재귀함수에서 리턴값을 넣어주지 않아서 한참동안 오류를 찾지 못했다.
08-30 (화)
백준 골드4
1062 가르침
https://www.acmicpc.net/problem/1062
문자열의 비교는 시간복잡도가 크게 나타나서 시간초과가 걸리므로, 비트마스킹 방식을 사용해야 풀 수 있는 문제.
08-31 (수)
백준 골드1
1700 멀티탭 스케줄링
https://www.acmicpc.net/problem/1700
탐욕 알고리즘을 통해 최적해를 찾는 문제. 문제에서 100 * 100 의 시간복잡도를 주었지만 O(n**2)을 사용하기 싫어 시간을 낭비했다.
또한 조건문에서 list가 채워지지 않은 경우보다 list에 해당 item이 존재하는지 먼저 check 해야 오류 없이 풀 수 있었다.
# 틀린 조건식 순서
if len(list) < N:
elif item in list
# 맞는 조건식 순서
if item in list:
elif len(list) < N:
