알고리즘131 [백준][다이나믹] 2193 이친수 현재자리에 1은 앞자리에 0으로 끝난 이친수이고, 현재 자리에 0은 앞자리에 0, 1로 끝난 이친수 모두가 가능하다. 따라서 현재자리의 1은 앞자리 0의 개수이고, 현재라리의 0은 앞자리 0 + 앞자리 1의 개수와 동일하다. https://www.acmicpc.net/problem/2193 2018. 6. 19. [백준][스택] 10828 스택 스택 문제는 배열과 현재의 위치를 나타내는 커서를 이용하여 구현할 수 있다. 배열에서 현재의 아이템 인덱스를 알리는 current 인덱스를 가지고 케이스문에서 처리하면 됩니다. 2018. 6. 19. [백준] 2606 바이러스(유니온 파인드) 2606 바이러스 문제는 "유니온 파인드" 를 이용하여 해결할 수 있다. https://www.acmicpc.net/problem/2606 2018. 4. 20. [백준][그래프] 1922 네트워크 연결(프림 알고리즘) 네트워크 연결 문제는 프림 알고리즘으로 해결할 수 있다. https://www.acmicpc.net/problem/1922 2018. 4. 20. [알고리즘] 크루스칼 알고리즘 크루스칼 알고리즘 간선중 최소값을 가지는 간선을 선택하고, 사이클이 생성되는 지를 확인하여 최소값을 구함Union-Find 알고리즘을 이용하여 처리 백준 1197 최소스패팅 트리 문제 - 크루스칼 알고리즘을 이용하여 해결http://118k.tistory.com/534 2018. 4. 20. [백준][그래프] 위상정렬 1516 게임개발 인입간선 정보를 이용하여 위상정렬로 해결한다. https://www.acmicpc.net/problem/1516 2018. 1. 25. [정올][다이나믹] 1491 자동차경주대회 도착시간 기준으로 방문했을때의 최소값을 기록하여 확인 가능하다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=763&sca=3050 2018. 1. 25. [백준][DP] 10942 팰린드롬? 펠린드롬 문제는 DP 로 풀이할 수 있다. 해결방법은 다음과 같다. https://www.acmicpc.net/problem/10942 2018. 1. 25. [백준][그래프][DAG] 1766 문제집 이 문제는 DAG 문제의 응용이다. 들어오는 간선의 개수가 0일 때 큐에 추가하여 다음 문제를 해결해 가면 된다. 쉬운 문제를 먼저 풀어야 하기 때문에 우선순위 큐(PriorityQueue)를 이용하여 처리하는 것이 더 좋다. https://www.acmicpc.net/problem/1766/ 2018. 1. 25. [백준][dp] 11066 파일합치기 파일합치기는 다이나믹 프로그래밍을 이용하여 해결할 수 있다. https://www.acmicpc.net/problem/11066 2018. 1. 24. [백준][그래프] 11403 경로찾기 경로 찾기는 배열과 BFS를 이용하여 간단하게 해결 할 수 있다. https://www.acmicpc.net/problem/11403 2018. 1. 24. [백준] 1991 트리순회 트리를 순회하는 방법을 전위 순회, 루트 -> 왼쪽 -> 오른쪽중위 순회, 왼쪽 -> 루트 -> 오른쪽후위 순회, 왼쪽 -> 오른쪽 -> 루트 https://www.acmicpc.net/problem/1991 2018. 1. 13. [알고리즘] 문제 풀이를 위해 익혀 두어야 할 것 들 알고리즘 문제 풀이를 위해서 다음의 내용은 숙지해야 문제를 풀 수 있다. 순열, 조합순열DFS, BFS다이나믹 프로그래밍LISLCS피보나치 수열트리LCA세그먼트 트리인덱스 트리 2018. 1. 12. [스크랩] 삼성 SW 검정에 도움이 되는 사이트 모음 홍준7님이 정리하신 SW 검정 시험 팁http://hongjun7.tistory.com/129 백준 사이트 문제의 풀이를 정리해 놓은 블로그Gooddday to Code 님 블로그 > 바로가기hotehrud 님의 GitHub > 바로가기코딩과 디버깅 사이 님의 블로그 > 바로가기 2018. 1. 9. [알고리즘] 큐를 이용하여 스택처럼 사용하기 큐를 2개 이용하여 스택처럼 사용 http://creatordev.tistory.com/m/83 2017. 12. 1. [백준][DP] 1149 RGB 거리 https://www.acmicpc.net/problem/1149 이 문제는 다이나믹 프로그래밍으로 해결할 수 있다. 이웃을 같은 색으로 칠할 수 없으므로집을 이동해 가면서 이전에 칠 할 수 있었던 색 중 최소값을 현재의 색의 비용으로 선택하여 다이나믹 테이블에 저장하면 된다 . 2017. 11. 15. [알고리즘] LRU(Least Recently Used) 최근최소사용 LRU는 메모리의 페이지를 교체 알고리즘 중 하나로 최근에 가장 적게 사용된 페이지를 교체 하는 것을 말한다. 사용 빈도수가 작은 페이지가 가장 적게 사용될 것이라는 것에 기반하여 교체하는 알고리즘이다. 2017. 11. 8. [백준][DP] 5721 사탕줍기 대회 https://www.acmicpc.net/problem/5721 DP를 이용하여 해결이 가능하다. 한행만 선택이 가능하므로 행마다 따로 선택할 수 있는 최대값을 계산하여 그 값을 이용하여 따로 최대값을 계산해 준다. 하나를 선택하면 다음을 걸러서 선택할 수 있으므로 점화식은 다음과 같다. dp[i] = Math.max(dp[i - 2] + dp[i], dp[i - 1]) 2017. 10. 26. [백준] 1504 특정한 최단 경로 https://www.acmicpc.net/problem/1504 이 문제는 다익스트라 알고리즘을 이용한다. 두 지점 사이의 경로를 구하기 위해서 다익스트라 알고리즘을 3번 호출하면 된다. * 주어지는 중간 지점이 어느쪽이 더 가까운지 알 수 없기 때문에 2번 호출하여야 한다. 2017. 10. 25. [백준][DP] 1463 1로 만들기 https://www.acmicpc.net/problem/1463 이 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있다. i번째 값을 만들 수 있는 경우는i-1 번째에서 1을 더하는 경우i%2 == 0인 경우에서 1을 더하는 경우i%3 == 0인 경우에서 1을 더하는 경우이다. 이 세가지 경우를 for 문을 이용하여 반복하여 해결한다. 2017. 10. 25. [백준][세그먼트 트리] 1275 커피숍2 https://www.acmicpc.net/problem/1275 이 문제는 기본적인 세그먼트 트리문제이다. 구간합을 이용하여 해결하면 된다. 변경되는 값을 잘 기록해 두면 해결 가능한다. 2017. 10. 25. [백준] 1753 다익스트라 알고리즘 다익스트라 알고리즘은 음수를 갖지 않는 유향 그래프에서 출발점과 도착점 사이의 최단거리를 구하는 알고리즘이다. 2017. 10. 12. [알고리즘] 플로이드 와샬 알고리즘(백준 11404) 플로이드 알고리즘은 그래프의 모든 꼭지점 사이의 최단거리를 구하는 알고리즘이다. - 음수 가중치를 갖는 간선도 순환만 없다면 처리할 수 있다. - 3개의 for문을 이용하여 처리한다. - 바깥 for 문은 중간지점, 가운데 for 문은 시작지점, 안쪽 for 문은 종료지점이다. 플로이드 알고리즘 설명 백준 11404 플로이드 - https://www.acmicpc.net/problem/11404 2017. 10. 12. [백준][다이나믹] 2533 사회망 서비스 다이나믹을 이용하여 해결할 수 있다. 자신이 얼리어답터일 때와 아닐때를 구분하여, 관계를 더하여 가면 해결할 수 있다. 2017. 9. 15. [백준][세그먼트트리] 6549 히스토그램에서 가장 큰 사각형 히스토그램에서 가장 큰 사각형문제는 세그먼트 트리를 이용하여 해결합니다. 2017. 9. 14. [백준][DP] 5557 1학년 1학년 문제는 DP를 이용해서 해결할 수 있습니다. 20까지의 숫자만 이용할 수 있고,+, - 연산만 할 수 있기 때문에 memo[20][연산횟수]로 메모이제이션을 하면 됩니다. 2017. 8. 23. [백준][DP] 11060 점프점프 점프 가능한 곳으로 이동가능 한 최소값을 이용하여 다이나미그 프로그래밍으로 문제를 해결한다. https://www.acmicpc.net/problem/11060 2017. 8. 23. [백준] 1005 ACM Craft 이 문제는 "위상정렬"과 메모이제이션을 이용하여 해결할 수 있다. 인입 간선이 0인 노드를 시작점으로 하여, 건물을 지을 때 걸리는 시간을 메모하여 최종 목적하는 건물을 지을 때 걸리는 시간을 확인하면 된다. https://www.acmicpc.net/problem/1005 2017. 7. 20. [정올][다이나믹] 1019 소형기관차 DP를 이용하여 해결한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=298&sca=3050 2017. 7. 7. [백준][트리] 1197 최소 스패닝 트리(크루스칼 알고리즘) 이 문제는 최소 스패닝 트리를 구현하는 방법중 크루스칼 알고리즘을 이용하여 구현하면 된다. 크루스칼 알고리즘은 그래프 사이 연결의 최소비용을 찾으면 된다. 간선을 비용순으로 정렬하고,가장작은 비용이 들어가는 간선을 사이클이 생기지 않는 순서대로 선택하면된다. 간선 사이의 사이클은 union, find 연산을 이용하여 처리한다. https://www.acmicpc.net/problem/1197 2017. 7. 6. 이전 1 2 3 4 5 다음