분류 전체보기

Chapter 3. 역할, 책임, 협력

조영호님의 오브젝트를 읽고 제 머릿속에 있는 내용들을 정리하며 작성한 글입니다. 객체 지향에서 가장 중요한 것은 💡 역할, 책임, 협력이다. 클래스, 상속, 지연 바인딩과 같은 개념은 구현에 초점이 맞추어져 있기 때문에, 애플리케이션의 기능을 구현하기 위해 어떤 협력이 필요하고 협력을 위해 어떤 역할과 책임이 필요한지 고민을 하는 것이 더 중요하다. 1️⃣ 협력 객체들이 애플리케이션의 기능을 구현하기 위해 수행하는 상호작용을 말한다. 두 객체의 협력은, 하나의 객체가 다른 객체에게 도움을 요청할 때 시작된다. 객체는 다른 객체의 상세한 내부 구현에 직접 접근할 수 없으므로, 💡 메시지 전송을 통해 협력한다. 만약 다른 객체의 내부 구현에 접근하여 동작한다면, 객체의 자율성을 훼손하는 행위이다. 따라서, ..

[JAVA] 백준 2637번 【G2.장난감 조립】

문제 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 풀이 1️⃣ 위상정렬을 이용한 풀이 💡 떠오른 Idea 일단 부품의 조립 순서가 있으므로 위상 정렬을 사용해야한다는 것은 파악했다. 근데, 원하는 출력은 최종 장난감을 구성하는 기본 부품의 수를 출력해야했다. 기본 부품은 조합되어 만들어진 부품이 아닌 경우 기본 부품이라고 한다. 따라서, 특정 부품을 조립할때마다 해당 조립 부품을 구성하는 기본 부품의 정보를 저장하고 계속 넘겨주어야겠다고 생각했다. 일단, indegree 값이 0..

[JAVA] 백준 21276번 【G2.계보 복원가 호석】

문제 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 풀이 1️⃣ 위상 정렬과 우선순위 큐를 활용한 풀이 💡 떠오른 Idea 이 문제에서 가장 중요한 포인트는 직계 자손임을 어떻게 파악하는가였다. haeun doha doha minji haeun minji 위와 같이 관계가 주어졌을 때 하은은 도하와 민지의 자손이고 도하는 민지의 자손임을 알 수 있는데 들어오는 간선의 수를 보면 민지 : 0 도하 : 1 하은 : 2 임을 알 수 있다. 위상 정렬에 따라 정렬하면 민지에서 시작해서 민지와 연결된 간선..

[JAVA] 백준 1967번 【G4.트리의 지름】

문제 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 1️⃣ dfs를 이용한 풀이 💡 떠오른 Idea 처음에는 문제에서 친절하게 부모 노드를 명시해서 알려줘서 다른 방향으로 많이 생각했던 것 같다. 근데, 이 문제는 부모 노드를 특정해서 문제를 풀기보다는 모든 노드가 루트 노드가 될 수 있음을 가정해서 푸는 것이 편리하다. 예시에서 나온 그림은 위와 같은데 사실 위 그림은 9 를 최상단 노드라고 생각하고 그리면 위와 같이 그려질 수 있다. 그리고 9 → 5 → 3 → 6 → 12 노드..

[JAVA] 백준 2250번 【G2.트리의 높이와 너비】

문제 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 풀이 1️⃣ 중위순회를 이용한 풀이 💡 떠오른 Idea 중위 순회는 위와 같이 트리의 노드를 순회하는 방식이다. 중위 순회를 사용하면 트리에 존재하는 각 노드의 열 값을 알 수 있다. 각 노드의 깊이를 체크해나가면서 중위 순회를 하고, 각 깊이에 해당하는 열 값의 최솟값과 최댓값을 기록해두면 된다. public class Main { static Node[] tree; static Map info = new HashMap(); static..

Chapter 2. 객체지향 프로그래밍

조영호님의 오브젝트를 읽고 제 머릿속에 있는 내용들을 정리하며 작성한 글입니다. 객체 지향 프로그래밍을 할 때, 유념해야할 부분은 다음과 같다. 어떤 클래스가 필요한지 고민하기 전에 어떤 객체들이 필요한지 고민해야한다. 코드로서 바라보기 전에 기능이 동작되는 메커니즘을 잘 생각하라는 의미인 것 같다. 객체를 고립된 존재로 바라보지 말고 협력에 참여하는 협력자로 바라보아야 한다. 무작정 결합도를 줄이려고 노력하기 보다 효율적으로 협력하기 위한 방법을 고민하는 것이 필요하다. 클래스의 경계를 잘 구분 지어야 한다. Chapter 1에서도 많이 설명했듯이, 객체는 자신의 필드를 자신이 관리하도록 해야하며 그러기 위해서는 캡슐화를 통해 외부에 공개하지 않는 것이 좋다. 외부에서 접근이 가능한 메서드를 통해 간접..

[JAVA] 백준 20955번 【G4.민서의 응급 수술】

문제 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 풀이 1️⃣ 트리의 특징과 bfs 를 이용한 풀이 💡 떠오른 Idea 이 문제는, 무작위로 주어지는 노드간의 관계를 트리관계로 풀어가야 하는 문제이다. 먼저, 생각할 수 있는 경우는 다음과 같다. 1. 정상적인 트리 형태를 이루고 있는 집합인 경우 2. 특정 노드 집합이 사이클을 이루고 있는 경우 3. 1번 혹은 2번 같은 집합이 연결되어있지 않고 떨어져 있는경우 그래서 모든 뉴런을 하나의 트리 형태로 연결하기 위한 횟수를 어떻게 구해야할까 고민했는데 먼저..

Chapter 1. 객체, 설계

조영호님의 오브젝트를 읽고 제 머릿속에 있는 내용들을 정리하며 작성한 글입니다. 변경에 취약한 코드 public class Theater { private TicketSeller ticketSeller; public Theater(TicketSeller ticketSeller) { this.ticketSeller = ticketSeller; } public void enter(Audience audience) { // 관람객 가방에 초대권이 있다면? if (audience.getBag().hasInvitation()) { Ticket ticket = ticketSeller.getTicketOffice().getTicket(); // 티켓 제공 audience.getBag().setTicket(ticket..

[JAVA] 백준 22856번 【G4.트리 순회】

문제 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 풀이 1️⃣ 트리 클래스를 정의한 풀이 💡 떠오른 Idea 처음에는 이 문제에서 정의한 유사 중위 순회를 똑같이 구현해야하나 고민했었지만, 그러지 않고 쉽게 해결할 수 있었다. 이 유사 중위 순회의 특징은 트리에서 제일 오른쪽 간선은 한번만 지나가게 된다는 특징이 있다. 따라서, 가장 오른쪽 자식만 지나가게끔 하는 순회를 정의하여 노드의 개수를 구했고 간선의 개수는 노드의 개수 -1 임을 이용하여 편도 간선의 개수를 구할 수 있었다. 그리고 (전체 노드의 ..

[JAVA] 백준 5214번 【G2.환승】

문제 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 풀이 1️⃣ bfs와 인접리스트를 이용한 풀이 💡 참고한 Idea 역의 수 N이 최대 100000 이고 하이퍼 튜브와 하이퍼 튜브가 연결하는 역의 개수 K 와 M이 최대 1000 이라서 일반적인 그래프를 푸는 방식으로 노드를 연결하면 시간 복잡도가 말도안되게 커져서 고민을 많이 했다. 계속 메모리 초과를 어떻게 해결해야할지 고민하다가 다른 사람의 아이디어를 참고하였다. 하이퍼 튜브를 일종의 역으로서 생각을 하고 노드로서 추가하는 ..

[JAVA] 백준 1043번 【G4.거짓말】

문제 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 1️⃣ 플로이드 알고리즘을 이용한 풀이 💡 떠오른 Idea 이 문제는 파티별로 바로 체크를 할 수 없는 문제이고, 모든 파티의 정보를 처리한 다음에 개수를 구할 수 있다. 그 이유는 예제 처럼 4 5 1 1 1 1 1 2 1 3 1 4 2 4 1 위와 같이 주어졌을 때, 4번째 파티인 1 4 에서는 4번이 진실을 모를것 같지만 5번째 파티에서 진실을 아는 1번이 4번에게 알려 줄 수 있기 때문이다. 따라서, 순차적으로 판단할 수 없다. 내가 생각한 전략은 지민이..

[JAVA] 백준 2617번 【G4.구슬 찾기】

문제 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 풀이 1️⃣ bfs와 Marble 클래스 정의를 통한 풀이 💡 떠오른 Idea 문제를 해결하기 위한 방법은 문제에 거의 주어지다 싶이 나와있었다. 구슬이 총 5개일때는 특정 구슬보다 가벼운게 3개 이상인 경우 중간이 될 수 없고 무거운게 3개 이상인 경우는 중간이 될 수 없다. 처음에는 N이 짝수로도 주어지나 싶어서, 짝수인 경우에는 약간 기준이 달랐지만 홀수로만 주어진다고 했으므로 특정 구슬이, 상대적으로 가벼운 구슬이 (N+1)/2 개..

[JAVA] 백준 1707번 【G4.이분 그래프】

문제 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 1️⃣ 이분 그래프의 정의와 bfs 를 이용한 풀이 예전에 풀어봤던 문제여서, 원리를 쉽게 파악할 수 있었다. 이전에도, 한참을 고민했었다가 서칭해서 풀었었는데, 이분 그래프라는 단어가 나오면 이 정의를 생각해야한다. 이분 그래프인지 아닌지 확인할 수 있는 특징 중 하나인, 노드 그래프를 2개의 색깔로 칠했을 때, 인접하는 노드끼리 색이 겹치지 않게 색칠할 수 있을 때, 이분 그래프가 될 수 있다고 한다. 위와 같은 그림처럼 말이다. 아직 방문하지 않..

[JAVA] 백준 2660번 【G5.회장뽑기】

문제 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 1️⃣ 플로이드 알고리즘 사용 💡 떠오른 Idea 처음에 문제가 '어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.' 라고 나와있어서 이해하기가 힘들었었다. 근데, 이 문제를 직관적으로 이해해보니 '특정 회원이 있을 때 가장 사이가 ..

[Java] 909. Snakes and Ladders

문제 파악 Boustrophedon 스타일의 n*n 보드가 주어진다. ( (n-1,0) 좌표에서 시작한다. ) 주사위에 따라 최대 6칸을 이동할 수 있다. 만약 뱀이나 사다리를 만나면 뱀이나 사다리를 이용해야한다. n^2 칸에 도달했을 때, 게임은 끝난다. 보드 값이 -1이 아닌 경우 뱀이나 사다리가 존재한다. 뱀이나 사다리인 경우 도착하는 보드 값이 기록되어있다. 뱀이나 사다리는 1 또는 n^2 칸에 존재하지 않고 연속으로 이동할 수 없다. n^2에 도달하기 위한 최소 이동 횟수를 반환하고, 도달하지 못하면 -1을 반환한다. 풀이 1️⃣ 1차원 맵과 bfs 를 이용한 방법 💡 떠오른 Idea 먼저, 보드판 순서가 헷갈려서 이를 1차원 맵으로 바꿔서 해결하면 간단할것이라 생각이 들었다. 따라서, 제일 아..