문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. ..
데이코레이터는 장식입니다. 지금 보고 있는 사진은 거북이 장식입니다. 예쁘죠? 물론 프로그래밍 상에서의 데코레이터는 살짝 다른 느낌이 들긴 하지만요. 아무튼 이름 만 봐서는 데코레이터는 무언가를 꾸미는 패턴이라고 생각하게 될것 같습니다. 막상 코드를 보면 이게 왜? 데코레이터지?라는 생각이 들지도 모릅니다. 보통 장식이라는게 정해진 위치에 놓잖아요. 커튼에 달린 장식품을 냉장고에 올려놓으면 이상한거처럼 이 패턴도 막 사용하면 안됩니다. 물론, 커튼 장식품을 냉장고에 가져다 놔도 아무상관은 없습니다. 아무리 멋있는 장식품이어도 아무데나 놓으면 그저 잡동사니에 불과하니까요. 이 처럼 데코레이터 패턴은 아무렇게나 사용이 가능은 하지만, 쓸데 없이 아무렇게나 사용하면 아무 쓸데 없는 패턴일 겁니다. 데코레이터 ..
오늘은 다른 방식으로 이 패턴을 이해하려고합니다. 이 패턴은 생각보다 구현이 단순하기 때문에 이해하는데 오히려 걸림돌이 되는 그런 패턴인것 같습니다. 그럼에도 그냥 한번 해보겠습니다. 오늘은 제가 직접 예제를 만들지 않고 유튜버 이야기'sG님의 코드를 분석하는 시간을 가져볼까합니다. 컴포짓트? 이건 과연 뭘까요? 컴포짓트는 한글로 혼합물이라는 뜻이라고 합니다. 혼합물의 가장 큰 특징은 2개 이상의 액체를 섞었다는 것이 그 특징입니다. 액체를 섞게되면 뭐가 섞였는지 잘 모릅니다. 하지만 저희는 액체를 섞고 싶은게 아닙니다. 저희가 섞고 싶은 건 객체입니다. 하지만 객체는 액체와 달리 섞는 방법이 정해져 있지 않습니다. 그래서 디자인 패턴에서 사용한 방법이 바로 트리로 만드는 것입니다. 물론, 자료구조의 트..
문제 문자열을 입력으로 주면 문자열의 첫 글자와 마지막 글자를 출력하는 프로그램을 작성하시오. 입력 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 한 줄에 하나의 문자열이 주어진다. 문자열은 알파벳 A~Z 대문자로 이루어지며 알파벳 사이에 공백은 없으며 문자열의 길이는 1000보다 작다. 출력 각 테스트 케이스에 대해서 주어진 문자열의 첫 글자와 마지막 글자를 연속하여 출력한다. 이 문제는 굉장히 간단하다. 앞글자랑 뒷글자랑 출력하면 된다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; while(n-..
문제 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001 등이다. 10진법의 수를 입력 받아서 -2진수를 출력하는 프로그램을 작성하시오. 입력 첫 줄에 10진법으로 표현된 수 N(-2,000,000,000≤N≤2,000,000,000)이 주어진다. 출력 -2진법 수를 출력한다. 이걸 내가 왜 못풀었지.ㅜㅜ 이걸 왜.... 그냥 2진수로 계산하고 홀수일때만 신경써서 계산하면 된다. #include using namespace std; in..
Observer 관측자라는 뜻으로 옵저버 패턴, 종속자 패턴, 게시-구독 패턴이라고 한다. 사실 이 패턴을 처음 접했을때는 단순히 난해하다고만 생각했다. 왜냐하면 옵저버 패턴의 가장 큰 특징중 하나가 객체의 느슨한 결합인데... 이것에 의미를 정확하게 인지하지 못하고 있었다. 정확하지는 않지만... 아마 직접 구현이아닌 인터페이스로 만들어서 결합도를 낮추는 방법인듯 싶다. 아무래도 인터페이스로 인스턴스를 만들게 되면 선택지가 많아지기 때문에 아마 맞는것 같다. 해드 퍼스트 디자인 패턴 책에서는 이 패턴을 설명할때, 신문과 구독이라는 주제로 설명했다. 신문사는 여러 종류가 있다. A 신문사, B신문사, C신문사... 등등 하지만 여기에서는 A신문사만 존재한다고 가정하자. 보통 신문사에는 구독자가 있다. 즉..
[코딩 인터뷰 완전 분석] ▶ 해시 테이블 - 효율적인 탐색을 위한 자료구조로 키를 값에 대응 시킨다. 해시 테이블을 구현하기 위해서는 연결리스트와 해시코드 함수만 있으면 된다. - 키와 값을 해시테이블에 넣을때 다음의 과정을 거친다. 1. 키의 해시코드를 계산한다. ※키의 개수는 무한대인데, int나 long의 개수는 유한하기때문에 서로 다른 두 개의 키가 같은 해시코드를 가리킬 수 있다는 사실을 명심해야한다. 2. hash(key) % array_length와 같은 방식으로 해시코드를 이용해 배열의 인덱스를 구한다. -> 같은 인덱스를 가르킬수 있다. 3. 배열의 각 인덱스는 키와 같은 같은 값으로 이뤄진 연결리스트가 존재한다. - 키와 값을 해당 인덱스에 저장한다. - 충돌에 대비하여 연결리스틀 이..
연결리스트 : - 차례대로 연결된 노드를 표현해 주는 자료구조 - 단방향 연결리스트에서 각 노드는 다음 노드를 가르킨다. - 양방향 연결 리스트에서 각 노드는 다음노드와 이전 노드를 가르킨다. - 배열과 달리 연결리스트는 특정 인덱스를 상수시간에 접근 할 수 없다. => k번째 원소를 찾고 싶다면, k번 루프를 돌아야 한다. 1 2 3 4 연결리스트의 장점 : 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수시간에 할 수 있다. 단 방향 연결리스트 코딩 public class Node { Node next = null; int data; public Node(int d) { this.data = d; } } 코드 : Node를 만드는 로직이 들어가있다. 이때 주의 할 점은 자기 자신을 호출..
문제 8진수가 주어졌을 때, 2진수로 변환하는 프로그램을 작성하시오. 입력 첫째 줄에 8진수가 주어진다. 주어지는 수의 길이는 333,334을 넘지 않는다. 출력 첫째 줄에 주어진 수를 2진수로 변환하여 출력한다. 수가 0인 경우를 제외하고는 반드시 1로 시작해야 한다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); string o; cin >> o; if (o == "0") { cout 0) { index++; } if (index > 0 && temp == 0) { sleep+="000"; } while ( temp > 0) { sleep += to_string(temp%2);..
문제 2진수가 주어졌을 때, 8진수로 변환하는 프로그램을 작성하시오. 입력 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 주어진 수를 8진수로 변환하여 출력한다. 이 문제는 생각보다 까다뤘다. 신경써야 하는게 한 두개가 아니였다. 보통 이진수에서 8진수로 바꿀 때 3개씩 끝어서 계산한다. 이것도 똫같이 하면 되는데... 문제는 컴퓨터와 사람이 문자열을 읽는 방식에 차이가 있다. 물론 일반 문자열은 크게 틀리지 않는데 문제는 숫자를 읽을때다 01이라는 숫자를 읽을때 컴퓨터는 0부터 인식한다... 그래서 이것을 01이라 읽고 사람은 1부터 읽기 때문에 1이라 읽는다. 뭐 어차피 자세하게 파면 틀린 이야기겠지만... 아무튼 내가 하고 싶은 이야기는 컴퓨터..
퍼사드? 그게 뭔데 패턴으로 붙여 놨을까? 이것 부터 알아야할듯 싶다. 완벽하게 일치는 안해도 퍼사드 하면 떠오르는 이미지가 있는게 좋지 않을까? 퍼사드는 건물의 정면을 말한다고 한다. 어떻게 보면 이름을 잘지은 패턴이라고 할 수도 있겠다. 퍼사드 패턴은 객체지향의 최소 지식 원칙을 준수한다고 한다. 최소 지식 원칙이라는게 무엇일까? 여기서 말하는 지식은 도대체 뭘까? 내가 생각할 때, 사람의 지식은 아닌것 같다는 느낌이 든다. 이게 무슨 말이냐면... 보통 지식은 많은 것을 아는 것을 뜻한다. 하지만 객체지향의 지식은 조금 다르게 해석 되는것 같다. 바로 클래스의 연결로 결정된다. 이게 무슨 말이냐면 A,B클래스가 있다고 가정하자. 또, A클래스는 B클래스와 연결이 되어있다. 이 정도가 최소 지식 원칙..
브릿지 패턴..... 이것도 어뎁터와 마찬가지로 떠오르는 이미지가 있을거다. 바로 이런 다리 이미지를 떠올릴 것이다. 물론 동물의 다리를 떠올리는 분도 있겠지만 말이다. 근데.. 나는 잘 모르겠다. 왜 이름이 브릿지인지에 대해 전혀 감이 잡히지 않고 있다. 어째든 브릿지 패턴의 가장 큰 특징은 구현과 기능을 분리한다는 점에 있다. 이걸 따로 공부했을때는 아 그렇구나 라고 느꼈는데, 구현과 기능을 합쳐서 내가 아는 구현이 맞는 구현인가라는 착각이 들기도 한다. 결론부터 말하면 내가 생각한 구현이 맞다. 다만, 기능을 분리한다는데 구현에는 뭐가 들어있는 걸까? 구현을 하면 당연히 구현안에도 기능이 있을 텐데.... 왜 이걸 구현과 기능의 분리라 한것일까? 사실 분리하는 기능은 기본 기능은 제외된거였다. 예를..