알고리즘 (56) 썸네일형 리스트형 백준 18809 <Gaaaaaaaaaarden> 씨앗을 놓을 수 있는 위치를 조합으로 구한 다음 씨앗을 퍼트려 꽃의 개수를 구하는 시뮬레이션 문제이다. 많은 시간을 들이면 풀 수 있는 문제기 때문에 빠른시간내에 방법을 생각하고 예외사항을 처리하는 게 문제였다. 문제를 해결하면서 고려해야 할 점은 두가지가 있다. 조합을 이용해 두가지 씨앗의 종류를 겹치지 않게 선택하는 방법 씨앗을 퍼트리면서 다른종류의 씨앗이 다음 차례에 동시에 위치하게 되면 꽃이 피게 되고 진행하지 않는 것 2번 부분을 처리하는게 가장 힘이 들었는데 두 개의 씨앗이 동시에 마주치는 경우를 처리해주는 방법이 어려웠다. 기본적으로 씨앗의 종류와 위치를 나타내기위한 클래스를 선언했다. 이후에는 씨앗을 놓을수 있는 장소만 배열에 넣기 위해 2인 위치를 ArrayList배열에 담아서 나타냈다... 백준 18808 <스티커 붙이기> 문제만 잘 읽는다면 많은 사람들이 쉽게 풀 수 있을 만한 전형적인 시뮬레이션 문제이다. 이 문제를 푸는데 가장 중요한것은 총 두 가지이다. 첫 번째는 스티커를 순서대로 붙이고 4방향으로 돌려서 붙여지지 않는 스티커는 넘어간다. 두 번째는 스티커를 가장 위쪽, 왼쪽에서부터 차례대로 확인하는 문제이다. 이 두 가지 방법만 잘 교려 해 준다면 쉽게 접근할 수 있는 문제이다. 기본적으로 이 문제의 최대 시간을 고려한다면 맵의 길이가 40*40이고 모든 칸을 검색한다 해도 30만이 안 되는 값이다. 4방향으로 한다고 고려하면 120만 스티커의 개수인 100을 곱해도 1억 2 천 번이기 때문에 해결할 수 있는 문제이다. 일단 나는 기본적으로 크기가 다른 배열을 넣어주기 위해서 어레이 리스트를 사용해서 2중 배열을 .. 백준 1068 <트리> 일반적으로 제목이 트리다 형태가 트리가 라고 해서 접근하면 어려운 문제 중 하나이다. 일반적으로 노드의 구성은 이렇게 2진 트리로 구성이 되어 있는데 이문제는 2진 트리라고 주어 져있지 않기 때문에 이렇게 노드 ArrayList를 노드 안에 넣어주었다. 또한 안의 ArrayList를 으로 해준 것은 이해를 돕기 위해서이니 ArrayList 로 인덱스 값만 넣어주면 되는 부분이다. 앞의 설명처럼 여러개의 노드를 자식으로 가질 수 있는 class를 만들어 주었다. 다음은 총 노드의 개수만큼 배열을 완성해주고 입력받은 값이 -1이 될 경우 시작점으로 선택을 하고 나머지는 입력값에 현재 위치를 추가해주었다. ※이 부분에서 중요한 점은 이문제는 하나의 트리이기때문에 -1 값이 두 개가 될 수 없다! 또한 이문제를.. 백준 1941 <소문난 칠공주> 문제를 처음 잘못 이해해서 한참 헤맷던 문제! 25명 중에 7명을 고르는 문제다. 그러나 처음 이해했던 방식은 어떤 지점에서 DFS를 이용해서 탐색해서 발생할 수 있는 경우를 고르는 문제인 줄 알았지만 아쉽게도 결과는 실패. 이러한 문제는 일반적으로 DFS 또는 BFS로 접근을 하다보니 문제에 접근하기 어려웠던 문제이다. 이 예제의 경우에도 이렇게 두가지 방법이 존재할 것이다. 그래서 떠오른 방법은 25개 중 7개를 뽑는 조합 문제인것이다!! 그래서 생각해낸 접근방법이 25개 중 7개를 고르는데 "Y" 임도연 파의 개수가 4개와 같거나 크면 실패이기 때문에 이점을 중점으로 조합을 생성했다. 일단 25개의 String을 만들어서 차례대로 글자를 하나씩 넣었다 또한 int 형의 resul 배열을 생성해서 7.. 백준 2206 <벽 부수고 이동하기> 단순하게 생각하고 구현하면 되는 전형적인 BFS, DFS문제!! 벽을 한 번까지 부수고 종점까지 가면 되는 문제 생각했던 방법은 총 2 가지 방문한 배열을 visit [][][] 이렇게 구현해서 3차원 배열을 만들어 방문처리를 해서 종점까지 가는 방법 dfs를 이용해서 한번 까지만 뚫고 갈 수 있게 설정해서 목적지를 탐색한다. 이 중에 첫번째 방법을 사용해서 구현을 했다. 우선은 좌표와 총 걸린 시간을 나타내는 t와 벽을 몇 번 부쉈는지를 표시하기 위한 num 변수로 클래스를 구성했다. 또한 다음 이동을 담을 Queue를 생성하고 visit의 z열 좌표는 0,1 두 가지로 벽을 1번 부순 것과 안 부순 것의 차이를 나타내기 위해 사용했다. 또한 목적지에 도달할 수 없는 경우가 있기 때문에 result는 .. 백준 19542 <전단지 돌리기> 문제의 중점은 그래프를 이해하고 리프 노드에서부터 시작해서 거리가 D거리 이하인 부분은 제외한 뒤 왕복하는 거리를 구하는 문제다. 그래프를 나타내기 위해 우선적으로 각각의 노드가 연결된 노드를 넣어줄 ArrayList 배열을 만든 뒤 삽입했다. 이 부분을 이해하기 위해서는 백준의 2644번 촌수 계산 문제를 풀어보는 것이 도움이 된다! www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진� www.acmicpc.net 그 후 dfs를 이용해서 return 하는 값을 이용해 시작.. 이전 1 ··· 3 4 5 6 다음
