전체 글 썸네일형 리스트형 10973번 10973번 - 이전 순열 10972 번과 같은 방식으로 푼다. 다만 이전 순열이기 때문에 모든 걸 반대로 해줘야한다. 이전 순열의 경우는 내림차순일 경우 정렬할 구간, 오름차순일 경우 정렬된 구간이라고 생각하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include#includeusing namespace std;void prev(vector &v){ int increase = -1; int decrease = -1; //변곡점이 아닌 내림차순의 끝 구하기 for (int i = 0; i v[i + 1]) { decr.. 더보기 10972번 10972번 - 다음 순열 이 문제는 오름 차순과 내림차순을 잘 이용해야 풀 수 있었다. 일단 사전순으로 정렬된 가장 작은 순서는 오름차순이 된다. 그리고 순열의 가장 마지막 번호는 내림 차순이 된다. 예를 들어 1 2 3 4 는 가장 첫수는 오름차순으로 정렬된 상태이고 마지막 수 4 3 2 1 은 내림차순으로 정렬된 상태이다. 그리고 이 다음 순열은 1 2 4 3 이 된다. 이때, 오름차순이었던 수에서 내림차순이 발생한다. 즉 나는 다음순열을 구할 때의 핵심은 오름 차순은 정렬 할 구간, 내림차순은 앞으로 정렬 된 구간이라고 생각하고 풀었다. 7 2 4 6 5 3 1 이라는 순열이 있다고 해보면, 7 2 내림차순, 2 4 6 오름차순, 6 5 3 1 내림차순이 된다. 따라서 오름차순은 정리를 해야하기 .. 더보기 5014번 5014번 - 스타트 링크 간단한 BFS 문제였다. 각 층을 정점으로 위 아래로만 움직일 수 있는 간선이 존재한다고 생각하고 풀었다. dist 를 구해야했기 때문에, visited 는 따로 안쓰고 dist 로 모두 구현했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include#include#includeusing namespace std;bool visited[1000001];int dist[1000001];int ans = 0;int dx[2] = { 1,-1 };int main(){ int F, S, G, U, D; cin >> F >>.. 더보기 3108번 3108번 - 로고 나는 이 문제를 연결요소의 갯수를 구하는 문제로 접근했다. 결국 DFS를 통해서 한붓그리기가 가능하면 거북이가 붓을 뗄 필요가 없기 때문이다. 그래서 처음에 makeGraph 함수를 통해서 각 점들을 정점으로 간선들을 모두 연결해줬다. 이 과정에서 음수 값들을 제거하기 위해 모든 점들에 500을 더해줬다. 그래서 모든 점을 DFS 로 순회해서 연결요소의 갯수를 풀면 된다. 단 주의해야 할 점은 , 거북이가 시작점에 있느냐 있지 않느냐의 문제이다.. 이 부분에서 계속 헤맸다.. 처음에 N==1 일 때 문제인줄 알았지만 그것도 아니었고.. 그냥 거북이의 시작점에서 처음에 시작할 수 있는가 없는가였다. 거북이의 시작점에서 시작할 수 있다면, 연결요소의 갯수에서 하나를 빼야하기 때문이다. 연.. 더보기 2186번 2186번 - 문자판 이 문제는 처음에 DFS를 통해서 완전탐색으로 풀었는데, 시간 초과가 발생 DP로 문제를 해결하였다. 찾아야하는 문자열과 같을 때 dfs를 돌렸고, 그렇게 해서 처음에 시간 초과가 났다. 중복되는 지점을 찾다보니, 어떤 점에서 find_idx 가 같으면 굳이 계산할 필요가 없다는 걸 깨달았다. D[find_idx][x][y] = x,y 에 도착했을 때 다음에 찾아야할 값이 goal[find_idx] 인 경우의 수 라고 점화식을 만들었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#include using n.. 더보기 1525번 1525번 - 퍼즐 이 문제는 처음에 배열로 풀었다. 나름 머리쓴다고, 했지만 결국은 메모리 초과로 인한 런타임 오류... 그래서 STL map 을 공부해서 풀었다. 일단 map 은 정말 사용하기 좋은 template 인거 같다... 정렬도 되고, 배열처럼 사용할 수도 있고... 단 중복은 안되므로 그럴때는 multimap을 이용. 처음에 map을 배워서 map 의 인덱스 값으로 string을 이용했는데, 이 마저도 메모리 초과가 일어났다. 그래서 결국은 string 을 stoi 함수를 통해 모두 int 로 변경에서 index 로 입력했더니 AC를 받을 수 있었다. 결국 이 문제는 3 x 3 크기의 맵을 int 형 변수로 변경하고, 이를 map 을 통해 방문여부 체크하는 용도로 사용하여, bfs를 돌리면.. 더보기 STL map 과 set http://yoshiki.tistory.com/entry/STL%EC%9D%98-Set-Map-%EC%82%AC%EC%9A%A9 http://sang9151.blog.me/221096852868 http://blog.naver.com/4roring/221149515188 http://yoshiki.tistory.com/entry/stl-map%EC%82%AC%EC%9A%A9%EB%B2%95?category=360674 http://yoshiki.tistory.com/entry/STL-map?category=360674 http://hashcode.co.kr/questions/552/stdmap%EC%97%90%EC%84%9C-%ED%8A%B9%EC%A0%95-key%EA%B0%80-%EC.. 더보기 to_string, stoi 함수 to_string(number) : int를 string 으로 바꿔주는 함수 string s=to_string(10) 을 하면 s="10"; stoi(string) : string 문자열을 int로 바꿔주는 함수 int a = stoi(s) 를 하면 a=10; 더보기 이전 1 ··· 45 46 47 48 49 50 51 ··· 61 다음