문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. 출력 각 테스트 케이스에 대해서, 섬의 개수를 출력한다..
문제 피카츄는 "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부터 방문된 점을 순서대로 출력하면 된다. ..
문제 문자열을 입력으로 주면 문자열의 첫 글자와 마지막 글자를 출력하는 프로그램을 작성하시오. 입력 입력의 첫 줄에는 테스트 케이스의 개수 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..
[코딩 인터뷰 완전 분석] ▶ 해시 테이블 - 효율적인 탐색을 위한 자료구조로 키를 값에 대응 시킨다. 해시 테이블을 구현하기 위해서는 연결리스트와 해시코드 함수만 있으면 된다. - 키와 값을 해시테이블에 넣을때 다음의 과정을 거친다. 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가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다. 이 문제가 LCD라 였나.. 그런건데.. 나는 잘 모르겠다. 아무튼 이런류의 문제의 핵심은 dp를 조작하지 않는것이 핵심이다. 이 말이 어떤 뜻인지는 계속 읽어보면 알 수도 있을것 같다. 10 30 ..
문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 ..