성장 일기 - Small Step

https://www.acmicpc.net/problem/1992 풀이음..설명하기가 어려운 문제같다.우선 같은 숫자들로만 이루어져 있으면 해당 숫자만 출력을 해야된다. 혹시나 다른 숫자들이 섞여 있으면왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 구간을 나누어 같은 숫자들로만 이루어져 있으면 해당 숫자를 출력, 아니면 다시 구간을 나누어 위와 같은 순서를 반복한다. 여기서 구간으로 나누어 들어갈 때는 ()로 구간을 나누어주어야된다. 위의 구간을 보면 빨간 선으로 처음으로 구간을 나누고 다음으로 파란선 다음으로 검은선 이렇게 쪼개서 구간을 나누어 들어간다. 왜 저 입력이 (0(0011)(0(0111)01)1)인지는 설명하기 어려우니 패스하고 추가적으로 확인할만한 예제와 출력을 첨부합니다. 문제를 제대로..

https://www.acmicpc.net/problem/2089 풀이 아...이 문제는 많은 고민을 하면 스스로 풀수도 있었을 텐데...좀만 고민하다 검색을 해버렸다. 검색을 하고 느낀건 스스로 풀었으면 많은 시간이 걸렸을 거라는 것이다. 그 이유는 N이 홀수인 7일 경우 -2로 나누면 몫은 -3이 아닌 -4가 된다는 것이다.그리서 -2로 나누어줄 때 N의 나머지가 -1일 경우 몫은 (N-1)/2로 계산해주어야 된다는 것이다. 재귀를 이용하여 문제를 풀었으며, N==0일 때 return하여 함수를 나올 때 마다 1이나 0을 출력하도록 하였다. 작성한 코드123456789101112131415161718192021222324252627282930#include int N; void bi(int N){ i..

https://www.acmicpc.net/problem/1107 풀이 모든 경우의 수를 다 해보는 부르트 포스문제이다. 모든 경우의 수를 다 계산하여도 제한시간을 초과하지 않는다. 1. 여기서는 100에서 + - 버튼으로 원하는 채널까지 이동하기 위해 누른 버른의 회수 k.2. 고장난 버튼때문에 원하는 채널에서 가장 가까운 수까지 버튼을 x번 누른수 + - 버튼을 누르는 y번의 합. k와 x+y의 값을 비교하여 더 작은 값을 출력하면된다.여기서 k와 x+y는 항상 양수여야 되므로 음수이면 if문을 사용하여 양수로 바꾸어준다. 위의 1번에서 말한 k=원하는 채널 - 100; x는 예로 5000이면 5를 한 번 0을 3번 눌러야되므로 4이다.y는 목표값이 4800이고 사용 가능한 버튼으로 목표값에 가장 가..

https://www.acmicpc.net/problem/1697 풀이 목표값으로 가기위한 최단거기를 찾는 문제로 BFS문제이다. 물론 다른 방법도 있겠지만..나는 주로 최단거리 문제는 BFS로 풀려고한다. 문제에서 말하는 1초가 추가될 때마다 1층씩 더 추가해가는 것으로 생각하고 풀면된다.문제에서 x-1, x+1,x*2 총 3가지의 갈래가 있다. 여기서 방문했던 곳을 또 방문하여 큐에 저장하는 것은 불필요하므로 방문배열을 하나 더 만들어 방문 체크를 하도록하자. 작성한 코드12345678910111213141516171819202122232425262728293031323334353637383940#include int N, K, L, Q[250000], visit[100001], front = -1,..

https://www.acmicpc.net/problem/9934 풀이 문제의 이름대로 두 갈래씩 갈라지면서 주어진 조건에 맞게 트리를 출력하는 문제이다. 문제에서 주어진 입력에 대한 탐색 순서를 나타내었다. 1. 우선 트리의 가장 왼쪽 끝인 1번 노드로 간다. 2. 그 후 더 진행할 노드가 없으므로 6번 노드를 방문한다. 3. 왼쪽은 이미 방문했으니 4번 노드로 간다. 4. 4번노드 방문 후 6번 노드를 방문했으므로 3번 노드로 간다. 5. 3번 노드에서 왼쪽은 이미 다 방문 했으므로 오른쪽으로 갈래의 노드로 내려간다. 6. 이 경우로 왼쪽 끝 노드인 5번 노드를 우선적으로 방문 한다. 7. 5번 노드에서 더 내려갈 곳이 없으므로 5번 노드를 나와 2번 노드를 방문한다. 8. 마지막으로 방문하지 않은 ..

https://www.acmicpc.net/problem/1182 풀이 부분집합의 합을 구하여 입력된 S와 같은 부분집합의 개수를 출력하는 문제이다.여기서 내가 생각하는 중요한 점은 두 가지이다. 1. 부분집합을 구하는 방법2. 부분집합을 구하는 중간에 S와 같다고 개수를 카운트하면 안 된다는 것이다. 설명부분집합을 구하는 방법은 아래 그림과 같이 그래프를 그려 표현할 수 있다. 그림은 이상하지만...위의 그림처럼 입력된 배열의 값들을 사용할지 안 할지를 구분해가면서 트리의 끝에 가서 부분집합의 합을 구하여야 된다는 것이다. 마지막에 부분집합의 구해야되는 이유는 만약 N이 5, S가 3이며 입력되는 수들이 1 1 2 -1 1을 예로들면N=5, S=3, arr[5]={1,1,2,-1,1} 3=arr[0]+..

https://www.acmicpc.net/problem/11723풀이비트마스크를 이용하여 문제를 풀었다. 이번에 비트마스크를 처음 공부하여 내가 이해한 것이 맞는지는 정확한지 모르겠다. 위의 문제에서 x의 범위가 1이상 20이하 이므로 20비트로 20로 2^20가지 경우의수를 표현하는 것 같다. Ex) S는 이진수로 0000 0000 0000 0000 0000인 상태이다.여기서 1이라는 경우의 수가 입력되면 0000 0000 0000 0000 0010여기서 2이라는 경우의 수가 입력되면 0000 0000 0000 0000 0110여기서 8이라는 경우의 수가 입력되면 0000 0000 0001 0000 0110이라는 식으로 2진수로 어떤 수를 포함하고 있는지 표현해주는 것 같다. 위에는 0~19까지 표현..

https://www.acmicpc.net/problem/10971 풀이경로를 탐색하는 탐색문제이다. 처음에 출발점이 안 주어져 있어서 모든 노드를 반복문으로 출발점으로 하여 탐색을 하였다. 그러나 문제에서는 마지막에 처음 출발한 경로로 다시 돌아와야 하기 때문에 모든 노드를 출발점으로 탐색할 필요가 없었다. Ex)답이 1-2-3-4-1이라고 하면 나는 for(int i=1;i

https://www.acmicpc.net/problem/1406풀이처음에 단순히 배열을 사용하여 풀고자 하였습니다. Point라는 변수를 커서 역할로하여 L이면 Point를 왼쪽으로, D면 오른쪽으로, B면 삭제하고 0을 대입하여 출력시 0이면 뛰어 넘도록 하였습니다. 그리고 P를 입력 받으면 입력되야되는 부분 뒤로 배열을 전부 한 칸씩 이동시켰습니다. 위는 처음 생각한 풀이에서 P를 수행할 때 x가 입력되야되는 지점 뒤로 다 뒤로 한 칸씩 미루고 대입을 하였습니다. 이 경우 명령에 대한 수행과 배열을 미루는 수행으로 인해 시간 복잡도가 n^2이 되어 시간초과가 나더군요. 그래서 2개의 배열로 스택 2개를 만들어서 문제를 풀었습니다. 처음 ABCDE를 입력 받은 후 순서대로 L, D, B, P x를 수..