소근소근

백준 Z https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net [시간 초과 코드] int N, r, c; int cnt; void count(int sx, int sy, int ex, int ey) { //cout > c; int len = 1; for (int i = 0; i < N; i++) { len *= 2; } count(0, 0, len - 1, len - 1); } 처음에는 단순히 재귀를 돌며 0부터 구하려는 위치까지 숫자를 다..

백준 쇠막대기 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net () 는 레이저, ( 와 ) 는 막대기의 끝을 의미하므로, )가 (을 만나면 스택에서 pop하는 느낌으로 풀어야겠다고 생각은 했다 스택을 이용하면 쉽게 풀 수 있을 것 같은데 처음에 너무 어렵게 생각해서 코드를 이렇게 엄청 복잡하게 짰다.. [시간초과 나는 코드] string s; cin >> s; st.push(s[0]); int total = 0; for (int i = 1; i < s.l..

백준 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 현재 큐에 문서들이 주어졌을 때, 앞에서부터 문서를 출력한다. 단, 나머지 문서들 중에 front보다 중요도가 더 큰 문서가 있다면, 출력하지 않고 큐의 뒤로 보낸다. 일단 큐에 문서들을 차례로 집어넣고, 앞에서부터 확인을 해야한다. 나머지 문서들과 중요도를 어떻게 비교할까 하다가 우선순위 큐를 함께 사용했다. 우선순위 큐에 주어진 문서를 다 넣으면, 중요도가 큰 문서가 앞으로 오도록..

백준 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 기본적인 dfs 만 구현할 줄 안다면 풀 수 있는 문제이다. 1년씩 지나면서 빙산이 녹을 때, 처음으로 덩어리가 두개 이상이 되는 최초의 시간을 출력한다. 상하좌우 4방향 중에서 비어있는 경우(0인 경우)의 개수만큼 빼준다. 여기서 주의해야 할 점은, 현재 상태를 기준으로 보고 빼줘야 한다. (동시에 녹는다고 본다) 표시한 부분에서 2-2 = 0 이 되어도, 4부분을 볼 때는 왼쪽은 0..

백준 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 어떤 칸에서 출발하여 계속 대나무가 더 많은 쪽으로만 이동할 때, 최대로 움직일 수 있는 칸의 개수를 구하는 문제이다. 처음에 단순 DFS인줄 알고 이중 for문을 돌며 모든 칸에 대해 dfs를 돌려 최대 칸의 개수를 구했더니 시간초과가 났다. 이 문제는 재귀로 dp를 구현해서 풀면 되는 문제였다. 풀이 해법은 https://yabmoons.tistory.com/15..

level3 지만 bfs로 간단하게 해결할 수 있는 문제였다. 오히려 level2보다 더 쉬운거 같기도 하고 ,.? dog -> dot 처럼 한 char만 바꿀 수 있다. 주어진 words의 문자들의 길이는 모두 동일하다고 조건이 주어졌기 때문에 단순히 두 문자열을 앞에서부터 비교하여 다른 char가 하나만 있을때 변환이 가능하도록 한다. #include #include #include #include #include #include #include using namespace std; bool able = false; queue q; map visit; int compchar(string a, string b){ int len = a.length(); int cnt =0; for(int i=0;i

BFS/DFS 분류에 있는 문제였지만, 분리집합으로 풀었다. 컴퓨터 두대가 연결 되면 같은 네트워크(같은 집합)으로 분류되기 때문이다. 연결된 컴퓨터 두대는 union해서 같은 집합으로 보고, 마지막에 집합의 개수를 출력하면 된다. #include #include #include #include #include using namespace std; int parent[200]; map m; int Find(int x){ if(x==parent[x]) return x; return parent[x] = Find(parent[x]); } void Union(int x, int y){ int px = Find(x); int py = Find(y); if(px != py){ parent[px] = py; } }..

bfs를 이용하면 쉽게 해결할 수 있는 문제이다. queue에 -num , num 을 더해주고 큐에 push하면서 반복문을 돌고, target 에 도달하면 answer를 증가시켜서 카운트한다. #include #include #include #include #include #include #include using namespace std; queue q; int solution(vector nums, int target) { int ans = 0; q.push({0,-nums[0]}); q.push({0,nums[0]}); while(!q.empty()){ int now_idx = q.front().first; int total = q.front().second; q.pop(); if(now_idx =..