반응형 분류 전체보기580 코드 실행시간 단축시키는 꿀팁 (C++) 첫 번째 팁 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 입출력에서 시간을 줄여주는 코드이고 3줄을 메인문의 시작 부분에 붙히면 된다. 이런식으로... 출력초과만 나다가 이 3줄을 붙히니까 바로 정답처리된 모습을 볼 수 있다. 본인은 지금까지 저 3줄을 붙이면서 문제 풀이를 해왔는데, 하필 저거 붙이는걸 깜빡하고 푼것이 이 문제라니 참으로 이보다 기가 막힌 우연일 수 없다. 두 번째 팁 여러줄을 출력해야하는 문제가 있다. cout 2020. 8. 17. [동적계획법, 난이도 중상] 백준 1520번 내리막 길 이 문제는 동적계획법과 DFS를 동시에 적용해야 하는 문제이다. 백준 1890번 점프와 접근법은 비슷하다. https://kimcoder.tistory.com/47 [동적계획법, 난이도 상] 백준 1890번 점프 동적계획법과 DFS를 동시에 적용해야 하는 높은 난이도의 문제이다. 본인은 이제부터 DFS를 마주쳤다 싶으면 바로 그래프로 도식화해서 풀 것이라고 다짐했다. 이 문제는 두 스텝으로 나누어서 �� kimcoder.tistory.com 경로벡터를 이용하였으며 도착점부터 시작점까지 역으로 DFS를 수행하였다. 자세한 설명은 위 링크에 있는 백준 1890번 점프 풀이를 읽고오면 된다. 아래 그림도 백준 1890번 점프에서 도식화 했던 원리랑 똑같다. 문제에 따른 push_back 기준만 다를 뿐이다. .. 2020. 8. 17. [동적계획법, 난이도 상] 백준 1890번 점프 동적계획법과 DFS를 동시에 적용해야 하는 높은 난이도의 문제이다. 본인은 이제부터 DFS를 마주쳤다 싶으면 바로 그래프로 도식화해서 풀 것이라고 다짐했다. 이 문제는 두 스텝으로 나누어서 해결했다. 1. 점프할 수 있는 좌표를 모두 경로벡터에 넣는다. 여기에서는 간선이라고 봐도 무방하다. 점프를 했을 때 맵 밖으로 벗어나는 경우도 신경 써줘야한다. 맵 밖으로 떨어진 좌표는 경로벡터에 넣지 않으면 된다. 오른쪽, 아래쪽만 점프 가능하다는 사실을 잊지말자. DFS를 도착점부터 역으로 수행할 것이기 때문에 간선 연결 방향은 반대로 했다. >> a[i+jump*dx[k]][j+jump*dy[k]].push_back(make_pair(i, j)); 이 과정이 끝나면 경로는 이렇게 된다. 맨 오른쪽 맨 아래 '0.. 2020. 8. 17. [그리디, 난이도 중] 백준 1543번 문서 검색 문자열 매칭 알고리즘들중 라빈카프를 이용했다. 라빈카프 알고리즘은 문자열의 특정 해쉬값을 계산한 후 두 해쉬값이 일치할 경우, 문자열 매칭에 성공했다고 판단하는 알고리즘이다. 여기서 2차적으로 동일한 해쉬값을 가진 문자열에 대해서 확인차로 한번더 문자열 그 자체를 검사할 수도있다. 문자열의 해쉬값을 정하는 방법은 많지만 이 소스코드에서 해쉬값은 이렇게 정했다. 문자열 a의 size를 size라고 가정하면 문자열의 해쉬값 = a[0]*2^(size-1) + a[1]*2^(size-2) +a[2]*2^(size-3) + ... a[size-1]*2^0 https://www.youtube.com/watch?v=kJJQJDsjXc8 문자열 매칭 알고리즘은 동빈나 님의 강의로 배웠는데 여기서 동빈나님이 이용하신 .. 2020. 8. 17. 큰 값을 나눗셈하는 소스코드 작성 시 주의할 점 백준 2869번 달팽이는 올라가고 싶다 라는 문제이다. 이 문제에서는 억단위의 숫자끼리 나눗셈을 수행하는 경우까지 처리해줘야한다. 시간복잡도 O(1)로 풀면 되는 문제인데도 정답율이 26%밖에 안되는 이유는 많은 이들이 어떤 사실을 모르고 있었기 때문이라고 생각한다. 이 어떤 사실이 무엇인지 설명하겠다. www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 �� www.acmicpc.net 결론부터 말하자면 큰값에서 큰값을 나눈 값을 float형 변수에다가 저장하지 말자. 그 .. 2020. 8. 17. [DFS, 난이도 중] 백준 1389번 케빈 베이컨의 6단계 법칙 이 문제는 BFS로 푸는게 훨씬 간단하다. 왜냐하면 최단경로를 구해야 하는 문제이기 때문이다. DFS로 하면 꽤 신경써야될 것들이 있다. 깊이 매개변수를 추가해줘야하고 DFS를 다 돌면 방문처리를 해제해야한다. 본인은 DFS연습 차원으로 DFS로 풀었기 때문에 DFS이용 기준으로 난이도를 중으로 정했다. BFS로 풀었다면 중하~하 사이가 아닐까 싶다. 주어진 예제를 양방향 그래프로 도식화한 그림이다. dfs의 매개변수는 각각 (출발점,도착점,깊이) 이다. 출발점=도착점인 경우 깊이의 최솟값을 갱신하는 처리를 해준뒤 하나의 dfs함수를 종료한다. 노드n이 노드1~n까지 모두 탐색하여 구한 최단경로의 합은 kevin[n] 이다. kevin의 최솟값을 가지는 최초의 인덱스값을 출력하면 문제는 해결된다. BFS.. 2020. 8. 16. [동적계획법, 난이도 중하] 백준 11726번 2xn 타일링 이 문제에 동적계획법을 적용시키면 2x1, 2x2, 2x3, ... 2x(n-1),2xn 이런식으로 차례대로 이전 값을 이용하여 계산해 나가면 된다. 이전 타일값에 1x2, 2x1 타일을 붙일 수 있는 경우의 수를 따져보자. 위의 전체 타일의 넓이는 2xn이다. 그리고 갈색 타일의 넓이는 1x2, 2x1이다. 이렇게 2x(n-1) 타일에 2x1 타일을 1개 추가하는 방법 -> 1가지 2x(n-2) 타일에 1x2 타일을 2개 추가하는 방법 -> 1가지 2x(n-2) 타일에 2x1 타일을 2개 추가하는 방법은 포함하지 않는다. 왜냐하면 이는 2x(n-1) 타일에 2x1 타일을 1개 추가하는 방법과 같은 경우이기 때문이다. 경우가 중복된다는 의미다. 즉 save[n]=save[n-1]+save[n-2] 라는 .. 2020. 8. 16. [개발중 Progress #1] Open The Door! (작품 설명 포함) Progress#1 : 2020년 5월부터 시작하여 주말, 휴가를 이용하여 수행 게임 설명 캐릭터 3명을 각각 움직여서 3명 모두 도착 지점에 있는 발판을 밟게 하는 두뇌게임 여러 색의 버튼을 눌러 문을 열어서, 다른 캐릭터들이 문을 통과할 수 있게 한다. 높은 단계로 갈수록 맵의 구조가 복잡해진다. 단계를 빨리 클리어 할 수록 다이아몬드 보상을 많이 받게 된다. 개발자의 기록에도 도전해보라! 플레이 영상 www.youtube.com/watch?v=aZ7ffQAa8sc 작업 화면 2020. 8. 15. [DFS, 난이도 중하] 백준 10026번 적록색약 (BFS, DFS 모두 사용) 제출번호 21761134가 DFS로, 제출번호 21760828이 BFS로 해결해서 정답처리된 소스코드이다. 맵의 모든 구역을 탐색하면서 탐색하지 않은 좌표에서 BFS/DFS를 호출하여 , 인접 색들을 만나면 전부 방문처리를 한다. BFS/DFS를 호출할 때마다 group 카운트를 늘려나가서 몇 개의 그룹으로 이루어져 있는지 계산하면 된다. 적록색약이 아닌사람에 대해서 map배열, visited배열, group변수를, 적록색약인 사람에 대해서 map2배열, visited2배열, group2변수를 썼다. 두 가지 경우에 대해 모두 수행해주었다. 적록색약인 사람인 경우 모든 초록색을 빨강색으로 인지하는 것으로 가정했다. 즉 map2에서는 R 혹은 B만 존재한다. 애초에 모든 G를 R로 바꾼 것이다. 이렇게 접.. 2020. 8. 15. 이전 1 ··· 58 59 60 61 62 63 64 65 다음
