코딩테스트
1.[프로그래머스] 달리기 경주
(출처 - 프로그래머스)이 문제의 핵심은 딕셔너리 값으로 찾는 것이다.index로 찾을 경우 시간 복잡도가 O(n) 이기 때문에 for 문 안에서 돌면 O(n^2)가 된다.
2.DFS 재귀 제한 해제
sys.setrecursionlimit(10000) 을 통해 재귀 최대 깊이를 임의로 설정하여 늘려줄 수 있다.DFS 문제를 재귀함수로 풀 때 활용하여야 한다.
3.[코테 팁 정리]
계속 업데이트 예정
4.[백준] 1987- 알파벳 파이썬 풀이 (DFS, 백 트래킹)
알파벳
5.[백준] 13023 - ABCDE (DFS, 백트래킹)
ABCDE
6.[백준] 2668 - 숫자고르기 (DFS)
숫자고르기
7.[백준] 2636 - 치즈 (BFS)
치즈
8.[백준] 1245 - 농장 관리 (BFS,DFS, trigger)
BFS,DFS
9.[백준] 2617 - 구슬 찾기 (DFS)
DFS
10.[백준] 2023 - 신기한 소수 (백트레킹)
백트래킹
11.[백준] 1149 - RGB 거리
DP
12.[백준] 2156 - 포도주 시식 (DP)
DP
13.[백준] 2579 - 계단 오르기
dp
14.[백준] 2302-극장 좌석(DP)
DP
15.[백준] 2688 - 줄어들지않아 (DP)
DP
16.[백준] 10844-쉬운계단 수 (DP)
dp
17.[알고리즘] 최소 스패닝 트리
MST
18.[백준] 1922 - 네트워크 연결 (그래프)
MST
19.[백준] 2141 - 우체국 (그리디)
가중치 중위값 문제이다.전체 가중치의 중간값이 되는 지점에 우체국을 세우면 되는 문제이다.이렇게 중간에 세우는 문제에 대해 유의
20.[백준] 1931 - 회의실 배정 (그리디)
그리디
21.[백준] 2437 - 저울 (그리디)
그리디
22.[백준] 2573 - 빙산 (BFS)
BFS
23.[프로그래머스] PCCP- 석유시추 (BFS)
문제 https://school.programmers.co.kr/learn/courses/30/lessons/250136?language=python3 코드 풀이 BFS를 사용하는 것이 효율성 측면에서 좋음. 석유가 있는 곳의 열을 y_list에 저장. 각 열에 대한 result를 만들어놓고, 열을 기준으로 count를 더해놓음.
24.[프로그래머스] 두 원 사이의 정수 쌍
프로그래머스
25.[백준] 1374 강의실 (그리디, heapq)
코드 풀이 heapq를 활용하는 문제이다. 시작하는 시간을 기준으로 sort한다. 끝나는 시간을 기준으로 room을 배정한다고 생각하자. 만약 가장 빨리 끝나는 강의 (heapq 첫번째 값)보다 다음 강의의 시작하는 시간이 크다면 -> 강의를 갈아끼우면 된다. 필요한 강의실의 max 값을 구하면 최소 필요한 강의실을 구할 수 있다.
26.[백준] 1261 알고스팟 (BFS)
코드 풀이 처음에는 DFS로 풀려고 했으나 시간초과가 날 것 같아서 BFS로 변경 만약 visited가 -1이라면 한번도 방문 안한거니 방문처리를 하는데, 그 값이 0이라면 벽을 부술 필요가 없으니 그 전의 vistied 값을 그대로 가져옴 값이 1이라면 벽을 부숴
27.[백준] 2589 보물섬 (BFS, 최단거리)
코드 풀이 visited를 따로 선언해주었더니 시간초과가 났다. 결국은 최단 거리를 구하면 되는 것이기 때문에, dist라는 것이 visited의 역할도 동시에 진행해주면 된다. dist가 0일 때만 Q에 append 하는 형식으로 if문을 걸어주면 된다.
28.[백준] 1976-여행가자 (유니온 파인드)
코드 풀이 갔던 도시를 다시 가도 된다는 점에서 visited list가 필요없다고 생각. 조상이 같으면 어떻게든 갈 수 있으므로, union-find로 풀이. 조상 찾기 진행 (union-find) 첫번째 도시를 조상으로 설정하고, 각 도시들의 조상 도시가 첫번째 도시가 아니면 NO를 출력
29.[백준] 1707-이분그래프(이분 그래프)
코드 풀이 인접하는 정점이 다른 집합이면 되는 이분 그래프이다. (같은 집합의 정점은 이어져있지 않아야 한다) 특정 정점과 인접한 정점은 다른 색으로 칠해지면 된다. 코드화 하기 위해 color와 -color로 색을 바꿔줫다.
30.[백준] 1520-내리막길 (DFS,DP)
코드 첫 풀이 이런 식으로 갈 수 있는 경우를 모두 끝까지 확인하였다. 시간초과 발생. 해결 코드 visited가 -1이라면 방문하지 않은 곳. 만약 해당 지점의 visited 테이블이 -1이 아닌 업데이트 되어있는 상태라면 더 진행 할 필요 없이, 그 지점이 부분 최적해가 되므로 그 지점의 visited 테이블의 값을 바로 반환해준다.
31.[백준] 1504 - 특정한 최단 경로 (다익스트라)
코드 풀이 전형적인 다익스트라 문제 한 정점에서 다른 모든 정점으로 가는 최단거리를 구함. 1,v1,v2 에서 시작했을 때의 최단거리 리스트를 구함. 1->v1->v2->V, 1->v2->v1->V 경로 중 작은 값이 result 길이 없다면 INF가 나올 것이므로 그럴 때는 -1 출력
32.[백준] 1138 - 한 줄로 서기 (그리디)
코드 리뷰 0으로 초기화 한 뒤, 특정 번호인 사람(0~N-1)의 앞에 본인보다 큰 사람에게 빈자리를 두고 채워나가면 됨. cnt는 본인보다 큰 사람 명수만큼 비워졌는지 확인, 그 자리가 0이라면 배정해주기.