목록백준 (24)

아무코딩

[백준 1806] 부분합

문제풀이 이중포문으로 돌리면 시간 초과가 날것이다. 두개의 포인터를 통해 부분합보다 크면 왼쪽을 줄이고 작으면 오른쪽을 한칸이동하는 방식으로 탐색하여 가장 짧은 길이를 반환한다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #define MAX 1000001 using namespace std; int arr_size,S; int arr[MAX]; int main() { cin>>arr_size>>S; for(int i=0;i>arr[i]; } int min_length = MAX; int left=0; int right..
알고리즘/백준 2020. 4. 17. 20:17
[백준 15685] 드래곤 커브

문제풀이 stack을 이용하여 현재까지의 드래곤커브를 저장한뒤 다음 드래곤 커브를 그린다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include #include #include using namespace std; int N; stack s; vector dir_order; int Map[101][101]; int dir_x[4] = {1,0,-1,0}; int dir_y[4]..
알고리즘/백준 2020. 4. 15. 14:50
[백준 5214] 환승

초반에 문제를 좀 잘못 이해해서 고치는 데 시간을 좀 썼다. 첨에보고 단순한 인접리스트 + BFS문제인지 알았다. 문제풀이 조금 신선한 방식의 문제였다. 하이퍼 튜브내에선 서로서로 바로바로 갈수있다는 개념을 적용하기위해 단순한 graph에서 가상의 node(역)를 추가하여 가상의 역인 경우에는 실제로 횟수를 올리지 않는 방법으로 구현하였다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include #include #incl..
알고리즘/백준 2020. 4. 15. 00:55
[백준 14503] 로봇청소기

문제풀이 문제에 명시되어있는 로봇청소기 작동 로직을 그대로 따라 하면 된다. (시뮬레이션 문제) 후진 시 바라보는 방향을 안 바꿔줘야 되는데 실수로 바꿔버리는 바람에 오류 잡느라 다 찍어보며 시간이 걸렸다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 #include #include int N, M; typedef struct Robot..
알고리즘/백준 2020. 4. 6. 17:07
[백준 16638] 괄호 추가하기 2

보자마자 자료구조 때 배운 스택을 이용한 계산기 만드는 과제가 생각났다. 그 방식을 적용하여 풀었다. 자료구조에 나오는 스택 계산기는 infix -> postfix postfix 를 통한 결과 로 이루어지는 과정이다. 풀이과정 dfs를 통해 괄호를 친다. 괄호가 중복될수 없기 때문에 괄호보다는 괄호 처리된 연산을 따로 우선순위만 높여주는 방식으로 마킹하였다. 괄호 처리 : 우선순위 1 * : 우선순위 2 +,- : 우선순위 3 dfs를 끝까지 간 후 수식을 계산한다. 수식계산법 Infix -> postfix 피연산자가 들어오면 바로 postfix 벡터에 넣는다. 입력이 연산자인 경우에는 스택이 비었거나, 스택 top보다 우선순위가 낮은 인풋일 때까지 pop 한다. pop한뒤에는 postfix 벡터에 넣는..
알고리즘/백준 2020. 3. 31. 05:48
[백준 12094] 2048(hard)

풀이 방법 이 문제는 시간 초과를 해결하는 게 관건인 문제였다. 기존에 2048(easy) 문제를 풀 때 완 탐으로 풀었었는데 가지를 쳐서(백트래킹 이용) 시간을 줄이는 방법으로 풀었다. 시간 초과 해결법 - 백트래킹을 이용한다. 진행할 때 단계별 최댓값을 미리 계산하여 불가능한 경우 더 이상 진행하지 않는다. 이동하여 맵이 같은 경우 더 이상 진행하지 않는다. 여기서 시간 초과 해결법 2번의 경우에 의해 예외처리를 제대로 해주지 않아 많이 헤맸다. 이유는 가장 큰 블록의 최신화를 항상 cnt==10 일 때 해주었었는데 그 때문에 움직이지 못하는 경우에 0으로 뽑히는 문제가 있었다. 반례가 나왔던 예 4 2 4 8 16 4 8 16 32 8 16 32 64 16 32 64 128 정답 : 128 내 기존..
알고리즘/백준 2020. 3. 29. 22:52
[백준 17136] 색종이 붙이기

풀이과정 1. dfs를 통해 모든곳을 완탐한다. 2. 크기가 큰 색종이 부터 확인한다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 #include #include #include #include #define ATTACH 0 #define DETACH 1 using namespace std; int map[10][10]; i..
알고리즘/백준 2020. 3. 17. 20:21
[백준 1525] 퍼즐

매우 참신한 문제이다. 처음에는 메모리 제한이 적길래 bfs를 쓰지 말라는 건 줄 알았는데 이후 문제를 읽다 보니 그런 문제가 아니었다. 풀이 방법 입력을 나중에 방문 처리하기 유리하게 하나의 int로 받는다. 여기서 0은 9로 변경하여 받는다. 왜냐하면 012345678처럼 0이 맨 앞에 오는 경우에는 int로 처리했을 때 12345678이 되기 때문에 9자리 숫자가 아니라 8자리 숫자가 된다. 방문 체크는 map을 이용한다. map을 사용하지 않으면 매번 찾아야 된다. index를 따로 저장하기보다는 map을 사용하여 한번에 찾는 것이 유리하다. 현재 9(원래 0)의 위치는 string으로 변환한 뒤 find 하여 찾는다. string으로 변환한 이유는 0의 위치를 쉽게 찾기 위해서이다. string..
알고리즘/백준 2020. 3. 13. 17:08
Prev 1 2 3 Next