본문 바로가기

분류 전체보기

 (341)
[디자인패턴] 스테이트 패턴 책을 공부하며 새로운 문제를 만들고 구현한것을 기록한 게시글입니다. (이해한 내용을 바탕으로 작성했기 때문에, 내용이 정확하지않고 틀린부분이 있을수있으며, 예시가 패턴을 사용하기에 알맞지 않을수도있습니다) 스테이트 패턴 객체의 상태에따라 객체의 행동이 변경된다. 객체를 사용하는 클라이언트 입장에서는 객체가 하는 행동이 완전히 바뀜으로써 자신이 호출하는 객체의 클래스가 바뀌는듯한 느낌을 받는다. 스트레티지 패턴과 상당히 유사한 패턴이다.(책에서도 이렇게 설명한다.) 스트레티지 패턴과의 차이점이라면, 우선, 사용 용도가 다르다는점이다. 스테이트 패턴은 상태에 따라서 행동을 동적으로 바꿔주기위해 사용하는 반면, 스트레티지패턴은 사용중 알고리즘군을 변경시켜주기위해 사용한다. 쉽게 생각해서 클라이언트가 객체의 행..
[디자인패턴] 컴포지트 패턴 책을 공부하며 새로운 문제를 만들고 구현한것을 기록한 게시글입니다. (이해한 내용을 바탕으로 작성했기 때문에, 내용이 정확하지않고 틀린부분이 있을수있으며, 예시가 패턴을 사용하기에 알맞지 않을수도있습니다) 컴포지트 패턴 - 클라이언트에서 객체컬렉션과 객체를 똑같이 처리한다. 쉽게말해, 객체를 담고있는 객체컬렉션과 객체컬렉션에 담겨있는 객체에대해서 똑같은 처리방법으로 접근할수있다는것이다. 트리 자료구조를 생각하면 이해가 쉬운데, 노드 D의 자식노드 E,F,G가 있다고하자. 이때, E, F, G는 D에 담겨있는 객체이고, D는 E,F,G를 담고있는 객체 컬렉션이다. 하지만, D는 항상 객체컬렉션이 아닐수도있다. D또한 어떠한 노드(A,B,C)의 자식중 하나일수있기때문이다. 즉, 각 노드를 객체이자 객체컬렉션..
[백준 / BOJ] 1242 소풍 (Java) 문제 출처 : https://www.acmicpc.net/problem/1242 1242번: 소풍 첫째 줄에 N, K, M가 주어진다. N과 K는 5,000,000보다 작거나 같은 자연수이고, M은 N보다 작거나 같다. www.acmicpc.net 소풍을간 사람의 수 N 제거될 사람의 번호 K 동호의 번호 M 이 주어진다. 사람들이 원형으로 둘러앉아 순서대로 번호를 외칠때, K를 외친사람이 탈락하고, 이후 남은사람들끼리 다시 게임을 시작한다. 동호는 자신이 몇번째에 탈락할지 궁금하다. 동호가 몇번째에 탈락하는지 구하는 프로그램을 만들자. 풀이 어려웠던 문제다. 처음에는 현재 제거될 사람의 위치를 구하기위해 유니온파인드를 사용해서 경로를 압축해줄려했다. 예를들어, 1 2 3 4 5에서 2번, 3번이 이미 ..
[백준 / BOJ] 4883 삼각 그래프 (Java) 문제 출처 : https://www.acmicpc.net/problem/4883 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net N(N>=2)개의 행, 3개의 열로이루어진 삼각그래프 가있다. 삼각그래프의 각 노드는, (y,x일때) 자신의 위치기준으로 (0, -1) (-1, -1) (-1, 0) (-1, 1)위치에 있는 노드들에서 올수있다. (해당 위치에 노드가 없는경우 올수없다.) 각 노드에 가중치가 있을때, (1,2)위치부터 (N,2)위치까지 가는 최소경로를 구하는 문제다. 풀이 다이나믹 프..
[디자인 패턴] Iterator 패턴 책을 공부하며 새로운 문제를 만들고 구현한것을 기록한 게시글입니다. (이해한 내용을 바탕으로 작성했기 때문에, 내용이 정확하지않고 틀린부분이 있을수있으며, 예시가 패턴을 사용하기에 알맞지 않을수도있습니다) Iterator 패턴 - 자료구조의 구조를 드러내지않으면서, 해당 구조에있는 모든 항목을 참조할수있도록함. 클라이언트에게 자료구조를 드러내지않으면서, 자료구조에 값을 참조할수있도록 한다. 클라이언트는 자료구조에 대해 몰라도 되기때문에, 이후에 자료구조가 추가되거나, 변경되더라도 클라이언트 코드는 변경될필요가 없다. Iterator패턴을 구현해봤다. 각각 다른 자료구조를 사용하는 클래스가있다. 예를들어, Array를 구현한 RepeatOnArray가 있고, ArrayList를 구현한 RepeatOnArr..
[백준 / BOJ] 1445 일요일 아침의 데이트 (Java) 문제 출처 : https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 형택이는 여자친구와 데이트를 하려고한다. 자신의 여자친구는 쓰레기를 지나가는것과, 쓰레기 주위를 지나가는것을 굉장히 싫어하기 때문에, 형택이는 이러한 상황을 최대한 피하고자한다. 숲의 크기 n,m 쓰레기의 위치(g), 형택이의 위치(S), 도착위치(F)가 주어진다. 이때, 위와 같은 상황을 최소화 하여 움직였을때 쓰레기를 지나간 횟수와 쓰레기 주위를 지나..
[디자인 패턴] 템플릿 메소드 패턴 - compareTo 책을 공부하며 새로운 문제를 만들고 구현한것을 기록한 게시글입니다. (이해한 내용을 바탕으로 작성했기 때문에, 내용이 정확하지않고 틀린부분이 있을수있으며, 예시가 패턴을 사용하기에 알맞지 않을수도있습니다) 템플릿 메소드 패턴 알고리즘의 구조를 정의한다. 이때 일부 단계는 서브클래스에서 구현할수도있다. 템플릿 메소드패턴은, 알고리즘의 구조는 유지하면서 특정단계만 서브클래스에서 구현하도록 할수있다. 스트래티지 패턴과 알고리즘군을 캡슐화한다는점이 유사하지만, 스트래티지 패턴은 구성을, 템플릿 메소드 패턴은 상속을 이용한다. 문제 Java의 Collections API에는 sort메소드가 있다. Collections에 포함되어있는 ArrayList또한 sort를 사용할수있다. (Collections의 sort ..
[백준 / BOJ] 2644 촌수계산 (Java) 문제 출처 : https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 입력받은 두 사람의 촌수를 계산하는 문제다. 풀이 매우 기초적인 그래프 문제다. 연결거리가 1 늘어날수록 촌수또한 1 늘어난다. 깊이우선탐색으로 입력받은 사람의 촌수를 계산해주면된다. (이때, 자손은 항상 한명의 부모만 가질수있으므로, 이 그래프는 항상 트리구조이다.) 소스코드 https://github.com/devxb/JJUNalgo/blob/master/2644%..

티스토리툴바