1. 8-Puzzle 게임

• 문제: 초기 상태에서 타일을 섞어 최종 상태로 복구하는 퍼즐.
• 해결 방법:
  • 초기 상태 생성: 숫자를 무작위로 배치하면 불가능한 상태가 나올 수 있으므로, 해결 가능한 상태를 보장하는 알고리즘 필요. 예를 들어, 일정한 규칙으로 타일을 섞는 방법(짝수/홀수 순열 검사)을 사용할 수 있음.
  • 탐색 알고리 즘: A* 알고리즘 또는 BFS/DFS 등을 사용해 최적 경로를 찾음.
  • 게임 확장: 3x3 외에도 4x4(15-puzzle), 5x5 등 다양한 크기의 퍼즐을 추가 가능. 난이도를 높이거나, 최단 경로 찾기 기능 추가.
  • 비주얼화: 퍼즐의 이동 과정을 그래픽으로 보여주기 위해 GUI를 이용한 윈도우 기반 프로그램 구현.

2. 텍스트 파일에 나타난 단어의 인덱스 만들기

• 문제: 텍스트 파일에서 단어를 추출하고 각 단어가 등장한 라인을 인덱스로 만드는 작업.
• 해결 방법:
  • 단어 추출: 파일을 읽어 공백, 구두점 등으로 단어를 구분하고 불필요한 단어(전치사 등)를 필터링.
  • 자료 구조: 해시 테이블 또는 이진 탐색 트리(BST)를 사용해 단어를 저장하고, 각 단어의 등장 라인을 연결 리스트로 관리.
  • 검색 및 저장: 단어가 이미 등장했으면 해당 단어의 리스트에 라인 번호 추가, 처음 등장한 단어는 새로운 항목으로 추가.
  • 출력: 단어를 알파벳 순서로 정렬한 후 각 단어와 그 단어가 등장한 라인 번호를 출력.

3. 8-Queen Problem

• 문제: 8x8 체스판에 8개의 퀸을 서로 공격할 수 없는 위치에 배치하는 문제.
• 해결 방법:
  • 백트래킹: 각 행에 퀸을 하나씩 배치하며, 다음 행에서 퀸이 공격받지 않도록 가능한 위치를 찾음. 퀸을 배치할 수 없는 경우, 이전 행으로 돌아가 다른 위치를 탐색(백트래킹).
  • 스택 사용: 퀸이 놓인 좌표를 스택에 저장하고, 백트래킹 시 스택에서 위치를 삭제하여 이전 상태로 되돌림.
  • 입출력: 체스판 크기(4~8)를 입력받아, 각 해답을 출력(예: Row 1 - Col 2 Q).

4. 간단한 메모리 관리자

• 문제: 동적 메모리 할당 및 해제를 구현하는 간단한 메모리 관리자.
• 해결 방법:
  • 메모리 할당(myalloc): 남은 메모리 리스트에서 요청 크기만큼의 메모리를 할당하고, 시작 주소를 반환.
  • 메모리 해제(myfree): 해제된 메모리를 기존 가용 메모리와 연속되면 합쳐서 더 큰 블록을 만듦.
  • 할당 전략: First-fit(가장 앞의 덩어리 사용) 및 Best-fit(가장 적합한 크기 사용) 전략을 구현하고 성능 비교.
  • 자료 구조: 연결 리스트를 사용해 가용 메모리 블록을 관리.

5. 방향 그래프에서 사이클 찾기

• 문제: 방향 그래프에서 사이클이 있는지 확인.
• 해결 방법:
  • DFS(깊이 우선 탐색): 각 노드를 방문하면서 사이클이 발생하는지 확인. 방문 중인 노드를 기록하고, 다시 방문할 경우 사이클이 존재함을 확인.
  • 그래프 순환 검출: DFS 중에서 부모 노드로 돌아가는 경로가 발견되면 사이클을 검출.
  • 확장 문제: 주어진 그래프에서 몇 개의 사이클이 존재하는지, 각 사이클의 경로는 무엇인지도 확인하는 방식으로 확장 가능.