13913번 숨바꼭질 4
BFS Problem - G4
지나간 거리를 기록해야하는 BFS 문제이다.
최소 소요시간을 구해야하기 때문에 시간 복잡도를 고려하여 이미 지나간 위치는 다시 탐색하지 않게 작성해야한다.
풀이 중 발생한 에러
- 메모리 초과 (스택 메모리 초과) : 범위를 범어날 경우 탐색하지 않는다.
- 런타임 에러 : 처음에 있는 위치와 목표된 위치가 같은 위치일 경우 탐색 중 인덱스 초과로 에러 발생하기 때문에 이러한 경우도 고려하여 작성해야한다.
2539번 모자이크
Binary Search Problem - G4
이분 탐색을 이용하여 문제 내 조건을 만족하는 길이의 최솟값을 구해야하는 문제이다.
풀이 중 발생한 에러
- 틀렸습니다 : 처음에 이분 탐색 방법이 잘못 된 것 같아 탐색 내 배열의 길이를 판별하는 로직에서 지정된 길이를 가진 종이의 갯수를 판별라는 로직으로 수정하여 문제 해결을 작성하였다.
16500번 문자열 판별
String DP Problem - G5
문자열을 이용하여 해당 조건을 판별해야하는 DP 문제이다.
풀이 중 발생한 에러
- 틀렸습니다 : 확인 결과 문자열 내 인덱스를 잘못 불러와 생긴 문제였다.
풀이 이후 해결 코드 내 문자열을 공통으로 판별하는 내역이 중복되어 있어서 함수로 추상화시켜 리펙토링을 진행하였다.
13422번 도둑
Prefix Sum Problem - G4
연속 된 합이 지정된 값보다 크지 않은 경우의 수를 구하는 문제이다.
주어진 시간복잡도를 해결하기 위하여 누적 합을 이용하여 연속된 합을 구하는 것이 중요하다.
문제 조건 중 끝과 끝 사이에 연결되어 있다는 것을 유의하여 누적합 배열의 크기를 2 * N으로 잡아야한다.
풀이 중 발생한 에러
- 틀렸습니다 : 연속된 길이와 주어진 N의 값이 같을 때를 고려했어야했다. 위의 경우 경우의 수가 1가지 였다.
풀이 이후 해결 코드 내 문자열을 공통으로 판별하는 내역이 중복되어 있어서 함수로 추상화시켜 리펙토링을 진행하였다.
2825번 수업시간에 교수님 몰래 교실을 나간 상근이
Bitmask Problem - G2
비트마스킹을 이용하여 주어진 수의 숫자 포함여부를 저장하여 친구의 수를 구하는 문제이다.
친구의 수를 구할 때 동일한 키들 끼리는 계산하지 않아야한다.
28291번 레드스톤
Implementation Problem - G5
BFS를 이용한 구현문제이다.
구현 문제를 풀 때 문제 내 요구사항 별로 꼼꼼히 읽어봐야겠다고 생각이 든다
25187번 고인물이 싫어요
Data Structures Problem - G4
그래프 노드 내 자료구조를 선언한 뒤 그래프 내를 순환해야 하는 문제였다.
1781번 컵라면
Priority Queue Problem - G2
우선순위 큐를 활용해야하는 문제이다. 위의 문제 같은 경우 문제를 해결하는 용도로 컵라면을 담을 때 우선순위 큐를 이용한다.
파이썬 같은 경우 내장 라이브러리를 통하여 비교적 쉽게 문제를 해결할 수 있었다.
1599번 만식어
String Sort Problem - G5
기준에 맞는 단어로 치환 후 정렬하는 문제이다.
o 이후 단어를 하나 다음으로 옮긴 후 나머지 단어를 전환시키면 된다. (ng 대응)
7578번 공장
Segment Tree Problem - P5
Counting Inversions을 활용하여 쌍의 갯수를 구해야하는 문제이다.
Segment Tree 같은 경우 이분 탐색을 이용하여 값을 입력해나가거나 값을 수정할 수 있는 로직을 작성해야한다.
파이썬 같은 경우 파이파이를 활용하면 시간 초과를 해결할 수 있었다는 것을 알게 되었다.
