알고리즘/문제풀이 - 백준

백준 15652 N과 M (4)

문제 : https://www.acmicpc.net/problem/15652 풀이 N과 M (1), (2), (3) 문제를 합한다. N과 M (1) : https://hydroponicglass.tistory.com/64 N과 M (2) : https://hydroponicglass.tistory.com/65 N과 M (3) : https://hydroponicglass.tistory.com/66 (1)을 통해 전체적인 코드를 구현한다. (2)를 통해 내림차순인 수열은 제거한다. (3)을 통해 중복 수열도 출력하게 만든다. 구현 //c++ #pragma warning(disable:4996) #include #include int n, m; int visited[9]; int seq[9]; void df..

2019. 8. 28. 12:20
알고리즘/문제풀이 - 백준

백준 15651 N과 M (3)

문제 : https://www.acmicpc.net/problem/15651 서론 N과 M (1)번 문제에서 중복 되면 안되는 조건이 빠졌는데, 마찬가지로 코드에서도 중복조건을 주석처리하면 끝난다. 나와 다른 방향으로 푼 사람들을 위한건지 문제의 의도를 잘 모르겠다. 아이디어 N과 M (1)을 풀고 난 후 중복조건을 주석처리하면 된다. N과 M (1) : https://hydroponicglass.tistory.com/64 구현 //c++ #pragma warning(disable:4996) #include #include int n, m; int visited[9]; int seq[9]; void dfs(int value, int idx) { //std::cout

2019. 8. 28. 12:13
알고리즘/문제풀이 - 백준

백준 15650 N과 M (2)

문제 : https://www.acmicpc.net/problem/15650 풀이 N과 M (1)을 풀고 난 후 수정하면 된다. N과 M (1) : https://hydroponicglass.tistory.com/64 1번문제에서 수열을 오름차순으로 출력하라는 조건이 추가되었다. 만약 1 2 1 3 1 4 2 1 2 3 2 4 ... 로 출력되면 1 2 1 3 1 4 1 2 2 3 2 4 ... 로 바꿔줘야한다. 위에서 2 1을 1 2로 바꿔주면 기존에 이미 출력했던 1 2 와 중복된다. 오름차순으로 정렬하면 중복되는 수가 반드시 존재한다. 그러므로 내림차순으로 출력된다면 그냥 출력하지 않으면 되는 조건문을 추가해주면 된다. 구현 //c++ #pragma warning(disable:4996) #incl..

2019. 8. 28. 12:06
알고리즘/문제풀이 - 백준

백준 15649 N과 M (1)

문제 : https://www.acmicpc.net/problem/15649 서론 DFS와 백트래킹 문제 아이디어 n이 4이고 m이 2인 예제면 DFS를 이용해서 위 그림과 같이 모든 경우의 수를 출력하게 할 수 있다. DFS함수는 반복문으로 1~n의 값을 가지는 DFS를 불러오고 DFS를 불러올 때마다 우측으로 자리수를 한자리씩 옮기도록 인덱스를 1씩 증가시켜주면 된다. 그런데 문제에서 중복없이 출력하라는 조건을 줬기 떄문에 우측으로 인덱스가 증가할때마다 선택된 값은 방문처리해주고 만약 방문처리 된 값을 다시 접근하면 그대로 리턴시킨다. 구현 //c++ #pragma warning(disable:4996) #include #include int n, m; int visited[9]; int seq[9]..

2019. 8. 27. 16:50
알고리즘/문제풀이 - 백준

백준 2206 벽 부수고 이동하기

문제 : https://www.acmicpc.net/problem/2206 서론 크게 어렵게 생각 안했는데 시간초과를 연타로 맞았다. DFS로 구현했다가 시간초과 같은 아이디어를 BFS로 구현했다가 시간초과 방문배열을 3차원으로 만들었는데 시간초과 큐에서 꺼낸 후 방문체크에서 꺼내기 전 방문체크로 수정해서 통과 많은걸 얻어가는 문제다. 풀이과정 기존의 이동할 곳이 0이면 방문하고 1이면 방문하지 않는것에서 조건을 하나 추가해준다. 1이더라도 내가 지금까지 벽을 뚫은적이 없다면 벽을 뚫은 후 다시는 벽을 뚫지 않겠다고 공표하고 방문한다. 따라서 방문할때마다 내가 기존에 벽을 뚫었는지 안뚫었는지 확인을 해야하므로 확인할 수 있는 변수를 큐에 좌표와 함께 넣어준다. 여기까지가 내 아이디어였는데 그 후 수많은 ..

2019. 8. 26. 19:13
알고리즘/문제풀이 - 백준

백준 1012 유기농 배추

문제 : https://www.acmicpc.net/problem/1012 서론 dfs(재귀)로 풀이 풀이 1. 모든 칸을 일일이 확인해서 배추가 심어져있는 칸만 dfs를 실행한다. 2. dfs가 실행되면 출력값을+1해주고 dfs로 만들어진 영역은 전부 0으로 만들어줘서 이 영역은 다시 dfs가 실행되지 않게 한다. (dfs가 재귀를 불러올 때 재방문하지 않게 하는 목적도 있다.) 3. 출력값을 출력한다. 4. 아래 코드는 지렁이를 발견할때마다 cnt를 +1 해줘서 cnt가 k값이랑 같아지면 남은 칸을 확인하지 않는 코드를 넣었는데, 없어도 무방하다. 구현 //c++ #pragma warning(disable:4996) #include #include int map[51][51]; int dy[4] = ..

2019. 8. 25. 13:33