알고리즘131 [정올][그리디] 2499 저울 그리디 알고리즘을 이용하여 저울 문제를 해결할 수 있다. 2016. 10. 7. [정올][다이나믹] 2000 동전교환 동전교환은 다이나믹 프로그래밍으로 해결한다. 잔돈이 n 이고, c가 코인일때 f(n) = f(n - c) + 1가 된다. 현재 잔돈에서 코인을 뺀돈의 코인개수가 있다면 거기에 +1을 하게 되면 현재의 코인개수가 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1273&sca=3050 2016. 10. 4. [정올] [문제은행] 1942 하얀모자 몇명이 하얀 모자를 쓰고 있는지 찾아내는 문제이다. 말하는 사람이 하얀 모자를 쓰고 있는 경우와 쓰고 있지 않은 경우의 하얀 모자 개수를 모두 확인해서 가장 많이 나온 하얀 모자의 개수가 실제 쓰고 있는 하얀 모자의 개수이다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1215&sca=50&sfl=wr_subject&stx=%ED%95%98%EC%96%80&sop=and 2016. 9. 23. [정올][다이나믹] 1871 줄세우기 LIS 문제중 가장 간단한 형태인것 같다. 숫자들중 순서대로 나보다 큰 숫자들 중 정렬이 가장 많이 되어 있는 숫자를 찾아서 +1을 하여 기록한다. http://saecom-dalcom.tistory.com/9http://comganet.github.io/dp/2016/06/03/dp-1007http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1144&sca=3050 2016. 9. 21. [정올][다이나믹] 1539 가장높은 탑 쌓기 가장높은 탑 쌓기 문제는 다이나믹 프로그래밍을 이용하여 처리한다. 우선 밑면의 넓이 기준으로 정렬을 하면 현재 인덱스보다 작은 인덱스의 무게만 비교하면 넓이는 신경쓰지 않고 확인할 수 있다. 대신 정렬을 이용하기 때문에 기존의 인덱스가 변하게 되므로 인덱스만 따로 저장해 둔다. 그다음은 현재 벽돌보다 작은 무게의 벽돌을 찾아서 현재벽돌의 높이 + 작은무게벽돌의 높이(자신의 위에 있는 벽돌의 높이도 추가되어 있음)만 저장한다. 더 큰 높이의 벽돌이 있으면 갱신한다. 올릴 수 있는 벽돌이 없다면 자신의 높이만 저장한다. 이렇게 result 배열에 결과를 저장하고가장 높은 높이의 벽돌을 찾아서 해당 벽돌의 인덱스를 역순으로 찾아서 출력하면 된다. http://www.jungol.co.kr/bbs/board.p.. 2016. 9. 20. [정올] [다이나믹] 배낭채우기1 배낭채우기문제는 다이나믹으로 처리한다. 배낭의 무게를 10부터 이동해가면서, 현재 시점에 최고의 무게를 확인하면서, 현재의 무게를 뺀 이전 무게의 최고값과 현재의 최고값을 더하면서 배낭을 채우면 된다. 보석 배낭무게 무게 가치 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 40 - 40 40 80 90 120 150 140 190 200 230 260 270 300 3 50 - - 50 50 90 100 130 160 170 200 210 240 270 280 5 110 - - - - 110 110 150 160 190 220 230 260 270 300 10 200 - - - - - - - - - 200 200 240 250 280 맥스값 - 40 50 80 110 120 150 160.. 2016. 9. 9. [정올] [백트래킹] 1840 치즈 매시간 공기가 되는 부분을 먼저 계산하고,이전에 없어진 부분을 제거하면서 백트래킹으로 처리해 가면 처리할 수 있음 http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1113&sca=3030 2016. 9. 9. [정올] [백트래킹] 1457 영역구하기 사각형으로 표시되지 않는 영역, 빈곳을 100부터 기록해서 나중에 100 이상인 값이 몇개인지 세어서 영역을 구한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=729&sca=3030 2016. 9. 9. [정올] [백트래킹] 1824 스도쿠 백트래킹을 이용한 스도쿠 처리 0으로 입력되어 입력가능한 값을 확인해야 하는 목록을 확인후에 해당 리스트를 순서대로 순회하면서 입력 가능한 값을 확인하면서 모든 값을 입력하면 종료한다. 2016. 9. 9. [정올] [그리디] 2641 택배 택배 문제는 도착지점을 기준으로 정렬하여싣고 갈 수 있는 택배를 용량으로 확인하여 최대 값을 확인할 수 있다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1903&sca=3020 2016. 9. 9. [정올] [그리디] 1828 냉장고 화학 물질을 온도가 낮은 순으로 정렬하고 온도가 겹치면 같은 냉장고에 입력하고, 온도가 겹치지 않으면 다른 온도의 냉장고를 선택하면 냉장고를 설정할수 있다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1101&sca=3020 2016. 9. 9. [정올] [그리디] 1060 최소비용 신장트리 정올의 그리디 알고리즘 1060문제최소비용 신장트리 * 프림알고리즘을 이용하여 풀이함 최소비용의 노드를 연결하고, 현재 연결된 노드중 최소비용의 노드를 추가하면서 더 이상 방문할 노드가 없으면 종료한다. https://ko.wikipedia.org/wiki/%ED%94%84%EB%A6%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 2016. 9. 2. [정올] [그리디] 1183 동전자판기 아무리 생각해도 해결책이 생각이 나지 않았는데 다른분이 푸신 방법을보고 해결함 사용가능한 최소의 동전개수를 구하기 위해서는동전의 총합으로 사용가능한 최대값에서 구하려는 동전의 값을 뺀 나머지를 구할 수 있는최대의 동전개수를 구해서 남은 나머지가 최소의 값이 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=466&sca=3020http://m.blog.naver.com/skyblue_2002/220631970001 2016. 8. 25. [스크랩] 알고리즘 문제를 풀이하느데 도움이 되는 페이지 정올의 문제를 주로 Java 로 풀이하여 모아놓은 사이트사이트 구성, 문제 풀이 방법을 알려주는 등 구성이 좋다. http://comganet.github.io/ 2016. 8. 24. [정올] [BFS] 2261 경로 찾기 경로찾기 해밍코드 찾는 방법은 문자열을 char 배열로 변환하고, 다른 부분을 체크하여 반환한다. 2016. 7. 28. [정올] 1495, 대각선 지그재그 정올 1495번 문제대각선 지그재그 배열의 크기 n을 입력 받아서 아래와 같이 출력1 3 4 2 5 8 6 7 9 http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=767&sca=20 2016. 7. 26. [정올] [그리디] 2194 요플레 공장 그리디 알고리즘의 요플레 공장 1주일 보관하는데 드는 비용을 추가해서 최소값을 계산하면 최소 비용이 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1454&sca=3020 2016. 7. 25. [정올] [BFS] 1106 장기 이번 문제는 BFS를 활용하는 장기 문제이다. 현재위치에서 이동가능한 방향으로, 목표가 있는 방향으로 이동하면서 움직이는 횟수를 카운트 해주면 된다. 중요한 점은 BFS 를 처리하면서 큐에 중복된 값이 존재하면 입력하지 않는 것이다. 중복된 값을 입력하면 뒤로 갈 수록 처리해야할 항목이 늘어나서 타임오버가 발생한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=386&sca=3040 2016. 7. 22. [정올] [BFS] 1078 저글링 방사능 오염 저글링 방사능 문제는 방사능이 시작된 부분을 기준으로현재 방사능 발생지점을 0으로 표시하고, 상하좌우로 방사능을 퍼뜨리면 된다. BFS를 이용하여 처리하면 더욱 편리하다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=358&sca=3040 2016. 7. 21. [정올] 1707 달팽이 문자열 사각형을 한번 반복하고, 다음 사각형으로 넘어가는 것을 한 Round로 구분하고, 라운드마다 반복한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=980&sca=2010 2016. 7. 20. [정올] 1239 비밀편지 비밀편지약속한 문자를 맵에 입력하고, 입력받은 문자열을 6글자씩 띄어서 값을 검색한다. 값이 검색되지 않으면 한글자만 틀린 값이 있는지 확인한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=522&sca=2030 2016. 7. 20. 트리구조의 깊이우선탐색, 너비우선탐색 트리구조에 대한 깊이 우선 탐색과 너비 우선 탐색 BFS는 큐를 이용하여 접속할 노드의 정보를 얻고 먼저 접속한다. 2016. 7. 18. [정올] [백트래킹] 1695 단지번호 붙이기 이 문제는 백트래킹을 이용하면 금방처리한다. 1일때 상, 하, 좌, 우로 집의 개수를 세어서리스트에 보관하고 다 확인하면 그때 리스트의 내용을 오름차순으로 보여주면 된다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=968&sca=3030 2016. 7. 16. [정올] [백트래킹] 1681 해밀턴 순환회로 해밀턴 순환회로 문제백트래킹을 이용하여 해결하면 된다. 마지막에 다시 시작위치로 돌아가는 것, 방문한 곳은 다시 방문하지 않고 처리하면 금방 해결할 수 있다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030 2016. 7. 15. [알고리즘] 백트래킹 모든 경우의 수를 전부 고려하는 알고리즘상태 공간을 트리로 나타낼 수 있을 때 적합한 방식깊이우선탐색너비우선탐색최선우선탐색 재귀함수로 구현하는 경우가 많음깊이우선탐색: 스택을 이용너비우선탐색: 큐를 이용 * 백트래킹은 모든 경우의 수를 다 확인하기 때문에, 확인해야 하는 대상이 많아지면 시간이 크게 늘어난다. 따라서 가지치기가 중요해 진다. 2016. 7. 15. [정올] [백트래킹] 1889 NQueen NQueen 문제는 백트래킹을 이용하는 가장 기본적인 문제라고 할 수 있다. 풀이방법은 다음의 유튜브를 시청하면 금방 이해할 수 있다. 2016. 7. 14. [정올] [그리디] 2247 도서관 문제 정올, 그리디 알고리즘의 도서관 문제 http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1508&sca=3020 정올 도서관은 학생들을 위하여 항상 열려있다. 학생의 입장에서는 아무 때든 도서관을 찾아 공부할 수 있어 편리하지만 정올 도서관의 입장에서는 그리 효율적이지 못했다. 학생이 몇 명 되지 않는 시간에도 모든 시설을 열어야 하며 심지어 학생이 오지 않는 시간에도 도서관을 열고 있어야 했다. 이러한 문제점을 개선하고자 도서관 관리자인 창환이는 학생들의 도서관 이용 시간을 분석하고자 한다. 먼저 하루 중 도서관에 학생들이 머물고 있는 가장 긴 시간과 학생들이 다녀간 전체 시간 중 학생이 하나도 없었던 가장 긴 시간을 알아보는 것이다. 예를 들어,.. 2016. 7. 8. [정올] [그리디] 1669 소시지 공장 소시지를 너비 순서대로 정렬한 후순차적인 길이 순서대로 작업을 진행한 후, 다시 작업하지 않은 소시지를 길이 순서대로 작업한다. http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=942&sca=3020 2016. 7. 7. [정올] [그리디] 1370 회의실 배정 이 문제는 회의실 종료시간을 오름차순으로 정렬한 후, 회의 종료시간과 다음회의의 시작시간을 비교하여 순차적으로 입력한다. 회의실이 먼저 종료되는 순으로 입력하는 것이 포인트다. 2016. 7. 6. [더블릿] Koi_Budget 더블릿의 예산 문제 http://59.23.113.171/pool/koi_budget/koi_budget.php?pname=koi_budget 프로그램 명: koi_budget제한시간: 1 초국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.(1) 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.(2) 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정.. 2016. 7. 5. 이전 1 2 3 4 5 다음
