탐색
-
19236.청소년상어알고리즘/백준 BAEK JOON 2020. 9. 9. 03:09
이번에 풀어볼 문제는 백준 19236 청소년 상어이다. 괜찮은 문제인거 같다. 문제를 어느정도 풀면서 갑자기 느낀 것인데 정답률은 난이도가 아닌거 같다. 정답률이 높은 문제들은 구현만 제대로하면 다른 예외처리 같은 것이나 함정(히든케이스)같은 것이 없는 문제라 정답률이 높고 낮은 문제들은 함정(히든케이스)가 있어서 낮은거 같다는 생각이 들었다. 여튼 이 문제는 시뮬레이션 문제이다. 이 문제에서 얻어갈 수 있는 것은 idx에 대한 내용을 굳이 구조체의 변수로 가져가는 것이 아니라 배열의 순번으로 가져는 방법도 괜찮은 방법이다. 그리고 함수 로직의 순번에 대한 내용이다. 당연한 이야기지만 여러 함수들을 구현해야할 때는 큰 함수와 작은 함수에 대한 구별이 필요하고 큰 함수 속에 작은 함수가 들어가도록 구현하는..
-
1932.정수 삼각형알고리즘/백준 BAEK JOON 2020. 8. 19. 21:37
이번에 풀어볼 문제는 백준 1932번 정수 삼각형이다. 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 정말 쉬워보이지만 자신의 인접한 대각선의 숫자로만 합을 구해야한다는 점을 해결해야만 이 문제를 풀 수 있다. 이 문제를 푸는 방법은 대표적으로 DP 동적계획법을 사용하는 것이다. * 제일 꼭대기의 값 부터 값을 누적해서 진행하되 겹치는 부분은 둘 중 큰 값으로 누적하면 된다 * 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..
-
2105.디저트 카페알고리즘/SW Expert Academy 2020. 6. 27. 12:05
이번에 풀어볼 문제는 SW Expert 2105번 디저트 카페이다. 재귀함수를 이용해서 풀면 간단히 풀리지만 중요한건 역시나 설계이다. 어떻게하면 불필요한 계산을 줄일지 고민해보고 풀어야한다. SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 각 모서리 값은 굳이 탐색을 할 필요가 없다 => 우리가 탐색하는 형태는 마름모 모양이므로 각 모서리는 탐색을 할 수 없다는 것을 인지 2. 항상 탐색의 시작은 아래로만 탐색하면된다. => Point !! => 탐색은 왼쪽에서 오른쪽으로, 윗줄부터 아랫줄로 탐색이 진행되는데 그림을 그려보면 알겠지만 윗줄에서 탐색한 내용들은 전부 아랫줄에서 위로 탐색하는 부분과 일치한다..
-
5656.벽돌깨기알고리즘/SW Expert Academy 2020. 6. 12. 00:53
이번문제는 SW Expert의 벽돌깨기이다. 정답률은 60% 정도지만 솔직히 말도안되는거같다.. 난이도가 상당히 높게 느껴졌고 정답률이 크게 의미가 없다는 생각이 들었다... (내가 못하는건가.. 쩝..) 구현은 하나하나씩 필요한 것들을 구현했고 어떻게 푸는 줄은 알겠는데 아직도 구현이 안되는 부분들이 있었다. 그런 부분들은 구글링을 통해서 진행했다. 그럼에도 불구하고 테스크케이스 50개중 47개만 맞았다.. 결국 질문을 올렸고 check 배열을 초기화하는 순서가 잘못되었다는 것을 알게되었다 ( 답변자분 감사합니다ㅠ ) SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 자체는 어렵다는 생각이 들지만 도움은 ..
-
2117.홈 방범 서비스알고리즘/SW Expert Academy 2020. 6. 6. 21:30
이번에 풀어볼 문제는 SW Expert 2117 홈 방범 서비스다. 난이도는 역시나 그렇게 어려운 거같진 않지만 이번에 느낀점은 역시 예외상황을 확인하려면 예시를 잘봐야한다. 이 문제에서 나의 실수는 탐색에 있었다. 이 문제는 전부다 탐색을 해봐야 하는데.. 나는 집위주로만 탐색을 했다. 허허허.. 여튼 다시수정했으니 됐지만... SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 탐색을 언제 끝마칠지 판단해야함 => 서비스 범위가 맵을 넘어서면 정지 2. 언제 최대값을 가져갈지 생각해야함 => 이득 - 운영비용이 적자가 나지 않으면 해당 값을 최대치와 비교 3. 탐색하는 좌표에 집이 있는 경우 => 집 갯수..
-
1949.등산로 조성알고리즘/SW Expert Academy 2020. 6. 3. 22:51
이번에 풀어볼 문제는 SW Expert의 1949 등산로 조성이다. ( 아래링크는 SW Expert 로그인하고 눌러야함.. ) SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 난이도는 높지않지만 한 가지를 빼먹어서 테스트 케이스 50개중 48개만 맞았다.. 제엔자앙!!!!!!! => 완벽한 설계인줄 알았는데... 닿을 듯 말 듯하네.. ㅎㅎ 여기서 중요한 점은 깎는 점에 대한 처리인데 언제깎아야할지는 생각보다 간단하다. 0. 제일 높은 봉우리를 찾고난 뒤 => 제일 높은 봉우리 일때만 해당좌표를 시작으로 탐색을 진행한다. => 탐색(BFS)은 재귀함수로 진행!! => 그렇지 않으면 c..
-
5644.무선충전알고리즘/SW Expert Academy 2020. 6. 2. 22:57
이번에 풀어볼 문제는 SW Expert의 5644 무선충전이다. ( 아래링크는 SW Expert 로그인하고 눌러야함.. ) SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 결론은 설계실패로 문제를 풀지 못했다 => 다른분의 블로그를 참조하여 공부함 : https://swjeong.tistory.com/162 3시간을 초과했고 설계실패의 이유는 한가지를 간과했다. 1. BC의 범위를 배열에 표시했다. 2. A사용자와 B사용자가 중복되는 구간을 따로 배열을 만들어 표시했다. 3. 중복구간을 제외한 나머지 구간의 합을 구했다. 4. 설계 실패가 발생한 지점 => 중복구간에서 어떤 BC들이 ..
-
14503.로봇청소기알고리즘/백준 BAEK JOON 2020. 6. 1. 00:51
이번에 풀어볼 문제는 백준 14503 로봇청소기이다. 시뮬레이션 분류의 문제이며 문제 이해만 잘하면 풀 수 있는 문제이다. 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 하지만 제대로 이해못하거나 설계를 잘못하면 미궁속에 빠져서 푼거 또 풀고 푼거 또 풀게된다... 나 역시 1주일전에 풀다가 틀린 부분을 못찾아서 1주일 후에 다시 푸는데 성공했다(그사이에 늘긴 늘었다보다..) 내가 실수했던 부분은 후진에 대한 내용이다. 4방향모두 갈곳이 없을 때 청소한 곳을 지나갈 수 있는 방법은 후진뿐인데 잘못이해해서 후..