백준[골드3]
1.[백준] 2638번 치즈 ★
인접한 4변 중에서 적어도 2변 이상이 공기와 접촉한다면 녹아 없어진다는 부분만 추가적으로 구현하여 수월하게 해결할 수 있었다.💡소요시간 : 41m
2.[백준] 1644번 소수의 연속합
에라토스테네스의 체와 슬라이싱을 이용해서 구할 수 있었다.💡소요시간 : 17m
3.[백준] 14905번 소수 4개의 합
입력값이 8미만인 경우 "Impossible."을 return하고 입력값이 8이상인 경우 에라토스테네스의 체를 이용해 소수를 걸러준 다음 4중 for문을 이용해서 입력값이 소수 4개의 합으로 표현이 된다면 출력하고 멈춘다.💡소요시간 : 40m
4.[백준] 1153번 네 개의 소수
4중 반복문을 통해서 소수 4개를 가져오는 방식으로 코드를 작성했다.Python3로는 시간초과(TLE)가 나와서 PyPy3로 제출했는데 AC를 받았다. 그런데 맞힌 사람들의 메모리와 시간을 보니 정말 하늘과 땅 차이였다. 머릿속에 떠오르는 방법은 4중 반복문 밖에 없어
5.[백준] 2812번 크게 만들기 ★
스택의 마지막 수와 N자리 숫자의 i번째 수를 비교했을때 스택의 마지막 원소의 값이 더 작다면 pop하고 N자리 숫자의 i번째 수를 스택에 넣어준다.💡소요시간 : 1h
6.[백준] 17299번 오등큰수 ★★★
이전 포스팅에 있던 \[백준 17298번 오큰수]의 문제와 유사하여 접근하기 그나마 수월했던 문제였다.리스트 원소들의 각 빈도 수를 알고 싶을 때 Counter를 사용한다.dictionary를 이용하면 각 원소의 키와 값을 대응시켜 구할 수 있지만 위와 같은 from
7.[백준] 11066번 파일 합치기 ★★★
머리로 문제를 이해하는 것은 성공했지만 코드를 짜는 부분에 대해서 정말 어렵다고 느껴서 어떤 식으로 접근해야할지에 대해서 확인해보기 위해서 구글링을 시도했다. 코드를 보지 않고 어떤 방식으로 접근을 하는지에 대해 설명하자면 다음과 같다.입력1440 30 30 50출력3
8.[백준] 2473번 세 용액
처음에 접근한 투 포인터 방식은 아래의 코드와 같았다.왼쪽 포인터와 오른쪽 포인터 사이에서 for문으로 순회를 하여 세 개의 값들을 골라 0에 가까운 조합을 만들 수 있는 경우의 수를 구하려고 했지만 실패하여 다른 방법을 생각했다.코드는 아래와 같다.
9.[백준] 16964번 DFS 스페셜 저지 ★★★
주어진 DFS 방문 순서대로 탐색을 할 수 있는지에 대해 묻는 문제였는데 일반적인 DFS 코드를 떠올려 인접 노드의 정점 방문 순서를 오름차순/내림차순 정렬을 수행한 결과를 각각 따로 구한 다음 주어진 DFS 방문 순서와 일치하면 1을 출력하는 방식으로 코드를 작성했지
10.[백준] 1937번 욕심쟁이 판다 ★★★
처음엔 이 문제에서 왜 깊이 우선 탐색이 사용되는지 몰라서 단순 방향 배열을 이용한 dp문제로 생각해서 코드를 짰는데 바로 WA를 받았다. dp로 접근을 하게 되면 특정 시작점에서부터 탐색을 시작하면서 dp 테이블의 값이 갱신이 되는데 다른 시작점에서 새롭게 탐색을 진
11.[백준] 2206번 벽 부수고 이동하기 ★★★
좌표 개념의 문제고 최단거리라는 표현을 보자마자 BFS로 풀어야겠다고 생각했다. 근데 일반적인 최단거리 문제가 아니라 벽을 부술 수 있다는 특징을 가지고 있는 문제였다.벽을 부수고 최단거리로 이동하는 방법도 존재하지만 벽을 부수지 않고 최단거리로 이동하는 방법도 존재한
12.[백준] 1238번 파티
모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있으므로 각각의 집에서 출발해서 X에 도달한 후 X에서 출발해서 각각의 집으로 돌아올 때 가장 오래 걸리는 학생의
13.[백준] 4386번 별자리 만들기
선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 발생한다.문자열 포맷팅을 절대/상대 오차 10^(-2)까지 허용하도록 출력💡소요시간 : 41m
14.[백준] 1613번 역사
플로이드-워셜 알고리즘을 이용한 문제a가 b보다 먼저 발생했는지 즉, graph\[a]\[b]가 1이면 -1b가 a보다 먼저 발생했는지 즉, graph\[b]\[a]가 1이면 1만약 graph\[a]\[b]가 INF라면 알 수 없으므로 0Python3로는 시간초과, P
15.[백준] 1719번 택배 ★
최단 거리를 출력하는 것이 아니라 최단 거리를 출력하는 경우 경유해야하는 집하장의 번호를 출력💡소요시간 : 47m
16.[백준] 1774번 우주신과의 교감
이미 연결된 통로의 경우 Union연산을 통해서 미리 연산을 수행한 후 나머지 연결되지 않은 경우에 대해서 크루스칼 알고리즘을 적용하여 문제를 풀이했다.💡소요시갼 : 51m
17.[백준] 1414번 불우이웃돕기 ★
문제에 대한 이해가 늦어 풀이에 많은 시간이 걸렸던 문제였다.💡소요시간 : 1h 24m
18.[백준] 14431번 소수마을 ★★★
다익스트라 알고리즘을 작성하는 과정에서 좌표의 개념을 어떻게 적용해야할지 고민이 많았고 이를 좌표 그대로 처리하는 과정에서 IndexError가 이 부분을 해결하기 위해 많은 고민을 했다.좌표를 그대로 넣지 않고 좌표에 해당하는 인덱스로 처리를 하여 다익스트라 알고리즘
19.[백준] 11779번 최소비용 구하기2 ★★★
일반적인 다익스트라 알고리즘처럼 최단거리를 출력하면서 최단 경로를 역추적해야하는 문제였다. 다익스트라의 역추적에 대해서 공부하고 다시 풀었다. 최단거리를 계산하는 것 뿐만 아니라 해당 경로도 출력할 수 있도록 하는 부분도 알아두자.💡소요시간 : 2h
20.[백준] 17182번 우주 탐사선
플로이드-워셜 알고리즘으로 각각의 출발점에서 발사했을 때 각각의 도착점에 도착하는데 걸리는 시간을 갱신한다.모든 행성을 탐사하는데 필요한 최소 시간을 구하기 위해 백트래킹을 이용한다.💡소요시간 : 37m
21.[백준] 13904번 과제 ★★
점수를 기준으로 내림차순하면서 마감일이 같은 여러 과제에 대해서 가장 높은 점수를 받을 수 있는 과제를 선택해 과제를 수행하면 된다. 뒤에서부터 확인하는 방법을 이용했다.💡소요시간 : 1h 47m