목록c++ (497)

1일1알

백준 1446번 지름길 C++

D까지 가는 최소 거리를 구하는 문제이다. 역주행은 불가능하다. dp방식으로 해결하였다. 처음에는 거리를 지름길을 고려하지 않고 초기화해주고 지름길들의 도착 위치를 기준으로 정렬한 뒤, 도착 전의 위치들을 검사하면서 도착 위치까지의 최소 거리를 찾아서 지름길을 이용한 최소 거리들을 구하고, 마지막에는 처음부터 D까지 검사하면서 최소 거리를 찾는 방식으로 문제를 해결하였다. 풀고 나서 시작 위치를 기준으로 정렬해도 맞았는데, 이유는 잘 모르겠다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef l..
알고리즘 2021. 12. 8. 12:28
백준 5904번 Moo 게임 C++

moo 문자열을 간단하게 숫자로 나타내 보겠다. moo는 3, mooo는 4, mooooo는 5 이런 식으로 사용할 것이다. moo 수열은 3 -> 3 4 3 -> 3 4 3 5 3 4 3 이런 식으로 증가하게 된다. n을 입력받아서 n이 수열의 길이보다 크다면 수열의 길이를 규칙에 맞춰서 늘리고, n이 수열의 길이보다 작다면 n의 값을 재조정하고 수열의 길이를 축소해가면서 문제를 해결하였다. 처음에는 직접 수열을 구현해보았는데, 그런 식으로 문제를 풀면 메모리 초과가 난다. 따라서 규칙에 맞춰서 특정 위치의 문자를 구하는 식으로 문제를 해결해야 한다. #include #include #include #include #include #include #include #include #include #inc..
알고리즘 2021. 12. 7. 12:31
백준 15662번 톱니바퀴 (2) C++

회전시킬 톱니바퀴와 회전 방향을 입력받고 해당 톱니바퀴는 회전시킨 뒤, 회전시키기 전의 톱니바퀴와 맞닿아 있는 톱니바퀴가 같다면 맞닿아 있는 톱니바퀴는 회전시키지 않고, 다르다면 반대방향으로 회전시킨다. 이것을 반복하다가 회전이 끝났을 때 12시 방향에 있는 S극의 톱니바퀴의 개수를 구하는 문제이다. 문제를 푸는데 어려움은 딱히 없었던 것 같은데 시간은 조금 걸린 것 같다. 엄청 쉬운 문제는 아닌 것 같은데 단순히 구현만 하면 돼서 그런지 정답률이 73퍼센트나 된다는게 놀랍다. #include #include #include #include #include #include #include #include #include #include #include #include #include using names..
알고리즘 2021. 12. 6. 15:13
백준 2002번 추월 C++

들어간 차들은 벡터를 이용해 순서대로 문자열을 저장해서 들어간 순서로 차의 번호를 접근할 수 있게 만들었고, 나온 차들은 unordered_map 를 이용해 차의 번호로 나온순서를 접근할 수 있게 만들었다. 들어간 차들을 검사하면서, 자신보다 먼저 들어온 차들 중 하나라도 자기보다 늦게 나왔다면 추월을 한 것이다. 들어간 차들을 순서대로 검사하면서 그 차의 번호를 이용하여 나온 차들의 순서를 접근하여 비교하면 문제를 해결할 수 있다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long lo..
알고리즘 2021. 12. 5. 12:52
백준 11568번 민균이의 계략 C++

문제를 한줄로 요약하자면 가장 긴 증가하는 부분 수열을 구하는 것이다. 다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 처음에 수열의 길이를 저장하는 dp테이블을 모두 1로 초기화 시킨다. (자신만 있을 경우 수열의 길이는 1) 원소들을 처음부터 검사하면서 자신의 앞에 있는 모든 원소들을 비교하다가 만약 자신보다 값이 작은 값을 찾으면 자신이 그 수열에 포함된다면 증가하는 수열의 길이가 늘어나는 것이기 때문에 찾은 값의 수열의 길이 중 가장 큰 값을 저장한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;..
알고리즘 2021. 12. 4. 12:59
백준 1342번 행운의 문자열 C++

백트래킹을 이용하여 위치를 재배치한 모든 문자열을 구할 수 있다. 첫 번째 예제는 abababa 라는 문자열 하나만 행운의 문자열이지만, 답을 구해보면 144가 나오는데, 그 이유는 abababa 라는 문자가 144번 중복되어서 나오기 때문이다. 이를 해결하기 위해 a의 개수 4, b의 개수 3을 팩토리얼 연산을 하고 곱해준 뒤 답에서 나눠주어야 한다. 4! = 24, 3! = 6이고 24*6 = 144이다. 처음에 구한 답이 144이고 이것을 144로 나누면 1이 나온다. 알파벳의 각각의 개수의 정보를 저장하는 데 unordered_map 자료구조를 사용하였다. #include #include #include #include #include #include #include #include #includ..
알고리즘 2021. 12. 3. 13:01
이전 Prev 1 ··· 79 80 81 82 83 Next 다음