문제 피카츄는 "pi", "ka", "chu"를 발음할 수 있다. 따라서, 피카츄는 이 세 음절을 합친 단어만 발음할 수 있다. 예를 들면, "pikapi"와 "pikachu"가 있다. 문자열 S가 주어졌을 때, 피카츄가 발음할 수 있는 문자열인지 아닌지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열 S가 주어진다. 문자열은 알파벳 소문자로 이루어진 문자열이며, 길이는 5000을 넘지 않는다. 출력 문자열 S가 "pi", "ka", "chu"를 이어 붙여서 만들 수 있으면 "YES"를 아니면 "NO"를 출력한다. 이 문제 자바로 풀면 난이도가 상승하는 이상한 문제... ㅡㅡ; 분명 같은 코드인데 자바는 런타임이고, c++은 답이고...ㅡㅡ;; 이래서 c++로 알고리즘 공부를 해야한다. packag..
문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력..
문제 그래프를 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이라 읽는다. 뭐 어차피 자세하게 파면 틀린 이야기겠지만... 아무튼 내가 하고 싶은 이야기는 컴퓨터..