본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

Algorithm143

[DFS, 난이도 중하] 프로그래머즈, 타겟 넘버 문제 설명에 쓰인 예제를 예로 들어 풀이 하겠다. □1□1□1□1□1 = 3에서 □에 +/- 를 넣어 3을 만들 수 있는 경우의 수를 계산하면 되는 문제이다. 이를 해결하기 위해서, 뒤에 있는 □일 수록 깊이가 커지는 DFS를 수행하면 된다. 예를 들면 탐색 순서는 +++++ ++++- +++-+ +++-- ++-++ ...... 이런 식인 것이다. DFS의 깊이가 numbers의 크기와 같아지면 리턴을 하되, 누적 값이 target과 같다면 리턴하기 전에 answer에 1을 더하고 target과 같지 않다면 그냥 리턴만 해버리면 된다. 테스트 케이스 8개 모두 통과 #include using namespace std; int answer; void dfs(int sum, int depth, vector.. 2020. 9. 29.
[BFS, 난이도 중하] 프로그래머즈, 네트워크 BFS를 돌며 연결된 간선은 모두 방문 처리를 해주고, 더 이상 방문할 노드가 없을 경우 중단 한다. 모든 컴퓨터를 탐색하면서, 아직 방문하지 않은 컴퓨터일 경우 BFS를 시작해주고, BFS를 새로 시작할 때마다 answer를 1씩 증가시키면 문제가 해결된다. 한번 BFS를 수행하면, BFS의 시작점 컴퓨터와 같은 네트워크안에 있는 모든 컴퓨터가 방문처리 되는 것이다. 즉, answer = BFS 수행 횟수 가 되는 것이다. 테스트 케이스 13개 모두 통과 #include #include using namespace std; bool visited[201]; vector a[201]; queue q; void bfs() { while(!q.empty()){ int x = q.front(); for(int.. 2020. 9. 29.
[DFS, 난이도 중] 프로그래머즈, 단어 변환 begin을 시작점으로 두고 words중에서 현재 단어와 알파벳 하나만 차이나는 단어로 변환해 나가며, 최소 몇 번째 변환만에 target이 되는가 계산하는 문제이다. target이 될 때 까지 연속으로 변환한다는 점에서 DFS문제라는 것을 알았다. 문자열 a,b가 알파벳 하나만 차이나는가 여부를 판단하기 위해 connect 함수를 만들었다. 먼저 connect 함수를 이용하여 begin과 words를 비교해나가며 참일 경우 간선을 설정한다. 다음에는 words단어끼리 간선을 설정한다. 그리고 편리를 위해 정점마다 번호를 매겨주었다. target은 정점 번호를 0으로 정했고, words의 i번째 단어의 정점 번호를 i+1로 매겼다. words에서 target이 있는 위치를 알기 위해 target_inde.. 2020. 9. 29.
동적계획법 고득점 kit 풀이 완료, 후기 코딩 테스트, 대회를 위해 대비해야 하는 필수 알고리즘중 하나이다. 동적계획법은 바로 해답을 구하는 것이 아니고, 이전에 계산했던 값을 활용하는 알고리즘이다. 동적계획법 문제는 대체로 코드가 짧지만 점화식을 세우기 어렵다는 특징이 있다. 백준에서 문제풀이를 제일 많이 했던 알고리즘인 만큼 레벨4(도둑질)에 해당하는 문제도 크게 어렵지 않게 풀었다. 프로그래머즈 문제들 뿐만 아니라 여러 동적계획법을 이용한 문제들도 포스팅 해두었으니 필요하면 참고해도 좋을 것이다. 모든 문제 [난이도 중상] 도둑질 kimcoder.tistory.com/92?category=879353 [난이도 중하] 등굣길 kimcoder.tistory.com/123?category=879353 [난이도 하] 정수 삼각형 kimcoder... 2020. 9. 28.
[동적계획법, 난이도 중하] 프로그래머즈, 등굣길 프로그래머즈의 효율성 테스트에서 숫자가 매우 커지면 실패를 출력한다는 것을 깨달았다. %1000000007을 하지 않았더라도 정확성은 만점이지만, 효율성은 0점이 나온다. 레벨3답지 않게 접근법은 매우 간단하다. dp[x][y] = (1,1) 부터 (x,y) 까지의 최단 경로의 수 맨 처음에는 dp[1][1]을 1로 두고 시작한다. 시작점=도착점이라면 경로의 경우의 수가 1이기 때문이다. 오른쪽과 아래쪽 영역을 탐색해가며 현재 영역의 dp값을 그대로 탐색중인 영역의 dp값에 더해주면 된다. 물론 탐색한 영역에 물이 있다면 더해주지 않으면 된다. 테스트 케이스 10개 정확성, 효율성 모두 만점 #include using namespace std; long long dp[101][101]; bool wate.. 2020. 9. 28.
[DFS, 난이도 중상] 프로그래머즈, 여행경로 여태 백준에서 DFS/BFS 문제를 풀 때는 노드명을 정수로 두고 풀었는데.. 노드명이 문자열이라 적응이 잘 안됐다. C++ vector의 요소들은 정수로된 인덱스로 다룰 수 있는데 , 이번 문제에서는 벡터만으로 풀기에는 꽤 난이도가 있어보였다. 그래서 파이썬의 딕셔너리와 유사한 기능을 하는 C++의 map의 도움을 받았다. map은 key와 value쌍으로 되어있는 구조이다. 하나의 출발점에서 여러 경로로 이동하는 경우를 고려해야 하므로 value에는 여러 요소를 담을 수 있는 vector을 넣기로 했고, 그 vector안에서도 도착점 정보 뿐만아니라 방문 여부까지도 알 수 있게 pair로 도착점, 방문여부 쌍을 이루었다. 모든 도시를 방문 해서 티켓을 모두 소진이 되었음을 확인 할 때 까지 dfs를 .. 2020. 9. 24.
완전탐색 고득점 kit 풀이 완료, 후기 완전탐색을 브루트 포스(brute force)라고도 많이 부르고, brute는 무식한 이라는 뜻이다. 알고리즘 설명에도 마침 '무식해 보여도 사실은 최고의 방법일 때가 있지요.' 라고 되어있다. 브루트 포스는 정말 특별한 접근법 없이 무식하게 모든 경우를 탐색하면 된다. 이 알고리즘의 장단점에 대해 설명하자면, 장점 : 다른 알고리즘에 비해 머리를 많이 쓰지 않아도 된다. 단점 : 모든 경우를 탐색하는 방법이다보니 시간복잡도가 크다. 브루트 포스 문제에서는 데이터 범위를 크게 주지 않는 편이다. 브루트 포스에서는 간단한 반복문만 써도 되는 경우도 있지만, 순열이나 조합을 써서 모든 경우를 탐색해야 하는 경우도 많다. 본인이 순열, 조합에 대해 정리한 포스팅 링크를 남겨두었으니 참고하면 좋을 것이다. 순열.. 2020. 9. 24.
[완전탐색, 난이도 하] 프로그래머즈, 모의고사 세 학생의 문제를 찍는 주기를 파악해야 하는 문제이다. 1번 수포자는 (1,2,3,4,5) 를 반복하여 찍고, 2번 수포자는 (2,1,2,3,2,4,2,5) 를 반복하여 찍고, 3번 수포자는 (3,3,1,1,2,2,4,4,5,5) 를 반복하여 찍는다. 주기는 각각 5,8,10 이다. 시험은 총 answers.size() 문제가 있고, %(나머지 연산자)를 이용하여 주기 사이클을 돌려가며 답과 비교하면 된다. 테스트 케이스 14개 모두 통과 #include using namespace std; int maxi(int a,int b){ if(a>b) return a; else return b; } int select_group1[5] = {1,2,3,4,5}; int select_group2[8] = {2,.. 2020. 9. 24.
next_permutation을 이용한 조합 구현 #include #include #include using namespace std; vector arr; vector check; void set_check(int n, int r){ for(int i=0;i 2020. 9. 23.

티스토리툴바