전체 글

[C++] 백준 1620번 문제풀이

이 문제를 보고 든 생각은 map 이나 vetor를 이용하여 풀어야 겠다 라고 생각하였다. 구현 자체는 어렵지 않았지만 생각해야 할 것이 시간초과를 하지 않게 해야 하는데 vector나 map 을 이용할때 for 문을 가지고 첫번째 요소부터 마지막 요소까지 확인하는 것은 매우 시간(O(N))을 많이 잡아먹는다. 따라서 다른 방법을 찾아야 했는데 map 을 두개 사용하거나 map 하나 또는 배열을 이용하여 푸는 것 이였다 두가지 다 사용하여 풀었으나 여기엔 map 과 배열을 이용한 풀이를 적어놓았다. ios_base::sync_with_stdio(0); cin.tie(NULL); 이 문장을 왜 쓰는줄 몰랐는데 찾아 보니까 C++ 알고리즘을 사용할 때 시간을 줄일 수 있다고 한다. (계속 똑같은 코드여도 위..

[C++] 백준 1463번 문제풀이

이 문제를 보면서 생각했던 점은 2,3 이 나오므로 6의 배수를 고려하여 풀고 입력 받은 수를 나눠가면서 풀자 였다. 그러나 문제를 풀다보니 입력 받은 수를 나눠서 풀기엔 순서를 고려하기 어려웠다 예시에 나온것 처럼 10 -> 9 -> 3-> 1 10 -> 5 -> 4-> 2->1 위와 같이 10에서 바로 2로 나누는것이 아닌 1을 빼고 3으로 나누는것이 연산 수가 적게 나오고 16 -> 8 -> 4 -> 2 -> 1 16 ->15 ->5 -> 4 -> 2 -> 1 위와 같이 16에서 1을 빼고 나누는것이 아닌 바로 2로 나눠서 푸는것이 연산 수가 적게 나왔다. 나눠서 풀기엔 적합하지 않은 문제였다. 그래서 연산을 하면서 풀기로 하였는데 여기서 DP (동적 프로그래밍)을 사용하여서 풀어야 한다는것을 알게..

[C++]백준 1074 번 문제 풀이

처음 문제를 풀때 2차원 배열로 풀려고 했으나 2차원 배열의 크기를 넘어가는 케이스가 있어서 재귀를 사용하여 풀었다. Z방향으로 움직이며 큰 사각형을 4등분하여 Z방향으로 이동하기 때문에 2사분면 -> 1사분면 -> 3사분면 ->4사분면 이런식으로 재귀하게 만들었고 주어진 r,c 와 같으면 count 를 출력하게 하였다. 문제 풀면서 생각해야 할 것 들이 있었는데 1. 어떤 범위내에 있을 때 재귀를 해야하는가 ? 2. Z 방향을 어떻게 표현할 것인가 ? 이 두가지 였다. 첫 번째는 현재 위치를 좌표로 표현했을 때 사각형 내에 r,c 가 좌표로 찍힐 수 있어야 하고 두 번째는 사분면을 이용하여 해결하였다. 재귀와 더 친해져야겠다...(나중에 DFS 문제 풀 때 헷갈리지 않도록) #include #inclu..

프로그래머스 전화번호 목록 문제 풀이

처음 문제를 보았을 때 제일 먼저 생각한것이 phone_book 안에 있는 요소들을 하나씩 비교해서 첫 번째 요소가 다른 요소들의 접두사가 된다면 비교를 끝내고 false 를 return 하고 끝이라고만 생각했다 문제를 풀면서 몇가지 문제들이 있었는데 내가 생각하지 못한 부분은 첫 번째 요소의 size가 요소들중 제일 짧은 요소가 아니란 점 answer 를 true 로 두었을 때 첫 번째 요소만 돌고 끝날 수 있다. 이를 해결하기 위해 첫 번째 요소가 제일 짧은 요소가 되게 sort 함수를 이용 하였고 check 를 사용하여 첫 번째 요소만 돌고 끝내지 않게 하였다. 다른 사람의 풀이를 보았을때 substr를 이용할 수 있었으면 훨씬 빠르고 간결하게 풀 수 있었을 것 같다. 다음 부턴 string을 비교..