2024 자료구조개론 & 알고리즘개론 정리 - 심화 문제

 

 

2024 자료구조개론 & 알고리즘개론 정리 - 심화 문제 

 

 

 

 

 

 

1. 배열 심화 문제 - 9문제

 

 

 

Q1. 문자열이 주어졌을 때 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 구현하세요. 추가적인 데이터 구조를 사용할 수 없다면 어떻게 할까요?

 

•  

 

 

 

 

 

Q2. 두 개의 문자열이 주어졌을 때, 하나가 다른 하나의 순열인지 결정하는 메소드를 작성하세요.

 

 

 

 

 

Q3. 문자열 내의 모든 공백을 '%20'으로 바꾸는 메소드를 작성하세요. 문자열 끝에는 추가 문자를 저장할 충분한 공간이 있다고 가정하고, 문자열의 "실제" 길이가 주어진다고 가정합니다. (참고: Java에서 구현한다면, 이 작업을 제자리에서 수행할 수 있도록 문자 배열을 사용해 주세요.) 예시 입력: "Mr John Smith ", 13 출력: "Mr%20John%20Smith”

 

 

 

 

 

 

Q4. 문자열이 주어졌을 때, 그것이 팰린드롬의 순열인지 확인하는 함수를 작성하세요. 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 단어나 구입니다. 순열은 문자의 재배열입니다. 팰린드롬은 꼭 사전에 있는 단어에만 국한되지 않습니다. 예시 입력: Tact Coa 출력: True (순열 예: "taco cat", "atco eta" 등)

 

 

 

 

 

Q5. 문자열에 수행할 수 있는 세 가지 유형의 편집이 있습니다: 문자 삽입, 문자 제거, 또는 문자 교체. 두 개의 문자열이 주어졌을 때, 그들이 한 번의 편집(또는 편집 없음)만으로 서로 변환될 수 있는지 확인하는 함수를 작성하세요. 예시 pale, ple -> true pales, pale -> true pale, bale -> true pale, bake -> false

 

 

 

Q6. 문자의 반복 횟수를 사용한 기본 문자열 압축을 수행하는 메소드를 구현하세요. 예를 들어, 문자열 aabcccccaaa는 a2b1c5a3가 됩니다. 만약 "압축된" 문자열이 원본 문자열보다 작아지지 않는다면, 메소드는 원본 문자열을 반환해야 합니다. 문자열은 대문자와 소문자만 가지고 있다고 가정할 수 있습니다 (a - z).

 

 

 

 

 

Q7. NxN 행렬로 표현된 이미지가 있고, 이미지의 각 픽셀은 4바이트입니다. 이미지를 90도 회전시키는 메소드를 작성하세요. 이 작업을 제자리에서 할 수 있나요?

 

 

 

 

Q8. MxN 행렬에서 요소 중 하나라도 0이라면, 해당 요소의 전체 행과 열을 0으로 설정하는 알고리즘을 작성하세요.

 

 

 

 

 

 

Q9. 다른 단어의 부분 문자열인지 확인하는 isSubstring 메소드가 있다고 가정합니다. 두 개의 문자열, s1과 s2가 주어졌을 때, isSubstring을 단 한 번만 호출하여 s2가 s1의 회전인지 확인하는 코드를 작성하세요 (예: "waterbottle"은 "erbottlewat"의 회전입니다).

 

 

 

 

 

 

 

2. Linked List 심화 문제 

 

 

 

Q1. 정렬되지 않은 연결 리스트에서 중복을 제거하는 코드를 작성하세요. 추가 질문 임시 버퍼를 사용할 수 없다면 이 문제를 어떻게 해결하시겠어요?

 

 

Q2. 연결 리스트가 팰린드롬인지 확인하는 함수를 구현하세요.

 

 

 

Q3. 단일 연결 리스트의 중간에 있는 노드(즉, 첫 번째와 마지막 노드를 제외한 어떤 노드라도, 반드시 정확한 중간일 필요는 없습니다)를 삭제하는 알고리즘을 구현하세요. 단, 그 노드에만 접근할 수 있습니다. 예시 입력: 연결 리스트 a->b->c->d->e->f에서 노드 c 결과: 반환값은 없지만, 새로운 연결 리스트는 a->b->d->e->f 처럼 보입니다

 

 

Q4. x 값을 기준으로 연결 리스트를 분할하는 코드를 작성하세요. 이때, x보다 작은 모든 노드가 x보다 크거나 같은 모든 노드들보다 앞에 오도록 합니다. 리스트 내에 x가 포함되어 있다면, x의 값은 x보다 작은 요소들 뒤에만 오면 됩니다(아래 참고). 분할 요소 x는 "오른쪽 분할" 어디에나 나타날 수 있으며, 왼쪽과 오른쪽 분할 사이에 나타날 필요는 없습니다. 예시 입력: 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1 [partition= 5] 출력: 3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8

 

 

 

Q5. 각 노드가 단일 숫자를 담고 있는 연결 리스트로 표현된 두 숫자가 있습니다. 숫자들은 역순으로 저장되어 있어, 1의 자리 숫자가 리스트의 머리에 위치합니다. 두 숫자를 더하고 그 합을 연결 리스트로 반환하는 함수를 작성하세요. 예시 입력: (7-> 1 -> 6) + (5 -> 9 -> 2). 즉, 617 + 295. 출력: 2 -> 1 -> 9. 즉, 912. 추가 문제 숫자들이 순서대로 저장되어 있다고 가정하세요. 위 문제를 반복하세요. 예시 입력: (6 -> 1 -> 7) + (2 -> 9 -> 5). 즉, 617 + 295. 출력: 9 -> 1 -> 2. 즉, 912.

 

 

Q6. 두 개의 (단일) 연결 리스트가 주어졌을 때, 두 리스트가 교차하는지 확인하세요. 교차하는 노드를 반환하세요. 교차의 정의는 값이 아닌 참조에 기반한다는 점에 유의하세요. 즉, 첫 번째 연결 리스트의 k번째 노드가 두 번째 연결 리스트의 j번째 노드와 정확히 동일한 노드(참조에 의해)라면, 그들은 교차하고 있다고 합니다.

 

 

 

Q7. 주어진 순환 연결 리스트에서, 루프의 시작 부분에 있는 노드를 반환하는 알고리즘을 구현하세요. 정의 순환 연결 리스트: 노드의 다음 포인터가 이전 노드를 가리켜 연결 리스트 안에서 루프를 형성하는 (손상된) 연결 리스트입니다. 예시 입력: A -> B -> C -> D -> E -> C [이전과 동일한 C]