Certi 프로젝트 개발 과정에서 추천 채용공고 화면을 만들기 위해 원티드의 open API를 사용해야 할 일이 생겼다. 우선 테스트를 위해 API Docs를 참고하여 원티드 측 개발 서버로 요청을 보냈더니 CORS 에러가 발생했다.

CORS Error?

CORS(Cross-Origin Resource Sharing) 에러는 서버의 자원에 접근하려고 할 때, 요청하는 도메인이 허용되지 않은 경우 발생한다. GPT에게 Next js 환경에서 해당 에러에 대한 해결책을 문의해본 결과, 크게 3가지 정도의 방법이 존재했다.

1. 프록시 서버 사용: 프론트엔드와 백엔드 사이에 프록시 서버를 두어 클라이언트가 프록시 서버에 요청을 보내고, 프록시 서버가 다시 백엔드에 요청을 보내는 방식이다.

2. 서버에서 CORS 허용: 이 방법은 클라이언트 차원에서 해결할 수 없지만, 서버 관리자에게 요청하여 Access-Control-Allow-Origin 헤더를 설정하는 방법이다.

3. Next.js API Routes 사용: Next.js에서 제공하는 API Routes를 사용하여 프록시 서버처럼 작동하게 할 수 있다.

만약 우리 서비스측 서버를 사용하는 상황이라면 2번 방식처럼 서버(백엔드) 개발자에게 요청하여 서버 차원에서 해결할 수 있는, 클라이언트 입장에선 그리 까다로운 에러는 아닐(?) 수도 있다.

하지만 이번 상황의 경우 우리측 서버가 아닌 원티드의 Open API를 사용하는 상황이기에 클라이언트 차원에서 우회를 통한 해결이 필요했다.

그리고 나는 3번 방식을 통해 이 문제를 해결하기로 결정했다.

Solutions

그럼 이제부터 Next.js API Routes를 사용하여 CORS 에러를 해결한 과정에 대해 서술해 보겠다.

1. API Route 작성 (pages/api/proxy.js)

우선 pages/api 경로에 proxy.js 라는 이름의 API Route 파일을 생성해주고, 아래와 같이 설정해주었다.

import axios from 'axios';

export default async function handler(req, res) {
  try {
    const response = await axios({
      url: '요청을 보낼 API 주소',
      method: req.method,
      headers: {
        'Content-Type': 'application/json',
      },
    });

    res.status(response.status).json(response.data);
  } catch (error) {
    res.status(error.response ? error.response.status : 500).json({
      message: error.message,
    });
  }
}

2. 클라이언트 코드에서 API Route 호출

다음은 클라이언트에서 작성한 API Route를 호출할 차례이다. 나는 아래와 같은 방식으로 호출해보았다.

const getJobPostings = async () => {
    try {
      const response = await axios.get('/api/proxy');
    } catch (error) {
      console.error('Error fetching data:', error);
    }
  };

Outro

전반적인 구조를 정리해보자면 다음과 같다.

1) pages/api/proxy.js: 외부 API에 대한 프록시 요청을 처리하는 API Route. 2) 클라이언트 코드 (예: 컴포넌트 파일): Next.js API Route를 호출하여 데이터를 가져옴.

위와 같은 구조처럼 설정하면 클라이언트는 Certi 도메인에서 원티드 Open API 도메인으로 직접 요청을 보내지 않고, Next.js 서버를 통해 간접적으로 요청을 보내게 되고, 이를 통해 CORS 에러를 피할 수 있다.

(위와 같이 실제로 제대로된 응답을 받을 수 있었다.)

👉 Certi 링크 👈

이번엔 앞서 배포한 IP 주소에 가비아에서 구매한 도메인을 연결해 볼 차례다.

약간의 조사를 거친 결과, 도메인에 배포된 IP 주소를 연결하는 방법에는 크게 두가지가 있다.

1. aws 사용 (Route 53 + 로드 밸런서)
2. Nginx를 사용

나는 이미 aws EC2에 내 프로젝트를 배포해놓은 상태라 1번 방식을 채택하는게 더 간편할 것이라 판단되긴 했지만, 서브도메인 중 하나가 이미 프레이머로 배포된 서비스에 연결되어 있는 이슈로 인해 2번 방식을 채택하기로 했다.

배포된 IP 주소로 도메인 연결

1. EC2 인스턴스에 Nginx 설치

sudo apt update
sudo apt install nginx

2. Nginx 설정

우선 각 앱(서비스)에 대한 서버 블록을 만들어주는데, 이를 위해 /etc/nginx/sites-available/ 디렉토리에 설정 파일을 만든다.

sudo vi 파일명

파일을 생성하고, 생성한 파일에 다음의 내용을 입력해준다.

server {
    listen 80;
    listen [::]:80;

    server_name 도메인;

    location / {
        proxy_pass http://localhost:포트번호;
        proxy_http_version 1.1;
        proxy_set_header Upgrade $http_upgrade;
        proxy_set_header Connection 'upgrade';
        proxy_set_header Host $host;
        proxy_cache_bypass $http_upgrade;
    }
}

이때 도메인과 포트번호에 올바른 값을 기입하도록 유의해야 한다.

3. Nginx 설정 활성화

심볼릭 링크를 만들어 설정을 활성화한다.

쉽게 말해 /etc/nginx/sites-available 과 /etc/nginx/sites-enabled 를 연결시켜주는 작업이다.

sudo ln -s /etc/nginx/sites-available/파일명 /etc/nginx/sites-enabled/

4. Nginx 재시작

Nginx 설정 테스트 및 재시작

sudo nginx -t
sudo systemctl restart nginx

5. DNS 설정(가비아)

도메인을 구매한 가비아의 DNS 관리 페이지에서, 설정하고자 하는 도메인을 EC2 인스턴스의 공인 IP로 설정해준다.

6. SSL 인증서 설치

나는 무료 SSL 인증서를 위해 Let's Encrypt를 사용했다.

sudo apt install certbot python3-certbot-nginx
sudo certbot --nginx -d 도메인

위의 명령어는 인증서를 발급하고 Nginx 설정을 자동으로 수정하여 HTTPS를 활성화한다.

설정 후에는 Nginx 설정 확인 및 재시작한다.

sudo nginx -t
sudo systemctl restart nginx

Outro

여기까지 완료 했으면 이제 연결된 도메인으로 배포한 앱에 안전하게 접속할 수 있다.

🚨 주의사항 🚨

1. EC2 보안 그룹에서 80번(HTTP)과 443번(HTTPS) 포트가 열려있는지 확인할 것

2. Let's Encrypt 인증서는 90일마다 갱신해야 하므로 자동 갱신을 위해 아래의 명령어로 cron job을 설정할 것

   sudo certbot renew --dry-run

   
   

👉 Certi 링크 👈

현재 작업중인 프로젝트 Certi의 배포 과정을 기록해보려고 한다.

aws를 통해 배포를 진행하기로 결정하고 조사를 해본 결과, aws를 사용하여 클라이언트를 배포하는 가장 대중적인 방식에는 크게 두가지가 있었다.

1. S3 + Cloud Front + Route 53 배포 → 정적 사이트 생성 시
2. EC2 배포 → 동적 사이트 생성 시

내가 배포하려는 서비스인 “Certi”의 경우 Next js 로 만들었고, i18n 을 통해 다국어 지원 기능을 사용하고 있기에 정적 사이트 생성이 불가능했다. 따라서 2번 방식으로 배포하기로 결정했다.

이제 대략적인 과정에 대해 설명해 보겠다.

IP 주소로 서비스 배포

1. aws 인스턴스 생성

1) aws -> EC2로 접속하여 '인스턴스 시작' 버튼을 클릭해서 인스턴스를 생성한다. 나는 ubuntu로 설정하였다. 이때 인스턴스에 연결할 때 필요한 key도 같이 생성해준다.

2) 탄력적 IP 주소 생성 후, 새로 생성한 인스턴스에 할당한다.

3) 하단의 ‘보안’ 탭 클릭 -> '보안그룹' 링크 클릭 -> ‘인바운드 규칙 편집’ 을 클릭해서 보안그룹 설정을 해준다. (HTTP, HTTPS, SSH, 사용자 지정 TCP 등)

2. 로컬에서 터미널로 인스턴스에 접속

ssh -i "생성된 key" ubuntu@퍼블릭 DNS

3. 인스턴스에 필요한 프로그램들 설치

현재 접속한 인스턴스는 아무것도 설치되어 있지 않은 컴퓨터(ubuntu)라 생각하면 된다. 따라서 node js, npm, yarn 등 필요한 프로그램들을 수동으로 설치해줘야 한다.

아래의 명령어들을 참고하여 필요한 프로그램들을 설치해주면 된다.

sudo apt update

// node 설치
sudo apt install nodejs

// npm 설치
sudo apt install npm

// node 버전 관리 다운로드(n)
sudo npm install -g n

// 노드 최신 버전 설치 > 설치 후 쉘 재실행 > node -v 로 버전 확인
sudo n lts

// 원하는 버전으로 설치
sudo n install [원하는 버전]

// 원하는 버전 선택
sudo n [원하는 버전]

4. git clone

이제 인스턴스로 배포할 프로그램을 git clone 하면 된다. clone 후 종속성 설치까지 잊지 말자! (npm install or yarn install)

5. 환경변수 파일(.env) 추가

일반적으로 보안상의 이유로 .env 파일은 gitignore 로 설정하여 git에 올리지 않는다. 따라서 git clone을 해도 인스턴스에 .env 파일은 생성되지 않는다. 따라서 직접 생성 후 저장을 해줘야 한다.

1) sudo vi .env 로 환경변수 파일 생성

2) 로컬의 환경 변수 내용 옮겨쓰기

3) esc + :wq 로 작성한 내용 저장

6. 빌드 후 배포

1) 우분투에서 clone 한 프로젝트 내부로 들어간다.

2) 빌드 실행 (npm run build or yarn build)

3) pm2 실행 (pm2 start “npm start” or pm2 start “yarn start”)

4) pm2 list로 pm2가 제대로 생성되었는지 확인

5) pm2 logs 0로 생성된 pm2가 제대로 실행되고 있는지 확인

Outro

여기까지 작업하면 IP주소로는 배포가 완료된 것이다. 즉, 예를 들어 00.000.000.000:3000 과 같은 주소로 내가 배포한 서비스에 접속이 가능한 상태이다.

이제는 도메인(DNS)에 해당 IP를 연결해야 할 차례이다. 해당 내용은 2편에서 이어 작성해보도록 하겠다.

우리는 웹 사이트를 요청하고 그에 대한 응답을 받을 때 HTTP 프로토콜을 통해 데이터를 주고 받는다. 클라이언트는 서버로부터 응답을 받을 때 웹 페이지뿐만 아니라 HTTP 패킷에 응답의 정보를 담은 코드를 함께 받는데, 이 코드를 HTTP 응답코드(HTTP Response Code)라고 한다.

HTTP 상태 코드는 매우 잘 정리된 형식으로, 상태 코드만 잘 확인해도 클라이언트가 서버로 보낸 요청에 대한 응답이 성공인지 실패인지, 구체적으로 어떤 성공인지 어떤 실패인지를 자세히 알 수 있다. 따라서 클라이언트에선 이 응답코드에 따라 응답의 상태를 판단한다.

📌 HTTP 상태 코드

1️⃣ 1xx Informational (조건부 응답)

리퀘스트를 받고, 처리 중에 있음. (요청을 받았으며 작업을 계속한다)

• 100 Continue (계속) : 요청자는 요청을 계속해야 한다. 서버는 이 코드를 제공하여 요청의 첫 번째 부분을 받았으며 나머지를 기다리고 있음을 나타낸다.

• 101 Switching Protocol (프로토콜 전환) : 요청자가 서버에 프로토콜 전환을 요청했으며 서버는 이를 승인하는 중이다.

• 102 Processing (처리, RFC 2518) : 서버가 요청을 수신하였으며 이를 처리하고 있지만, 아직 제대로 된 응답을 알려줄 수 없음을 알려준다.

  
  

2️⃣ 2xx Success (성공)

리퀘스트를 정상적으로 처리함. (클라이언트 요청이 성공적으로 수행)

• 200 OK (성공) : 응답코드 200을 받았다면, 가장 완벽한 상황이다. 서버가 요청을 제대로 처리했다는 뜻으로 주로 서버가 요청한 페이지를 제공했다는 의미로 쓰인다. 성공의 의미는 HTTP 메서드에 따라 달라진다.

  1) GET : 리소스를 불러와서 메시지 바디에 전송됐다. 2) HEAD : 개체 해더가 메시지 바디에 있다. 3) PUT 또는 POST : 수행 결과에 대한 리소스가 메시지 바디에 전송됐다. 4) DELETE : 삭제를 수행했고 응답 메시지가 이후의 상태를 설명한다. 5) TRACE : 메시지 바디는 서버에서 수신한 요청 메시지를 포함하고 있다.

• 201 Created (작성됨) : 요청이 성공적이었으며 그 결과로 새로운 리소스가 생성. 일반적으로 POST 요청 또는 일부 PUT 요청 이후에 따라온다.

• 202 Accepted (허용됨) : 서버가 요청을 접수했지만 아직 처리하지 않았다.

• 203 Non-Authoritative Information (신뢰할 수 없는 정보) : 서버가 요청을 성공적으로 처리했지만 다른 소스에서 수신된 정보를 제공하고 있다.

• 204 No Content (내용 없음) : 서버가 요청을 성공적으로 처리했지만 콘텐츠를 제공하지 않는다.

  
  

3️⃣ 3xx Redirection (리디렉션, 경로 재지정)

리퀘스트 완료를 위해 추가 동작이 필요함. (클라이언트가 요청을 완료하기 위해 추가 조취를 취해야 함)

• 301 Moved Permanently (영구적 이동) : 요청한 리소스의 URI가 변경되었음을 의미한다. 새로운 URI가 응답에서 주어질 수 있다.

• 304 Not Modified (변경 없음) : 마지막 요청 이후 요청한 페이지는 수정되지 않았다. 서버가 이 응답을 표시하면 페이지의 콘텐츠를 표시하지 않는다. 요청자가 마지막으로 페이지를 요청한 후 페이지가 변경되지 않으면 이 응답을 표시하도록 서버를 구성해야 한다. 이것은 캐시를 목적으로 사용된다. 이것은 클라이언트에게 응답이 수정되지 않았음을 알려주며, 그러므로 클라이언트는 계속해서 응답의 캐시 된 버전을 사용할 수 있다.

• 307 (임시 리다이렉션) : 어떤 페이지가 긴급점검을 하고 있어서 일시적으로 다른 페이지로 리다이렉트해야 할 경우에 이 응답코드를 받게된다. 이 응답을 받았다면 리다이렉트해야 할 페이지로 다시 요청을 하게 된다.

  
  

4️⃣ 4xx Client Error (클라이언트 오류)

클라이언트 요청을 처리할 수 없어 오류 발생함. (클라이언트로 인한 오류 발생)

• 400 Bad Request (잘못된 요청) : 서버에서 필요로하는 어떤 정보를 클라이언트에서 잘못된 구문이나 문법으로 보낸 경우이다. 서버에서 필요로 하는 파라미터 값을 보내지 않았거나, 오타로 잘못된 값을 보내게되면 이 에러코드를 받게된다.

• 401 Unauthorized (권한 없음) : 이 요청은 인증이 필요하다. 이 경우 클라이언트는 요청한 응답을 받기 위해 스스로를 인증해야 한다. 서버는 로그인이 필요한 페이지에 대해 이 요청을 제공할 수 있다. 상태 코드 이름이 권한 없음(Unauthorized)으로 되어 있지만 실제 뜻은 인증 안됨(Unauthenticated)에 더 가깝다.

• 403 Forbidden(접근 금지) : 서버가 요청을 거부하고 있다. 사용자가 리소스에 대한 필요 권한을 갖고 있지 않기 때문. (401은 인증 실패, 403은 인가 실패라 보면 이해하기 편할 것이다.)

• 404 Not Found (찾을 수 없음) : 서버가 요청한 페이지(Resource)를 찾을 수 없다. 클라이언트에서 요청한 페이지가 존재하지 않을 때의 코드이다. 따라서 페이지명을 잘못 입력했거나, 경로를 잘못 입력했을 때 그 자원을 찾을 수 없다면 이 에러코드를 받게된다.

• 405 Method Not Allowed (허용되지 않은 메소드) : 클라이언트에서 요청한 HTTP 메서드를 서버에서 허용하지 않을 경우에 받게되는 응답이다. 우리는 보통 GET, POST와 같은 HTTP 메소드를 사용하는데, 간혹 DELETE 같은 보안상 위협이 되는 메소드는 서버에서 막고 있다. 따라서 이런 메소드를 통해 요청시 허용되지 않음을 알려주는 코드이다.

• 408 Request Timeout (요청 시간 초과) : 서버의 요청 대기가 시간을 초과하였다.

  
  

5️⃣ 5xx Server Error (서버 오류)

서버에서 처리를 하지 못하여 오류 발생함. (서버가 유효한 요청을 명백하게 수행하지 못했음)

• 500 (내부 서버 오류) : 서버에 오류가 발생하여 요청을 수행할 수 없다. 클라이언트의 요청에는 문제가 없으나 서버 내부에서 에러가 발생한 경우이다. 대표적으로 JSP파일에서 예외가 발생하거나, 문법적으로 오류가 있을 때 이 에러가 발생한다.

• 501 (구현되지 않음) : 서버에 요청을 수행할 수 있는 기능이 없다. 예를 들어 서버가 요청 메소드를 인식하지 못할 때 이 코드를 표시한다.

• 502 Bad Gateway (불량 게이트웨이) : 서버가 게이트웨이나 프록시 역할을 하고 있거나, 업스트림 서버에서 잘못된 응답을 받았다.

• 503 (서비스를 사용할 수 없음) : 서버가 오버로드되었거나 유지관리를 위해 다운되었기 때문에 현재 서버를 사용할 수 없는 상태이다. 급격하게 부하가 몰리거나, 서버가 임시 보수 중인 경우에 나타난다. (속된말로 서버가 터진 상황) 이는 대개 일시적인 상태이다.

• 504 (게이트웨이 시간초과) : 서버가 게이트웨이나 프록시 역할을 하고 있거나 또는 업스트림 서버에서 제때 요청을 받지 못했다.

  
  

💡 요약

1xx, 2xx, 3xx까지는 정상적인 처리 또는 과정 및 정보를 뜻하는 반면, 4xx, 5xx 경우는 에러의 의미, 즉 어딘가 문제가 발생했음을 의미한다.

📚 Reference

• https://ko.wikipedia.org/wiki/HTTP_%EC%83%81%ED%83%9C_%EC%BD%94%EB%93%9C
• https://developer.mozilla.org/ko/docs/Web/HTTP/Status
• https://surprisecomputer.tistory.com/47

로컬에서 코드를 수정한 후, 깃헙으로 업로드를 하려고 했는데 token이 만료되었다는

새로운 토큰을 발급받고 입력한 후 재업로드

또 에러

🔑 Solution

Git 접속 -> 프로필 클릭 -> Settings -> Developer settings -> Personal access tokens

우선 위와 같은 경로로 들어간다.

그리고 다음과 같이 "Generate new token"을 눌러준다.

먼저 생성할 토큰의 이름과 토큰의 유효기간을 설정해준다.

그리고 다음과 같이 "repo, admin :org, gist, user" 를 모두 체크해준다. 이 중 하나라도 체크를 하지 않으면 또다시 같은 오류가 발생할 것이다.

📚 Reference

• https://amid1jungs.tistory.com/60

Next JS로 작업을 하던 중, 외부 이미지를 불러와 사용해야 할 일이 생겼다. 늘상 하던대로 Next의 Image 컴포넌트의 src 값으로 내가 사용할 이미지의 url을 넣어주었다. 그랬더니 다음과 같은 에러가 발생했다.

에러 문구를 살펴 보니 다음과 같았다.

On one of your pages that leverages the next/image component, you passed a src value that uses a hostname in the URL that isn't defined in the images.domains config in next.config.js.

쉽게 설명하자면, Next의 Image 컴포넌트는 src에 들어가는 도메인을 미리 next.config.js에 정의를 해줄 필요가 있기 때문에 발생하는 에러였다. 정적파일의 접근은 상관없지만, 나는 외부 서버의 이미지를 가져와야하기 때문에 도메인 설정이 필요했던 것이었다.

🔑 Solve

해결 방법은 간단했다.

const nextConfig = {
  reactStrictMode: true,
    images: {
      domains: [
        "w.namu.la",
        "t1.daumcdn.net",
    ]
  }
}

next.config.js 파일을 열어 위와 같이 images의 도메인을 설정해주면 된다. 이때 설정할 도메인으론 에러메세지에서 hostname 다음 따옴표속 URL을 적어주면 된다.

이때 주의해야 할 점은 도메인 설정을 최상단에 해주지 않으면 인식을 잘 못할수도 있다는 점이다. 그러니 도메인 설정은 최상단에 해주도록 한다.

수정 후 서버를 껐다가 다시 키면 삽입한 이미지를 확인할 수 있을 것이다. 👍

📚 Reference

• https://velog.io/@hhhminme/Next.js%EC%97%90%EC%84%9C-Nextimage%EC%97%90%EC%84%9C-%EC%99%B8%EB%B6%80-%EC%9D%B4%EB%AF%B8%EC%A7%80%EB%A5%BC-%EB%AA%BB%EA%B0%80%EC%A0%B8%EC%98%A4%EB%8A%94-%EB%AC%B8%EC%A0%9C%EB%8F%84%EB%A9%94%EC%9D%B8-%EC%84%A4%EC%A0%95%ED%95%98%EA%B8%B0-loader-%EC%A0%81%EC%9A%A9%ED%95%98%EA%B8%B0
• https://jae04099.tistory.com/entry/ERROR-Error-Invalid-src-prop-on-nextimage

사용자의 세션정보를 저장해서 로그인 기능을 구현하는 방법이다. 간단히 정리해보면 다음과 같다.

• 유저가 로그인 했었다는 정보를 서버의 메모리에 기록해놓는다. (세션을 저장)

• 유저가 로그인이 필요한 페이지(Mypage 등)를 요청할 경우,

• 세션에서 해당 유저가 로그인했다는 정보가 발견되면 해당 페이지를 유저에게 제공한다.

  
  

좀 더 자세한 과정은 다음과 같다.

🔐 로그인

1. 유저가 로그인을 한다.

이때 유저가 제출한 아이디, 비번이 DB에 저장된 회원정보와 일치한다면, 서버는 세션스토어에 세션을 하나 만들어 저장한다.

📖 세션 : 유저가 언제 어디서 로그인 했는지 등의 정보를 담은 자료.

ex) "dev_sony 라는 사람이 20시에 서울시에서 로그인했습니다."

*2. 로그인한 유저마다 유니크한 세션아이디를 발급한다. *

이때 로그인한 사람이 여러명일 수 있으니, 유저마다 유니크한 세션아이디를 발급해서 서로 구분지어준다.

*3. 발급한 세션아이디는 쿠키에 담아서 고객 브라우저에 전송해준다. *

세션아이디는 고객과 서버 둘다 보관하기에 쿠키에 담아서 고객에게 보내준다.

📖 쿠키 : 브라우저에 마련되어있는 일종의 문자데이터 저장공간으로 이곳에 세션아이디가 기록된다.

🔐 로그인이 필요한 페이지를 요청한 유저가 로그인했던 사람인지 검사.

*1. 유저가 로그인을 한다. *

이때 ID / PW 를 서버로 전송하면 서버는 DB에 해당 ID / PW 가 존재하면 세션아이디를 만들어준다. 그리고 세션아이디들을 담을 변수 혹은 DB 공간을 마련해 저장하는데, 이걸 세션데이터라고한다. 그후 세션아이디를 쿠키에 담고 유저의 브라우저에 쿠키를 저장한다.

*2. 유저가 페이지를 요청한다. *

유저가 로그인이 필요한 페이지를 요청하면 서버는 렌더링을 해주기 전 해당 유저가 로그인을 한 상태인지 확인한다.

*3. 쿠키에 세션아이디가 포함되어있는지 검사한다. *

유저가 페이지를 요청하면 자동으로 쿠키가 서버로 전송된다. 서버는 쿠키에 기록된 세션아이디를 서버메모리, 혹은 DB에 저장되어있던 세션아이디와 비교해서 해당 세션아이디가 존재하면 해당 유저가 로그인을 한 상태라고 판단한다.

*4. 서버는 유저가 요청한 페이지를 보내준다. *

이때 DB상의 정보가 필요하다면 세션데이터를 참고해서 해당 정보를 DB에서 꺼내온다.

⚡️ 다시 한번 정리해보자면 다음과 같다.

• ID / PW 를 DB에 기록할 수 있는 회원가입 폼을 만들고,
• 누군가 로그인을하면 세션아이디를 하나 발급하여 서버와 유저가 나눠가진다.
• 그후 해당 유저가 특정한 페이지를 요청하면 해당 유저의 세션아이디가 DB상에 존재하는지 검사한다.
  

📌 JSON Web Token (JWT)

JWT 는 세션데이터를 서버에 저장하지 않은채로 페이지를 열람할 수 있는 열쇠(토큰)를 유저에게 부여하는 방식이다. 따라서 토큰은 session 방식 보다 더 많은 정보들을 담게된다.

아무튼 어떤 방식인지 자세히 알아보도록 합시다.

*1. 유저가 로그인을 한다. *

유저가 로그인시 제출한 ID / PW 가 DB 상에 저장되어 있다면 서버는 Token 하나를 만들어서 유저의 브라우저로 보내준다.

📖 Token : 암호화된 긴 문자열로, 유저의 로그인 유무, 아이디 등의 정보들을 넣을 수 있다.

이때 위조가 불가능하도록 특별한 서명이 추가된다. 그리고 토큰은 쿠키 또는 로컬스토리지에 저장된다.

*2. 유저가 페이지를 요청한다. *

유저가 로그인이 필요한 페이지를 요청하면 서버는 렌더링을 해주기 전 해당 유저의 토큰을 검사한다.

*3. 서버는 토큰을 검사한다. *

유저가 페이지 요청 시 함께 보낸 Token이 적법한지 검사한다. 유통기한이 지나지 않았는지, 서명이 잘 되어있는지, 블랙리스트에 등록된 토큰인지 등의 검사를 거친 후 이상이 없으면 요청한 페이지로 통과시켜준다.

💥 장점

• 토큰의 구현이 매우 간단하다.
• 서버는 세션데이터 등을 메모리나 DB에 저장해둘 필요가 없으니 서버 스케일링시 큰 문제가 없다.
  

💥 단점

• 유저의 로그인 유무에 대한 정보 전체를 서버는 가지고 있지 않고 유저만 가지고 있다는 점에서 보안상 좋은 방법은 아니다.

• JWT 정보가 도난 될 경우 보안에 매우 취약해진다.

📖 stateful JWT : '어떤 사람이 언제 어디서 로그인했는지'룰 서버에 저장해두는 방식.

ex) refresh token

📌 Open Autentication

이 방법은 쉽게말하면 페이스북, 구글 로그인입니다. 고객의 페이스북, 구글 계정정보를 불러와서 그걸 가지고 가입을 승인시켜주는 방법입니다.

💥 장점

• 비밀번호를 취급하지 않아도 되므로 관리가 편리하고, 유저에게도 편리함을 제공한다.
• 공식 개발문서가 많기 때문에 상대적으로 개발하기가 수월하다.
  

💥 단점

• 구글이나 페이스북이 1. OAuth를 중단 2. 방법을 수정 3. 페이스북 API 서버 다운으로 접속이 불가능하다면 사이트 로그인도 불가능하다.

주어진 사전 파일의 단어들을 연결리스트로 담아 사전 프로그램을 만든다.

⚡️ 단어 사전 파일

• randdict.txt 파일에는 약 5만개의 단어와 그 뜻이 저장되어 있다. 저장된 순서는 없다.
• 단어와 단어의 뜻은 " : " 으로 구분되어 있다. (ex. apple : 사과)
  

⚡️ 단어 사전 데이터로 연결리스트 만들기

• 자료형은 연결 리스트를 이용한다.
• 사전의 단어들을 연결리스트에 추가할 때에는 알파벳 순으로 정렬된 상태로 저장한다.
  

완성된 프로그램의 실행 예시는 다음과 같다.

📌 연결리스트를 어떤 형태로 만들 것인가?

이중 연결리스트로 만들었다.

⚡️ Why?

• 우선 해당 연결 리스트는 사전의 단어들이 ‘정렬된’상태로 저장되어야 한다.
• 이를 위해 단일 연결 리스트는 새로운 단어가 추가될 때 마다 head부터 탐색하여 해당 단어가 들어갈 위치를 찾아야한다. (정렬된 상태를 유지해야 하므로)
• 이는 매우 비효율적이고 동시에 많은 높은 시간 복잡도를 요하는 방식이란 생각이 들어 더 나 은 자료 구조가 없는지 생각해 보았다.
• 그렇게 생각해낸 것이 ‘이중 연결 리스트’였다.
• 이중 연결 리스트는 head나 tail이 아닌 내가 원하는 특정한 지점(ex. 중간, 1/3 지점, 1/4지점…) 의 위치 정보를 저장해두고, 해당 위치를 기준으로 탐색을 수행할 수 있어 단일 연결 리스트 보 다 효율적인 방식이란 생각이 들었다.
• 그리고 실제로 이를 위해 head와 tail 외에 mid, 즉 연결 리스트의 중간 위치를 반환하는 변수 를 따로 설정해 주었고, 이를 기준점으로 삼아 탐색을 수행하도록 하였다.
  

🛠 Doubly Linked List class

class dbList:
    def __init__(self):
        self.head = None         # 링크드 리스트의 가장 앞 노드
        self.tail = None         # 링크드 리스트의 가장 뒤 노드
        self.mid = None         # 링크드 리스트의 중간 위치 노드
        self.pos = 0             # mid 의 위치를 조정하기 위한 flag
        self.size = 0             # 링크드 리스트의 노드의 개수

head(맨 앞), tail(맨 뒤) 변수 외에도 mid(중간) 변수를 선언한 것을 확인할 수 있다. 또한 mid의 위치를 연결 리스트의 중앙으로 조정해주기 위한 변수 pos와 연결 리스트의 전체 node의 개수를 나타내는 size변수도 선언하였다.

🛠 class Node

class Node:
    def __init__(self, data):
        self.data = data # 실제 노드가 저장하는 데이터
        self.next = None # 다음 노드에 대한 레퍼런스
        self.prev = None # 전 노드에 대한 레퍼런스

노드가 저장하는 데이터(단어와 그 뜻) data, 현재 노드의 다음 노드에 대한 레퍼런스를 나타내는 변수 next, 그리고 다음 노드에 대한 레퍼런스를 나타내는 변수 prev를 선언하였다.

🛠 isEmpty( )

def isEmpty(self):
    if self.size != 0:
        return False
    else:
        return True

연결 리스트가 비어 있는지 판단해주는 메소드이다.

🛠 insert( )

def insert(self, pre, data):
    new_node = Node(data)

    if pre is self.tail:             # 가장 마지막 순서 삽입
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node
    else:                             # 두 노드 사이에 삽입
        new_node.prev = pre
        new_node.next = pre.next
        pre.next.prev = new_node
        pre.next = new_node

    self.size += 1

연결 리스트의 원하는 위치에 노드를 삽입해주는 메소드이다. 삽입할 노드의 데이터(data)와 삽입할 위치 앞의 노드(pre)의 위치를 매개변수로 받는다.

🛠 append( )

def append(self, data):
    new_node = Node(data)

    if self.isEmpty():
        self.head = new_node
        self.tail = new_node
        self.mid = new_node
    else:
        temp = self.head
        self.head = new_node
        temp.prev = self.head
        new_node.next = temp

    self.size += 1

비어 있는 연결 리스트, 혹은 비어 있지 않은 연결리스트의 맨 앞에 노드를 삽입하는 메소드이다.

📌 어떻게 제공된 사전 파일의 단어들을 정렬된 형태의 연결리스트로 만들 것인가?

🛠 makeDict( )

def makeDict(self, data):

randdict의 단어들을 순서대로 가져와 정렬한 채로 링크드 리스트에 넣어 주는 메소드이다. 이 메소드의 작동 방식은 다음과 같다.

iterator = self.mid

우선 연결 리스트를 돌아다니며 새로운 단어가 추가 될 위치를 탐색하게 될 변수 iterator를 선언 해주고, 해당 변수의 위치를 연결리스트의 중앙(mid)으로 초기화 시켜준다.

앞서 설명했던 대로 매번 연결 리스트의 맨 앞부터 탐색하는 것보단 중앙에서 탐색을 시작하는 것이 보다 효율적일 것 같다고 생각하여 위와 같은 과정을 수행하였다.

그리고는 케이스를 분류하여 각 케이스마다 알맞은 작업을 수행하였다.

⚡️ Case

1) 리스트가 비어 있을 경우

append 메소드로 새로운 단어를 추가해준다.

2) 리스트가 비어 있지 않을 경우

2-1) 추가될 단어가 iterator 위치에 해당하는 단어 보다 작을 때 (알파벳 순서상 앞에 위치)

a. iterator 앞에 노드가 없을 경우

• 리스트의 맨 앞에 해당 단어 바로 추가 (by append 메소드)

b. 추가될 단어가 iterator.prev에 해당하는 단어 보다 작을 경우

• iterator 위치 왼쪽으로 한 칸 이동

c. 추가될 단어가 iterator.prev에 해당하는 단어 보다 클 경우 (알파벳 순서상 뒤에 위치)

• iterator 와 iterator.prev 사이에 해당 단어 삽입 (by insert 메소드)

d. 추가될 단어가 iterator.prev에 해당하는 단어와 같을 경우 (randdict에는 중복된 단어가 존재하지 않는데 위와 같은 경우가 발생하는 이유는 lower( )함수를 사용하여 모든 단어를 소문자로 변환한 뒤 해당 단어들을 비교하기 때문이다.)

d-1) lower를 떼고 비교 했을 때, 추가될 단어가 iterator.prev에 해당하는 보다 작을 경우

• iterator.prev 앞에 노드가 없을 경우 : 리스트의 맨 앞에 해당 단어 바로 추가
• 아닐 경우 : iterator.prev 와 iterator.prev.prev 사이에 해당 단어 삽입

d-2) lower를 떼고 비교 했을 때, 추가될 단어가 iterator.prev에 해당하는 보다 클 경우

• iterator 와 iterator.prev 사이에 해당 단어 삽입
  

2-2) 추가될 단어가 iterator 위치에 해당하는 단어 보다 클 때

a. iterator 뒤에 노드가 없을 경우

• 리스트의 맨 뒤에 해당 단어 바로 추가 (by insert 메소드)

b. 추가될 단어가 iterator.next에 해당하는 단어 보다 클 경우

• iterator 위치 오른쪽으로 한 칸 이동

c. 추가될 단어가 iterator.next에 해당하는 단어 보다 작을 경우

• iterator 뒤에 해당 단어 삽입 (by insert 메소드)

d. 새로 추가될 단어가 iterator.next에 해당하는 단어와 같을 경우

d-1) lower를 떼고 비교 했을 때, 추가될 단어가 iterator.next에 해당하는 단어보다 작을 경우

• iterator.next 뒤에 해당 단어 삽입

d-2) lower를 떼고 비교 했을 때, 추가될 단어가 iterator.next에 해당하는 단어보다 클 경우

• iterator.next 뒤에 해당 단어 삽입
  

3) pos값의 변화

앞서 설명한대로 pos는 mid의 위치를 연결 리스트의 중앙으로 조정해주기 위한 변수이다.

size가 짝수일때는 이 pos의 값이 0, -1 혹은 +1이면 iterator의 위치가 mid(중앙)이고, 홀수일때는 pos의 값이 0이면 iterator의 위치가 mid(중앙)이다.

해당 작업이 잘 수행되도록 하기 위해 iterator, 즉 mid가 연결리스트의 왼쪽으로 이동할 경우엔 pos에 -1을, 오른쪽으로 이동할 경우엔 pos에 +1을 해준다.

이는 곧 mid를 기준으로 왼쪽과 오른쪽의 균형을 맞춰주는 것을 의미한다. 그러다 균형이 깨지면 (pos = -2 or pos = +2) 다음과 같은 작업을 수행한다.

• pos = -2 : mid를 왼쪽으로 한 칸 이동 & pos = 0
• pos = +2 : mid를 오른쪽으로 한 칸 이동 & pos = 0

위와 같은 과정들을 통해 mid의 위치를 계속하여 연결리스트의 중앙으로 유지시킬 수 있다.

📌 단어 검색 & 단어 추가 기능은 어떻게 구현할 것인가?

🛠 search( )

def search(self, target):

연결 리스트에서 원하는 단어를 탐색하기 위한 메소드이다. 해당 메소드도 마찬가지로 연결리스트의 중간부터 탐색을 시작한다. 그리고는 케이스를 분류하여 각 케이스마다 알맞은 작업을 수행하였다.

⚡️ Case

1) 찾고자 하는 단어가 iterator에 해당하는 단어와 같을 경우 (lower( )를 수행한 값)

a. lower를 떼고 비교 했을 때, 찾고자 하는 단어가 iterator에 해당하는 단어와 같을 경우

• iterator에 해당하는 단어의 뜻 출력

b. lower를 떼고 비교 했을 때, 찾고자 하는 단어가 iterator 보다 작을 경우

• iterator 위치 왼쪽으로 한 칸 이동

b-1) 이동한 위치에 해당하는 단어와 찾고자 하는 단어가 일치할 경우

• iterator에 해당하는 단어의 뜻 출력

b-2) 이동한 위치에 찾고자 하는 단어가 없을 경우

• newWord 메소드 호출

c. lower를 떼고 비교 했을 때, 찾고자 하는 단어가 iterator 보다 클 경우

• iterator 위치 오른쪽으로 한 칸 이동

c-1) 이동한 위치에 해당하는 단어와 찾고자 하는 단어가 일치할 경우

• iterator에 해당하는 단어의 뜻 출력

c-2) 이동한 위치에 찾고자 하는 단어가 없을 경우

• newWord 메소드 호출
  

2) 찾고자 하는 단어가 iterator에 해당하는 단어 보다 작을 경우

a. iterator 앞에 노드가 없을 경우

• newWord 메소드 호출

찾고자 하는 단어가 연결 리스트 상에 존재하지 않는 경우이기 때문이다.

b. 찾고자 하는 단어가 iterator.prev에 해당하는 단어 보다 클 경우

• newWord 메소드 호출

이 또한 찾고자 하는 단어가 연결 리스트 상에 존재하지 않는 경우이다. 왜냐하면 이는 target을 찾아 특정 방향으로 탐색을 계속해서 진행하다가(one way) 한번 그 방향이 반대 방향으로 틀어졌음, 즉 target이 연결 리스트 상에 존재하지 않음을 의미하기 때문이다.

c. 위의 경우들에 해당하지 않는다면

• iterator 위치 왼쪽으로 한 칸 이동
  

3) 찾고자 하는 단어가 iterator에 해당하는 단어 보다 클 경우

a. iterator 뒤에 노드가 없을 경우

• newWord 메소드 호출

찾고자 하는 단어가 연결 리스트 상에 존재하지 않는 경우이기 때문이다.

b. 찾고자 하는 단어가 iterator.next에 해당하는 단어 보다 작을 경우

• newWord 메소드 호출

이 또한 찾고자 하는 단어가 연결 리스트 상에 존재하지 않는 경우이다. 왜냐하면 이는 target을 찾아 특정 방향으로 탐색을 계속해서 진행하다가(one way) 한번 그 방향이 반대 방향으로 틀어졌음, 즉 target이 연결 리스트 상에 존재하지 않음을 의미하기 때문이다.

c. 위의 경우들에 해당하지 않는다면

• iterator 위치 오른쪽으로 한 칸 이동
  

🛠 newWord( )

def newWord(self, inputWord):

찾고자 하는 단어가 없을 경우, 해당 단어를 연결 리스트에 추가해주는 메소드이다.

📌 실행결과

📌 전체코드

"""Node 클래스"""
class Node:
    def __init__(self, data):
        self.data = data        # 실제 노드가 저장하는 데이터
        self.next = None        # 다음 노드에 대한 레퍼런스
        self.prev = None        # 전 노드에 대한 레퍼런스

"""더블 링크드 리스트 클래스"""
class dbList:
    def __init__(self):
        self.head = None    # 링크드 리스트의 가장 앞 노드
        self.tail = None    # 링크드 리스트의 가장 뒤 노드
        self.mid = None     # 링크드 리스트의 중간 위치 노드
        self.pos = 0        # mid의 위치를 조정하기 위한 flag
        self.size = 0       # 링크드 리스트의 노드의 개수

    """링크드 리스트가 비어 있는지 판단하는 메소드"""
    def isEmpty(self):
        if self.size != 0:
            return False
        else:
            return True

    """링크드 리스트의 원하는 위치에 노드를 삽입하는 메소드"""
    # 삽입할 노드의 데이터와 삽입할 위치 앞의 노드(pre)의 위치를 매개변수로 받는다
    def insert(self, pre, data):
        new_node = Node(data)

        if pre is self.tail:            # 가장 마지막 순서 삽입
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        else:                           # 두 노드 사이에 삽입
            new_node.prev = pre
            new_node.next = pre.next
            pre.next.prev = new_node
            pre.next = new_node
        self.size += 1

    """비어 있는 링크드 리스트, 혹은 비어 있지 않은 리스트의 맨 앞에 노드를 삽입하는 메소드"""
    def append(self, data):
        new_node = Node(data)

        if self.isEmpty():            # 링크드 리스트가 비어 있을때
            self.head = new_node
            self.tail = new_node
            self.mid = new_node
        else:                         # 비어 있지 않을때 : 리스트의 맨 앞에 노드 삽입
            temp = self.head
            self.head = new_node
            temp.prev = self.head
            new_node.next = temp
        self.size += 1

    """randdict의 단어들을 순서대로 가져와 정렬한 채로 링크드 리스트에 넣어 주는 메소드"""
    def makeDict(self, data):
        if self.isEmpty():                                                     # 리스트가 비어 있을 경우
            self.append(data)
        else:                                                                   # 리스트가 비어 있지 않을 경우
            iterator = self.mid                                                 # 리스트의 중간부터 새로 추가될 단어가 삽입될 위치 탐색
            if data[0].lower() < iterator.data[0].lower():                      # data[0]이 mid.data[0] 보다 작을 때
                while True:
                    if iterator.prev is None:                                   # iterator 앞에 노드가 없을 경우
                        self.append(data)                                       # 리스트의 맨 앞에 바로 추가
                        break
                    elif data[0].lower() < iterator.prev.data[0].lower():       # 새로 추가될 단어가 iterator.prev 보다 작을 경우 (알파벳 순서상 앞에 위치)
                        iterator = iterator.prev                                # iterator 위치 한칸 앞으로 이동
                    elif data[0].lower() > iterator.prev.data[0].lower():       # 새로 추가될 단어가 iterator.prev 보다 클 경우 (알파벳 순서상 뒤에 위치)
                        self.insert(iterator.prev, data)                        # iterator 와 iterator.prev 사이에 해당 단어 삽입
                        break
                    elif data[0].lower() == iterator.prev.data[0].lower():      # 새로 추가될 단어가 iterator.prev 와 같을 경우 (lower() 때문에)
                        if data[0] < iterator.prev.data[0]:                     # 원본으로 복구 시켜 비교했을때, 새로 추가될 단어가 iterator.prev 보다 작을 경우(알파벳 순서상 앞에 위치)
                            if iterator.prev.prev is None:                      # iterator.prev 앞에 노드가 없을 경우
                                self.append(data)                               # 리스트의 맨 앞에 바로 추가
                                break
                            else:
                                self.insert(iterator.prev.prev, data)           # 아닐 경우엔 iterator.prev 와 iterator.prev.prev 사이에 해당 단어 삽입
                                break
                        elif data[0] > iterator.prev.data[0]:                   # 원본으로 복구 시켜 비교했을때, 새로 추가될 단어가 iterator.prev 보다 클 경우(알파벳 순서상 뒤에 위치)
                            self.insert(iterator.prev, data)                    # iterator 와 iterator.prev 사이에 해당 단어 삽입
                            break
                self.pos -= 1                                                   # 링크드 리스트의 왼쪽으로 이동할 경우엔 pos에 -1

            else:                                                               # data[0]이 mid.data[0] 보다 클 때
                while True:
                    if iterator.next is None:                                   # iterator 뒤에 노드가 없을 경우
                        self.insert(iterator, data)                             # 리스트의 맨 뒤에 바로 추가
                        break
                    elif data[0].lower() > iterator.next.data[0].lower():       # 새로 추가될 단어가 iterator.next 보다 클 경우 (알파벳 순서상 뒤에 위치)
                        iterator = iterator.next                                # iterator 위치 한칸 뒤로 이동
                    elif data[0].lower() < iterator.next.data[0].lower():       # 새로 추가될 단어가 iterator.next 보다 작을 경우 (알파벳 순서상 앞에 위치)
                        self.insert(iterator, data)                             # iterator 뒤에 해당 단어 삽입
                        break
                    elif data[0].lower() == iterator.next.data[0].lower():      # 새로 추가될 단어가 iterator.next 와 같을 경우 (lower() 때문에)
                        if data[0] < iterator.next.data[0]:                     # 원본으로 복구 시켜 비교했을때, 새로 추가될 단어가 iterator.next 보다 작을 경우 (알파벳 순서상 앞에 위치)
                            self.insert(iterator, data)                         # iterator 뒤에 해당 단어 삽입
                            break
                        elif data[0] > iterator.next.data[0]:                   # 원본으로 복구 시켜 비교했을때, 새로 추가될 단어가 iterator.next 보다 클 경우 (알파벳 순서상 뒤에 위치)
                            self.insert(iterator.next, data)                    # iterator.next 뒤에 해당 단어 삽입
                            break
                self.pos += 1                                                   # 링크드 리스트의 오른쪽으로 이동할 경우엔 pos에 +1

            """mid 위치 설정 : pos의 값이 0일때의 mid의 위치가 링크드 리스트의 중앙이다."""
            if self.pos == 2:               # pos가 2가 되면
                self.mid = self.mid.next    # mid를 오른쪽으로 이동
                self.pos = 0                # pos값 다시 0으로
            elif self.pos == -2:            # pos가 -2가 되면
                self.mid = self.mid.prev    # mid를 왼쪽으로 이동
                self.pos = 0                # pos값 다시 0으로

    """링크드 리스트에서 원하는 단어를 탐색하기 위한 메소드"""
    def search(self, target):
        iterator = self.mid                                             # 리스트의 중간부터 찾고자 하는 단어(target) 탐색 시작
        while True:
            if target.lower() == iterator.data[0].lower():              # 찾고자 하는 단어가 iterator 와 같을 경우 (lower() 때문에)
                if target == iterator.data[0]:                          # 원본으로 복구 시켜 비교했을때, 찾고자 하는 단어가 iterator 와 같을 경우
                    print(iterator.data[1])                             # iterator에 해당하는 단어의 뜻 출력
                    break
                elif target < iterator.data[0]:                         # 찾고자 하는 단어가 iterator 보다 작을 경우 (알파벳 순서상 앞에 위치)
                    iterator = iterator.prev                            # iterator 위치 한칸 앞으로 이동
                    if target == iterator.data[0]:                      # 찾고자 하는 단어가 iterator(이동 한 위치) 와 같을 경우
                        print(iterator.data[1])                         # iterator에 해당하는 단어의 뜻 출력
                        break
                    else:                                               # 찾고자 하는 단어가 없을 경우
                        self.newWord(target)                            # newWord 메소드 호출
                        break
                else:                                                   # 찾고자 하는 단어가 iterator 보다 클 경우 (알파벳 순서상 뒤에 위치)
                    iterator = iterator.next                            # iterator 위치 한칸 뒤로 이동
                    if target == iterator.data[0]:                      # 찾고자 하는 단어가 iterator(이동 한 위치) 와 같을 경우
                        print(iterator.data[1])                         # iterator에 해당하는 단어의 뜻 출력
                        break
                    else:                                               # 찾고자 하는 단어가 없을 경우
                        self.newWord(target)                            # newWord 메소드 호출
                        break
            elif target.lower() < iterator.data[0].lower():             # 찾고자 하는 단어가 iterator 보다 작을 경우 (알파벳 순서상 앞에 위치)
                if iterator.prev is None:                               # iterator 앞에 노드가 없을 경우
                    self.newWord(target)                                # newWord 메소드 호출
                    break
                elif target.lower() > iterator.prev.data[0].lower():    # 찾고자 하는 단어가 iterator.prev 보다 클 경우 (알파벳 순서상 뒤에 위치)
                    self.newWord(target)                                # newWord 메소드 호출 -> 튕겨져 나온 경우 이므로 찾는 단어가 없다는 의미이다
                    break
                else:                                                   # 위의 경우들에 해당하지 않는다면
                    iterator = iterator.prev                            # iterator 위치 한칸 앞으로 이동
            else:                                                       # 찾고자 하는 단어가 iterator 보다 클 경우 (알파벳 순서상 뒤에 위치)
                if iterator.next is None:                               # iterator 뒤에 노드가 없을 경우
                    self.newWord(target)                                # newWord 메소드 호출
                    break
                elif target.lower() < iterator.next.data[0].lower():    # 찾고자 하는 단어가 iterator.next 보다 작을 경우 (알파벳 순서상 앞에 위치)
                    self.newWord(target)                                # newWord 메소드 호출 -> 튕겨져 나온 경우 이므로 찾는 단어가 없다는 의미이다
                    break
                else:                                                   # 위의 경우들에 해당하지 않는다면
                    iterator = iterator.next                            # iterator 위치 한칸 뒤로 이동

    """찾고자 하는 단어가 없을 경우, 해당 단어를 추가하는 메소드"""
    def newWord(self, inputWord):
        print('찾을 수 없는 단어입니다. 뜻을 추가하세요(추가하지 않으려면 공백)')
        inputMean = input('> ')

        if inputMean == '':
            pass
        else:
            newData = [inputWord, inputMean]
            self.makeDict(newData)
            print(newData[0], newData[1], '가 추가되었습니다.(총 %d개 단어)' % self.size)

f = open('randdict_utf8.TXT', 'r')
dict = dbList()                            # randdict의 단어를 가져와 담아 줄 링크드 리스트

while True:
    line = f.readline()
    if line == '':
        break
    word = line[:line.find(':') - 1]      # 단어
    mean = line[line.find(':') + 2:-1]    # 단어의 뜻
    data = [word, mean]                   # [단어, 뜻]
    dict.makeDict(data)
f.close()

while True:
    target = input(">>")
    dict.search(target)

📌 Review

프로그램을 실행해본 결과 내 의도대로 이중 연결 리스트를 사용했기 때문인지는 모르겠지만 단어를 검색하는 작업과, 존재하지 않는 단어를 연결리스트상에 추가하고, 이를 다시 탐색하는 작업은 매우 빠르게 수행되었다.

그러나 데이터의 양이 꽤 많아서인지 단어장의 단어들을 가져와 정렬된 상태로 연결 리스트를 만드는 과정에는 꽤 많은 시간이 소요되었다. (대략 1분 30초정도) 따라서 해당 부분에 대한 보완에 대해서도 좀 더 생각해봐야 할 필요가 있다고 느꼈다.

문자가 입력되어 큐에 쌓이는 시스템에서 필요한 수만큼 문자를 가져오는 프로그램을 작성한다.

⚡️ 조건

• 해당 프로그램은 문자가 큐로 들어온다.
• 사용자가 필요한 데이터의 개수를 입력하면 큐에서 해당 데이터를 가져온다.
• 사용되는 큐의 크기는 20(문자)이다. 큐의 크기를 초과한 데이터는 받아들일 수 없다. (에러 표시)
• 사용되는 큐는 원형 큐이다. 직접 원형 큐를 만들어야 한다.
  

⚡️ 큐 입력

• 사용자가 입력한 n 개의 문자 (AZ, az) 를 순차적으로 큐에 넣는다.
  

⚡️ 큐 출력

• 사용자가 숫자 (1~9) 를 넣으면 큐에서 해당 수만큼 가져와 화면에 표시한다.
• 0 을 넣으면 큐에서 가져오지 않고 큐의 상태를 화면에 표시한다.
  

완성된 프로그램의 실행 예시는 다음과 같다.

📌 큐의 형태

원형 큐의 Empty와 Full상태를 구별하기 위한 방식은 두가지가 있다.

1. 별도의 flag 변수를 사용한다. ⚡️ flag == True : 원소가 존재, flag == False : 원소가 존재하지 않는다
2. 큐의 한칸은 비워둔다.

그 중 첫번째 방식을 통해, 즉 별도의 flag 변수를 사용하여 큐를 만들어 보았다.

📌 Code 설명

🛠 flag 변수

self.flag = False

큐의 Empty와 Full상태를 구분하기 위한 변수 flag를 선언하고 그 값을 False로 초기화해주었다. 큐에 값이 들어있을 경우엔 True값을, 없을 경우엔 False값을 가진다.

🛠 is_Empty(self)

def is_Empty(self):
    return not self.flag

큐가 비었는지 판단해주는 함수로, flag와 반대의 값을 반환한다.

Flag == True : 큐에 값이 존재하므로 -> is_Empty == False Flag == False : 큐에 값이 존재하지 않으므로 -> is_Empty == True

🛠 is_Full(self)

def is_Full(self):
    if self.flag:
        return self.front == self.rear % QSIZE
    else:
        return False

만약 flag == True이면, 즉 큐에 값이 있을 경우엔 큐의 front의 위치와 rear(% QSIZE)의 위치가 같은지 판단하여 그 결과값을 반환한다.

아닌 경우엔 False를 반환한다.

🛠 push_Queue(self, item)

def push_Queue(self, item):
    for i in range(len(item)):
        if not self.is_Full():
            self.items[self.rear] = item[i]
            self.rear = (self.rear + 1) % QSIZE
            print("(SYSTEM) ADDQUEUE(%s)" % item[i],
                "F=%d R=%d" % (self.front, self.rear))
            self.flag = True

큐가 가득 차 있지 않은 경우에 (not self.is_Full( )) 문자열을 입력 받으면(ex. “ABC”), 이를 문자별로 쪼개서 큐에 담아준다. 그리고 입력 받은 문자열의 문자의 개수 만큼 rear의 위치도 이동시켜준다. 이때, 원형 큐 이므로 항상 rear의 값에 “% QSIZE”연산을 수행해준다. 그리고나서 각 문자별로 입력되었음을 확인시켜주는 문장을 출력해준다. 마지막으로 flag의 값을 True로 바꿔주고 메소드를 종료시킨다. (큐에 값이 들어왔으므로)

🛠 pop_Queue(self, n)

def pop_Queue(self, n):
    for i in range(n):
        if not self.is_Empty():
            pop = self.items[self.front]
            self.front = (self.front+1) % QSIZE
            print("DELETEQUEUE() =%s," % pop, "F=%d R=%d" % (self.front,
                self.rear))
            if self.flag and self.front == self.rear:
                self.flag = False
        else:
            print("DELETEQUEUE() FAIL. QueueEmpty")

큐가 비어 있지 않은 경우에 (not self.is_Empty( )) 외부로부터 n 이라는 정수를 입력 받고, n 만큼 반복하면서 큐에 들어있는 값들을 하나씩 가져오고, 각 문자별로 꺼냈음을 확인시켜주는 문장을 출력해준다. 그리고 가져올때마다 front의 위치도 한 칸 씩 앞으로 옮겨준다. 이때, flag의 위치와 rear의 위치가 같아지면 이는 큐가 비었음을 의미하므로, flag의 값도 False로 바꿔주고 메소드를 종료 시킨다. 큐가 비어 있는 경우엔 값을 더이상 가져올 수 없다는 문장을 출력해주고 메소드를 종료 시킨다.

🛠 display(self)

def display(self):
    if self.front < self.rear:
        str = self.items[self.front:self.rear]
    else:
        str = self.items[self.front:QSIZE] + self.items[0:self.rear]

    if not self.is_Empty():
        str = ''.join(str)
        print("QUEUE =", str, "(%d)" % len(str))
    else:
        print("QUEUE = (0)")

rear의 위치가 front보다 앞에 있을 경우, front부터 rear까지 해당하는 문자들을 가져와서 str리스트에 담아준다. 아닐 경우엔 front부터 큐의 끝까지 해당하는 문자들과, 큐의 시작점부터 rear까지 해당하는 문자들을 가져와 str리스트에 담아준다.

이렇게 케이스가 나뉘는 이유는, 해당 큐가 원형이기 때문이다. 원형 큐는 큐를 운영하다 보면, 즉 큐에 요소를 삽입하거나 빼내는 과정에서 rear의 위치가 front의 위치보다 앞에 오는 경우가 발생 할 수도 있기 때문이다.

큐가 비어 있지 않은 경우엔 (not self.is_Empty( )), str에 들어있는 문자들을 합쳐서 하나의 문자열로 변환한 뒤, 해당 문자열과 문자열의 길이를 출력해준다. 큐가 비어 있을 경우엔 "QUEUE = (0)"을 출력해준다.

📌 실행결과

📌 전체코드

QSIZE = 10

class Queue:
    def __init__(self):
        self.front = 0
        self.rear = 0
        self.flag = False
        self.items = [None] * QSIZE

    def is_Empty(self):
        return not self.flag

    def is_Full(self):
        if self.flag:
            return self.front == self.rear % QSIZE
        else:
            return False

    def clear(self):
        self.front = self.rear
        self.flag = False

    def push_Queue(self, item):
        for i in range(len(item)):
            if not self.is_Full():
                self.items[self.rear] = item[i]
                self.rear = (self.rear + 1) % QSIZE
                print("(SYSTEM) ADDQUEUE(%s)" % item[i], "F=%d R=%d" % (self.front, self.rear))
                self.flag = True

    def pop_Queue(self, n):
        for i in range(n):
            if not self.is_Empty():
                pop = self.items[self.front]
                self.front = (self.front+1) % QSIZE
                print("DELETEQUEUE() = %s," % pop, "F=%d R=%d" % (self.front, self.rear))
                if self.flag and self.front == self.rear:
                    self.flag = False
            else:
                print("DELETEQUEUE() FAIL.QueueEmpty")

    def peek(self):
        if not self.is_Empty():
            return self.items[self.front % QSIZE]

    def display(self):
        if self.front < self.rear:
            str = self.items[self.front:self.rear]
        else:
            str = self.items[self.front:QSIZE] + self.items[0:self.rear]

        if not self.is_Empty():
            str = ''.join(str)
            print("QUEUE =", str, "(%d)" % len(str))
        else:
            print("QUEUE = (0)")

q = Queue()

print("시스템이 시작됩니다.")
while True:
    enter = input(">>>")

    if enter == '0':
        q.display()
    elif enter in '123456789':
        enter = int(enter)
        q.pop_Queue(enter)
    else:
        q.push_Queue(enter)

주어진 미로 파일을 이용하여 미로를 탈출하는 프로그램을 작성한다.

⚡️ 조건

• 미로의 탈출구는 스택을 이용하여 탐색하도록 한다.
• 스택을 이용할 때 마다 스택에서 어떤 정보를 PUSH하고 POP 하는지 화면에 표시하도록 한다.
• 길은 여러개가 존재 할 수 있는데, 발견한 모든 길을 화면에 표시한다.
• 추가로 길찾기에 앞서 미로를 어떻게 저장할 것인지 부터 생각한다.

그럼 이제 내가 작성한 프로그램에 대해 설명해보겠다.

📌 알고리즘

1. 미로 저장 방식

미로의 벽을 구성하는 요소들(‘+’, ‘|’, ‘-‘)은 그대로 놔두고 길에 해당하는 부분, 즉 공백 부분만 ‘0’으로 변환하여 리스트 형태로 저장하였다. 리스트 형태로 저장한 이유는 경로의 각 점들을 하나의 좌표로 취급하여 좀 더 직관적인 사고가 가능하게 하기 위함이다.

2. 어떻게 출구까지 찾아 갈 것인가?

1) 우선 이동시의 우선순위를 부여하였다 : '아래 -> 오른쪽 -> 위 -> 왼쪽' 순으로 2) 우선순위에 맞춰 시작지점에서 출발하여 ‘0’으로 표시된 지점을 따라 이동한다. 이때 내가 지난 길은 값을 ‘1’로 바꿔준다. (내가 이미 지난 길임을 표시해주기 위해) 3) 그러다 갈림길을 만나면 이를 ‘2’로 표시해주고 여기서도 마찬가지로 우선순위에 따라 이동할 방향을 결정한다. 이때 해당 지점의 좌표와 해당 지점에서의 이동 방향(ex. D(하), R(우) U(상) L(좌))을 스택에 push해준다. 4) 갈림길에서 내가 선택한 길이 막다른 길에 다다를 경우 그곳에서 가장 가까운 갈림길의 좌표, 즉 스택의 top을 pop하여 해당 지점까지 되돌아간다. 5) 갈림길로 되돌아온 후 이전에 이동했던 방향이 아닌 다른 방향으로 다시 탐색을 시작한다. 그리고 이럴 경우 갈림길의 두 방향을 모두 탐색하게 된 것이므로 이 또한 갈림길의 좌표와 함께 스택에 다시 push해준다. (예를 들어 갈림길에서 처음엔 아래쪽으로 이동했는데 이번엔 오른쪽으로 이동할 경우엔 ‘DR’과 같이 표기해준다.) 6) 1~5의 과정을 반복하며 출구가 나올 때 까지 미로를 탐색한다.

3. 출구에 도착하였을 때

1) 우선 첫번째 경로를 찾았으므로 경로의 개수를 나타내는 변수 path에 +1을 해준다. 2) 그리고 첫번째 경로가 표시된 미로를 출력하여 보여준다. 3) 그후 스택이 완전히 빌 때까지 스택의 요소들, 즉 갈림길들을 차례로 pop한다. 그리고 해당 지점들로 이동해가며 시작점으로 되돌아간다.

4. 시작점으로 되돌아왔을 때

시작점이 갈림길일 경우, 처음에 이동했던 방향과 다른 방향으로 이동하여 미로를 다시 탐색하며 새로운 경로를 찾는다. 시작점이 아닐 경우엔, 미로를 모두 탐색한 것이므로 프로그램을 종료 시킨다.

5. 전체 프로그램을 종료하는 방식

만약 시작점이 갈림길이라면, 스택이 두 번째로 비었을 때(empty상태가 되는 경우가 두 번 발생하였을 때) 프로그램을 종료하도록 한다. 갈림길이 아닐 경우엔 스택이 첫번째로 비었을 때(empty상태가 되는 경우가 한 번 발생하였을때) 프로그램을 종료하도록 한다.

📌 Code 설명

🛠 move_D( ), move_R( ), move_U( ), move_L( )

# 아래로 움직이게 해주는 함수
def move_D(i, j):
    # 갈림길(D, R)
    if maze[i + 1][j + 1] == '0' and maze[i + 2][j] == '0':
        # 갈림길은 '2'로 마크하고
        maze[i + 1][j] = '2'
        print("PUSH(%d, %d, D)" % (i + 1, j))
        # 스택에 push 해준 후
        st.push([[i + 1, j], 'D'])
        # 다음 좌표로 이동한다
        i += 1
    # 갈림길(D, L)
    elif maze[i + 1][j - 1] == '0' and maze[i + 2][j] == '0':
        maze[i + 1][j] = '2'
        print("PUSH(%d, %d, D)" % (i + 1, j))
        st.push([[i + 1, j], 'D'])
        i += 1
    # 갈림길(R, L)
    elif maze[i + 1][j - 1] == '0' and maze[i + 1][j + 1] == '0':
        maze[i + 1][j] = '2'
        print("PUSH(%d, %d, R)" % (i + 1, j))
        st.push([[i + 1, j], 'R'])
        i += 1
    # 갈림길이 아닐때
    else:
        maze[i + 1][j] = '1'
        i += 1
    return i, j

각각 현재 위치를 기준으로 아래, 오른쪽, 위, 왼쪽으로 이동하게 해주는 함수이다. 이때 내가 지나온 부분은 값을 ‘0’에서 ‘1’로 바꿔준다. 그리고 갈림길의 경우엔 ‘2’로 바꿔주고 해당 지점의 좌표와 이동 방향을 스택에 push해주고 그 내역을 출력하여 보여준다. (ex. 갈림길의 좌표가 (14, 6)이고 갈림길에서의 이동 방향은 아래일 경우, [ [14, 6], ‘D’]를 스택에 push해준다.)

🛠 return_to_Fork( ):

# 막다른 길에서 갈림길까지 돌아가는 함수
def return_to_Fork(i, j):
    # 가장 최근에 거쳐왔던 갈림길을 스택으로부터 pop
    fork = st.pop()
    print("POP(%d, %d, %s)" % (fork[0][0], fork[0][1], fork[1]))
    x = fork[0][0]
    y = fork[0][1]
    # 갈림길에 닿을 때 까지 지나왔던 경로를 지워주며 이동
    while not (i == x and j == y):
        # 1. 아래로 이동
        if maze[i + 1][j] == '1' or maze[i + 1][j] == '2':
            maze[i][j] = '0'
            i += 1
        # 2. 오른쪽으로 이동
        elif maze[i][j + 1] == '1' or maze[i][j + 1] == '2':
            maze[i][j] = '0'
            j += 1
        # 3. 위로 이동
        elif maze[i - 1][j] == '1' or maze[i - 1][j] == '2':
            maze[i][j] = '0'
            i -= 1
        # 1. 왼쪽으로 이동
        elif maze[i][j - 1] == '1' or maze[i][j - 1] == '2':
            maze[i][j] = '0'
            j -= 1
    return i, j, fork

미로를 탐색하는 과정에서 막다른 길에 다다르거나 출구에 도착하였을 때, 해당 지점에서 가장 가까운 갈림길의 정보(좌표)를 스택으로부터 꺼내어 해당 지점으로 되돌아가게 해주는 함수이다. 이때 내가 지나왔던 경로는 다시 ‘0’으로 초기화 시켜준다.

📌 실행결과

📌 전체코드

class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)

    def pop(self):
        try:
            return self.items.pop()
        except IndexError:
            print("Stack is empty")

    def top(self):
        try:
            return self.items[-1]
        except IndexError:
            print("Stack is empty")

    def isEmpty(self):
        return len(self.items) == 0

f = open('maze2.txt', 'r')
maze = []                       # 미로의 정보를 담을 리스트
line = f.readline().strip()     # 첫 줄 생략

# 미로 정보 저장
while True:
    line = f.readline().strip()                 # 파일의 정보를 한 줄씩 가져 온다
    if line == '': break
    str = line.replace(' ', '0', len(line))     # ' '는 '0'으로
    maze.append(list(str))                      # 변경하여 미로의 정보를 저장

f.close()

# 미로를 출력해주는 함수
def print_Maze(maze):
    for k in maze:
        temp1 = ''.join(k).replace('0', ' ', len(k))
        temp2 = temp1.replace('1', '*', len(k))
        temp3 = temp2.replace('2', '*', len(k))
        print(temp3)

print_Maze(maze)

# 아래로 움직이게 해주는 함수
def move_D(i, j):
    # 갈림길(D, R)
    if maze[i + 1][j + 1] == '0' and maze[i + 2][j] == '0':
        # 갈림길은 '2'로 마크하고
        maze[i + 1][j] = '2'
        print("PUSH(%d, %d, D)" % (i + 1, j))
        # 스택에 push 해준 후
        st.push([[i + 1, j], 'D'])
        # 다음 좌표로 이동한다
        i += 1
    # 갈림길(D, L)
    elif maze[i + 1][j - 1] == '0' and maze[i + 2][j] == '0':
        maze[i + 1][j] = '2'
        print("PUSH(%d, %d, D)" % (i + 1, j))
        st.push([[i + 1, j], 'D'])
        i += 1
    # 갈림길(R, L)
    elif maze[i + 1][j - 1] == '0' and maze[i + 1][j + 1] == '0':
        maze[i + 1][j] = '2'
        print("PUSH(%d, %d, R)" % (i + 1, j))
        st.push([[i + 1, j], 'R'])
        i += 1
    # 갈림길이 아닐때
    else:
        maze[i + 1][j] = '1'
        i += 1
    return i, j
# 오른쪽으로 움직이게 해주는 함수
def move_R(i, j):
    # 갈림길(D, R)
    if maze[i + 1][j + 1] == '0' and maze[i][j + 2] == '0':
        maze[i][j + 1] = '2'
        st.push([[i, j + 1], 'D'])
        print("PUSH(%d, %d, D)" % (i, j + 1))
        j += 1
    # 갈림길(U, R)
    elif maze[i - 1][j + 1] == '0' and maze[i][j + 2] == '0':
        maze[i][j + 1] = '2'
        st.push([[i, j + 1], 'R'])
        print("PUSH(%d, %d, R)" % (i, j + 1))
        j += 1
    # 갈림길(U, D)
    elif maze[i + 1][j + 1] == '0' and maze[i - 1][j + 1] == '0':
        maze[i][j + 1] = '2'
        st.push([[i, j + 1], 'D'])
        print("PUSH(%d, %d, D)" % (i, j + 1))
        j += 1
    # 갈림길이 아닐때
    else:
        maze[i][j + 1] = '1'
        j += 1
    return i, j
# 위로 움직이게 해주는 함수
def move_U(i, j):
    # 갈림길(U, R)
    if maze[i - 1][j + 1] == '0' and maze[i - 2][j] == '0':
        maze[i - 1][j] = '2'
        st.push([[i - 1, j], 'R'])
        print("PUSH(%d, %d, R)" % (i - 1, j))
        i -= 1
    # 갈림길(U, L)
    elif maze[i - 1][j - 1] == '0' and maze[i - 2][j] == '0':
        maze[i - 1][j] = '2'
        st.push([[i - 1, j], 'U'])
        print("PUSH(%d, %d, U)" % (i - 1, j))
        i -= 1
    # 갈림길(R, L)
    elif maze[i - 1][j - 1] == '0' and maze[i - 1][j + 1] == '0':
        maze[i - 1][j] = '2'
        st.push([[i - 1, j], 'R'])
        print("PUSH(%d, %d, R)" % (i - 1, j))
        i -= 1
    # 갈림길이 아닐때
    else:
        maze[i - 1][j] = '1'
        i -= 1
    return i, j
# 왼쪽으로 움직이게 해주는 함수
def move_L(i, j):
    # 갈림길(D, L)
    if maze[i + 1][j - 1] == '0' and maze[i][j - 2] == '0':
        maze[i][j - 1] = '2'
        st.push([[i, j - 1], 'D'])
        print("PUSH(%d, %d, D)" % (i, j - 1))
        j -= 1
    # 갈림길(U, L)
    elif maze[i - 1][j - 1] == '0' and maze[i][j - 2] == '0':
        maze[i][j - 1] = '2'
        st.push([[i, j - 1], 'U'])
        print("PUSH(%d, %d, U)" % (i, j - 1))
        j -= 1
    # 갈림길(U, D)
    elif maze[i - 1][j - 1] == '0' and maze[i + 1][j - 1] == '0':
        maze[i][j - 1] = '2'
        st.push([[i, j - 1], 'D'])
        print("PUSH(%d, %d, D)" % (i, j - 1))
        j -= 1
    # 갈림길이 아닐때
    else:
        maze[i][j - 1] = '1'
        j -= 1
    return i, j

# 막다른 길에서 갈림길까지 돌아가는 함수
def return_to_Fork(i, j):
    # 가장 최근에 거쳐왔던 갈림길을 스택으로부터 pop
    fork = st.pop()
    print("POP(%d, %d, %s)" % (fork[0][0], fork[0][1], fork[1]))
    x = fork[0][0]
    y = fork[0][1]
    # 갈림길에 닿을 때 까지 지나왔던 경로를 지워주며 이동
    while not (i == x and j == y):
        # 1. 아래로 이동
        if maze[i + 1][j] == '1' or maze[i + 1][j] == '2':
            maze[i][j] = '0'
            i += 1
        # 2. 오른쪽으로 이동
        elif maze[i][j + 1] == '1' or maze[i][j + 1] == '2':
            maze[i][j] = '0'
            j += 1
        # 3. 위로 이동
        elif maze[i - 1][j] == '1' or maze[i - 1][j] == '2':
            maze[i][j] = '0'
            i -= 1
        # 1. 왼쪽으로 이동
        elif maze[i][j - 1] == '1' or maze[i][j - 1] == '2':
            maze[i][j] = '0'
            j -= 1
    return i, j, fork

st = Stack()
maze[1][1] = '2'

path = 0    # 미로를 빠져 나갈 수 있는 경로의 개수
i = 1       # 좌표(행)
j = 1       # 좌표(열)
flag = 0    # 무한 루프를 빠져 나올 때 사용될 flag

# 미로가 갈림길이 아닐 경우 flag에 +1
if (maze[2][1] == '0' and maze[1][2] != '0') or (maze[2][1] != '0' and maze[1][2] == '0'): flag += 1

# 시작점에서 이동할 방향 표시
if maze[2][1] == '0':
    st.push([[1, 1], 'D'])
    print("PUSH(1, 1, D)")
elif maze[1][2] == '0':
    st.push([[1, 1], 'R'])
    print("PUSH(1, 1, R)")

while True:
    # 출구에 도착했을 때
    if i == len(maze)-2 and j == len(maze[0])-2:
        # 경로 개수 1 증가
        path += 1
        print(' ')
        # 경로가 표시된 미로 출력
        print("<Path %d>" % path)
        print_Maze(maze)
        print(' ')
        # 왔던 길을 따라 시작점까지 되돌아간다
        while not st.isEmpty():
            # 갈림길까지 돌아감
            i, j, fork = return_to_Fork(i, j)
        # 처음 시작점에서 아래쪽으로 이동했었다면
        if fork[1] == 'D':
            # 오른쪽으로 이동하여 미로 다시 탐색하기
            if maze[i][j + 1] == '0':
                st.push([[i, j], 'DR'])
                print("PUSH(%d, %d, DR)" % (i, j))
                i, j = move_R(i, j)

    # 이동이 가능할 때
    # 1. 아래로 이동
    elif maze[i+1][j] == '0':
        i, j = move_D(i, j)
    # 2. 오른쪽으로 이동
    elif maze[i][j+1] == '0':
        i, j = move_R(i, j)
    # 3. 위로 이동
    elif maze[i-1][j] == '0':
        i, j = move_U(i, j)
    # 1. 왼쪽으로 이동
    elif maze[i][j-1] == '0':
        i, j = move_L(i, j)

    # 막다른 길일때
    else:
        # 막다른 길 직전의 갈림길로 돌아간다
        i, j, fork = return_to_Fork(i, j)
        # 직전 갈림길에서 아래쪽으로 이동했었다면
        if fork[1] == 'D':
            if maze[i][j + 1] == '0':
                st.push([[i, j], 'DR'])
                print("PUSH(%d, %d, DR)" % (i, j))
                i, j = move_R(i, j)
            elif maze[i - 1][j] == '0':
                st.push([[i, j], 'DU'])
                print("PUSH(%d, %d, DU)" % (i, j))
                i, j = move_U(i, j)
            elif maze[i][j - 1] == '0':
                st.push([[i, j], 'DL'])
                print("PUSH(%d, %d, DL)" % (i, j))
                i, j = move_L(i, j)
        # 직전 갈림길에서 오른쪽으로 이동했었다면
        elif fork[1] == 'R':
            if maze[i+1][j] == '0':
                st.push([[i, j], 'RD'])
                print("PUSH(%d, %d, RD)" % (i, j))
                i, j = move_D(i, j)
            elif maze[i - 1][j] == '0':
                st.push([[i, j], 'RU'])
                print("PUSH(%d, %d, RU)" % (i, j))
                i, j = move_U(i, j)
            elif maze[i][j - 1] == '0':
                st.push([[i, j], 'RL'])
                print("PUSH(%d, %d, RL)" % (i, j))
                i, j = move_L(i, j)
        # 직전 갈림길에서 위쪽으로 이동했었다면
        elif fork[1] == 'U':
            if maze[i+1][j] == '0':
                st.push([[i, j], 'UD'])
                print("PUSH(%d, %d, UD)" % (i, j))
                i, j = move_D(i, j)
            elif maze[i][j+1] == '0':
                st.push([[i, j], 'UR'])
                print("PUSH(%d, %d, UR)" % (i, j))
                i, j = move_R(i, j)
            elif maze[i][j - 1] == '0':
                st.push([[i, j], 'UL'])
                print("PUSH(%d, %d, UL)" % (i, j))
                i, j = move_L(i, j)
        # 직전 갈림길에서 왼쪽으로 이동했었다면
        elif fork[1] == 'L':
            if maze[i+1][j] == '0':
                st.push([[i, j], 'LD'])
                print("PUSH(%d, %d, LD)" % (i, j))
                i, j = move_D(i, j)
            elif maze[i][j+1] == '0':
                st.push([[i, j], 'LR'])
                print("PUSH(%d, %d, LR)" % (i, j))
                i, j = move_R(i, j)
            elif maze[i - 1][j] == '0':
                st.push([[i, j], 'LU'])
                print("PUSH(%d, %d, LU)" % (i, j))
                i, j = move_U(i, j)

    # 스택이 비게 될 경우 flag에 +1을 해준다
    if st.isEmpty(): flag += 1
    # flag가 2가 될 경우, 프로그램을 종료 시킨다
    if flag == 2: break

print(' ')
print("경로의 수 : %d" %path)

계산식을 입력하면 그 결과 값을 돌려주는 프로그램을 작성한다. 또한 완성된 프로그램은 다음의 조건들을 만족시켜야 한다.

⚡️ 조건

• 사용되는 연산자는 + - * / ( ) 이다.
• 입력에 사용되는 수는 실수이다.
• 수식에서 괄호는 최대 1회만 사용한다. 또한 겹쳐진 괄호는 쓰지 않는다.
• 잘못된 수식이 입력된다면 어느 위치에 문제가 있는지 알려준다.

그럼 이제 내가 작성한 프로그램에 대해 설명해보겠다.

우선 프로그램의 전체 프로세스는 다음과 같다.

1) 입력 받은 수식의 오류 탐색 2) (오류가 발견되지 않았다면) 수식의 피연산자 식별 3) 입력 받은 수식(infix)을 후위 표기법(postfix)으로 변경 4) 후위 표기법으로 변경된 수식의 계산 결과값 도출

📌 어떤 자료구조를 사용할 것인가?

해당 프로그램을 작성하기 위해 스택(Stack)을 활용하였다.

⚡️ 활용방안

주어진 수식을 왼쪽에서 오른쪽으로 스캔하며, 피연산자는 스택에 저장하고, 연산자이면 필요한 수만큼의 피연산자를 스택에서 꺼내 연산을 실행하고, 연산의 결과를 다시 스택에 저장하는 방식으로 계산기가 실행되도록 프로그램을 작성하였다.

🛠 Stack( )

class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)

    def pop(self):
        try:
            return self.items.pop()
        except IndexError:
            print("Stack is empty")

    def top(self):
        try:
            return self.items[-1]
        except IndexError:
            print("Stack is empty")

    def __len__(self):
        return len(self.items)

    def isEmpty(self):
        return self.__len__() == 0

프로그램 내에서 사용한 스택의 구조이다.

📌 프로세스를 실행하기 위한 함수들

🛠 search_Error( )

def search_Error(expr):
    possible = list('0123456789.()+-*/')            # 수식에 입력 가능한 문자들의 리스트
    integers = list('0123456789')                   # 0~9까지의 정수들의 리스트
    operators = list('+-*/')                        # 수식에 사용될 연산자들의 리스트
    s = Stack()

    for i in range(len(expr)):
        if expr[i] not in possible:                 # 입력 가능한 문자가 아닐 경우 해당 위치 반환
            return i
        elif i == 0 and expr[i] in operators:       # 연산자가 수식의 가장 앞에 위치할 경우 해당 위치 반환 (ex. *123+4...)
            return i
        elif expr[i] in operators:
            if i + 1 == len(expr):                  # 연산자 뒤에 피연산자가 오지 않고 수식이 끝날 경우 위치 반환 (ex. 1+2+)
                return i
            else:                                   # 연속해서 연산자가 위치할 경우 해당 위치 반환 (ex. 1+*2...)
                if expr[i + 1] in operators:
                    return i + 1
        elif expr[i] == '(':                        # 수식에서 '('가 발견되었을 때
            if expr[i - 1] in integers and i != 0:  # 여는 괄호('(') 앞에 정수가 올 경우 해당 위치 반환
                return i
            else:
                if s.isEmpty():                     # 스택에 이미 값이 들어있으면 해당 위치 반환
                    s.push('(')                     # 스택이 비어있으면 push
                else:
                    return i
        elif expr[i] == ')':                        # 수식에서 ')'가 발견되었을 때
            if s.isEmpty():                         # 스택이 비어있으면
                return i                            # 해당 위치 반환
            elif expr[i + 1] in integers and i != len(expr) - 1:
                return i + 1                        # 닫는 괄호(')') 뒤에 정수가 올 경우 해당 위치 반환
            else:
                s.push(')')                         # 스택이 비어있지 않다면 해당 값을 스택에 push

    if not s.isEmpty():                             # 수식에 '('는 존재 하지만 ')'는 존재하지 않는 경우
        if s.pop() == '(':
            return len(expr)                        # 수식의 마지막 위치를 반환

입력 받은 수식(expr)에서 오류가 발생한 부분을 찾아 낼 함수이다. 우선 수식에 입력 가능한 문자들(0123456789.()+-/)의 리스트 *possible 0~9까지의 정수들의 리스트 integers 수식에 사용될 연산자들의 리스트 operators**를 선언해준다. 그 후 오류가 발생하는 case를 나눠 오류를 찾아낸다. 케이스는 다음과 같다.

⚡️ case

1) 입력 가능한 문자가 아닐 경우 2) 연산자가 수식의 가장 앞에 위치할 경우 (ex. 123+4...) 3) 연산자 뒤에 피연산자가 오지 않고 수식이 끝날 경우 (ex. 1+2+) 4) 연속해서 연산자가 위치할 경우 (ex. 1+2...) 5) 수식에서 여는 괄호 앞에 정수가 올 경우, 또는 스택에 이미 값이 들어있을 경우 (괄호는 최대 1번만 사용 가능한데, 이 경우는 1번이상 사용 되었다는 의미이므로) 6) 수식에서 닫는 괄호 뒤에 정수가 올 경우, 또는 스택이 비어있을 경우 (닫는 괄호를 쓸려면 여는 괄호가 이미 쓰여 있어야 하는데 이 경우는 그렇지 않다는 의미이므로) 7) 수식에 여는 괄호는 존재하지만, 닫는 괄호는 존재하지 않는 경우

1~7까지 각각의 경우에 해당하는 위치, 즉 오류가 발생한 위치를 반환한다.

🛠 recognize_Operands( )

def recognize_Operands(infix):
    numbers = list('0123456789.')                       # 실수 계산기 이므로, 모든 피연산자는 0~9인 정수와 .으로 이루어진다
    recognized = []                                      # 수식의 숫자들을 피연산자로 인식하여 다시 담아 줄 리스트

    i = 0
    while i < len(infix):
        j = 1
        if infix[i] in numbers:                         # 연산자가 아닐 경우, 즉 숫자 또는 .일 경우
            while i + j < len(infix):                   # 해당 요소의 다음 요소도 숫자 또는 .인지를 판별하고
                if infix[i + j] in numbers:
                    j += 1
                else:
                    break
            recognized.append(''.join(infix[i:i + j]))   # 이들을 하나로, 즉 하나의 숫자로 인식 할 수 있도록 묶어준다
            i += j
        else:                                           # 연산자일 경우엔 리스트에 바로 추가해준다
            recognized.append(infix[i])
            i += 1
    return recognized

사용자가 입력한 수식에서 피연산자(실수)를 인식하기 위한 함수이다. 우선 해당 프로그램은 실수 계산기 이므로, 모든 피연산자는 0~9사이의 정수와 .만으로 이루어진다. 따라서 이를 인식하기 위한 리스트 numbers와 피연산자로 인식된 숫자들을 담아 줄 리스트 recognized를 선언해준다. ( ex. recognized = [12.9 , 30.1, 17.89, 48.66] )

다름으로 입력 된 중위 표기식(infix)의 앞에서부터 돌며 연산자가 발견될 경우, 리스트에 바로 추가해준다. 숫자 또는 .이 발견될 경우에는 해당 요소의 다음 요소도 숫자 또는 .인지를 판별한다. 맞을 경우 연산자가 나올 때 까지 위의 과정을 반복하며 이들이 하나의 숫자(피연산자)로 인식될 수 있도록 묶어주고, 그 상태로 recognized에 추가해준다. 위의 작업들이 모두 마무리 되고 나면 recognized를 반환해준다.

🛠 in2post( )

def in2post(infix):
    s = Stack()                                             # 스택 생성
    postfix = []                                            # 후위 표기법으로 바뀐 수식을 담아 줄 리스트
    for i in infix:
        if i == '(':                                        # 여는 괄호('(')일 경우 스택에 바로 push
            s.push(i)
        elif i == ')':                                      # 닫는 괄호(')')일 경우
            while s.top() != '(':                           # '('와 ')'사이의 연산자들을 모두 postfix 리스트에 추가
                postfix.append(s.pop())
            s.pop()                                         # 그리고 stack에 들어있던 '('는 삭제. (후위 표기법은 괄호를 표시하지 않으므로)
        elif i in priority:                                 # '+ - * /'일 경우
            while not s.isEmpty():                          # 스택이 비어 있지 않을 때
                if priority[s.top()] >= priority[i]:        # 스택의 top에 해당하는 연산자의 우선순위가 비교할 연산자의 우선순위보다 크거나 같을 경우
                    postfix.append(s.pop())                 # 해당 연산자(top)를 postfix 리스트에 추가한다
                else:
                    break
            s.push(i)                                       # 스택이 비어있을 경우엔 해당 연산자를 스택에 바로 push
        else:                                               # 피연산자(숫자)의 경우 리스트에 바로 추가
           postfix.append(i)
    while not s.isEmpty():                                  # '('보다 밑 스택에 남아있던 연산자들을
        postfix.append(s.pop())                             # 모두 리스트에 추가해준다

    return postfix                                          # 변환된 후위 표기식을 반환한다

중위 표기법으로 표기된 수식을 후위 표기법으로 바꿔줄 함수이다. 우선 하나의 스택과 후위 표기법으로 변환된 수식을 담아 줄 리스트 postfix를 선언해준다.

다음으로 입력 된 중위 표기식(infix)의 앞에서부터 돌며

1) 숫자(피연산자)가 발견될 경우 postfix에 바로 추가해준다. 2) 연산자(+ - * /)가 발견될 경우 스택이 비어 있으면 해당 연산자를 바로 스택에 push해준다 스택이 비어있지 않다면 해당 연산자와 스택의 top에 해당하는 연산자의 우선순위를 비교하고, 후자의 우선순위가 더 높을 경우 전자를 postfix에 추가해준다. 3) 여는 괄호가 발견 될 경우 스택에 바로 push해준다. 4) 닫는 괄호가 발견 될 경우 여는 괄호와 닫는 괄호 사이에 존재하는 연산자들을 모두 postfix에 추가해준다. 그후 postfix에 남아있던 여는 괄호는 삭제해준다.(후위 표기법은 괄호를 따로 표기하지 않기 때문) 5) 마지막으로 여는 괄호보다 밑 스택에 남아있던 연산자들을 차례로 postfix에 추가해주고, postfix를 반환해준다.

이때 연산자의 우선순위는 다음과 같이 설정해준다.

priority = {'(': 1, ')': 1, '+': 2, '-': 2, '*': 3, '/': 3}   # 연사자의 우선 순위(숫자가 클수록 더 높은 우선 순위)

🛠 post_Cal( )

def post_Cal(postfix):
    s = Stack()

    for i in postfix:
        if i in priority:                                   # 연산자일 경우
            num1 = s.pop()                                  # 스택에 쌓여 있던 두 피연산자(숫자)를 꺼내
            num2 = s.pop()
            if i == '+':                                    # 덧셈(+)
                s.push(num2 + num1)
            elif i == '-':                                  # 뺄셈(-)
                s.push(num2 - num1)
            elif i == '/':                                  # 나눗셈(/)
                s.push(num2 / num1)
            elif i == '*':                                  # 곱셈(*)
                s.push(num2 * num1)                         # 두 피연산자에 대해 각 연산자에 해당하는 연산을 수행한 값을 스택에 push해준다

        else:                                               # 숫자일 경우
            s.push(float(i))                                # 해당 숫자를 float 자료형으로 스택에 push(실수 계산기이므로)

    return s.pop()                                          # 계산된 값을 반환한다

후위 표기법으로 변환된 수식을 계산하여 결과값을 반환하게 될 함수이다. 우선 후위 표기식(postfix)의 앞에서부터 돌며 숫자가 발견되면 해당 숫자를 float자료형으로 스택에 push해준다. 해당 프로그램은 '실수 계산기' 이기 때문이다. 연산자가 발견되면 스택에 쌓여 있던 두 피연산자를 꺼내고, 두 피연산자에 대해 각 연산자에 해당하는 연산(+ - * /)을 수행하고 그 결과값을 다시 스택에 push해준다. 수식의 모든 요소에 대해 위와 같은 과정을 반복하고 최종 결과값을 스택에서 꺼내 반환해준다.

📌 실행결과

📌 전체코드

class Stack:
    def __init__(self):
        self.items = []

    def push(self, val):
        self.items.append(val)

    def pop(self):
        try:
            return self.items.pop()
        except IndexError:
            print("Stack is empty")

    def top(self):
        try:
            return self.items[-1]
        except IndexError:
            print("Stack is empty")

    def __len__(self):
        return len(self.items)

    def isEmpty(self):
        return self.__len__() == 0

# 입력 받은 수식의 오류를 찾아내는 함수
def search_Error(expr):
    possible = list('0123456789.()+-*/')            # 수식에 입력 가능한 문자들의 리스트
    integers = list('0123456789')                   # 0~9까지의 정수들의 리스트
    operators = list('+-*/')                        # 수식에 사용될 연산자들의 리스트
    s = Stack()

    for i in range(len(expr)):
        if expr[i] not in possible:                 # 입력 가능한 문자가 아닐 경우 해당 위치 반환
            return i
        elif i == 0 and expr[i] in operators:       # 연산자가 수식의 가장 앞에 위치할 경우 해당 위치 반환 (ex. *123+4...)
            return i
        elif expr[i] in operators:
            if i + 1 == len(expr):                  # 연산자 뒤에 피연산자가 오지 않고 수식이 끝날 경우 위치 반환 (ex. 1+2+)
                return i
            else:                                   # 연속해서 연산자가 위치할 경우 해당 위치 반환 (ex. 1+*2...)
                if expr[i + 1] in operators:
                    return i + 1
        elif expr[i] == '(':                        # 수식에서 '('가 발견되었을 때
            if expr[i - 1] in integers and i != 0:  # 여는 괄호('(') 앞에 정수가 올 경우 해당 위치 반환
                return i
            else:
                if s.isEmpty():                     # 스택에 이미 값이 들어있으면 해당 위치 반환
                    s.push('(')                     # 스택이 비어있으면 push
                else:
                    return i
        elif expr[i] == ')':                        # 수식에서 ')'가 발견되었을 때
            if s.isEmpty():                         # 스택이 비어있으면
                return i                            # 해당 위치 반환
            elif expr[i + 1] in integers and i != len(expr) - 1:
                return i + 1                        # 닫는 괄호(')') 뒤에 정수가 올 경우 해당 위치 반환
            else:
                s.push(')')                         # 스택이 비어있지 않다면 해당 값을 스택에 push

    if not s.isEmpty():                             # 수식에 '('는 존재 하지만 ')'는 존재하지 않는 경우
        if s.pop() == '(':
            return len(expr)                        # 수식의 마지막 위치를 반환

# 사용자가 입력한 수식에서 피연산자를 인식하기 위한 함수
def recognize_Operands(infix):
    numbers = list('0123456789.')                       # 실수 계산기 이므로, 모든 피연산자는 0~9인 정수와 .으로 이루어진다
    recognized = []                                      # 수식의 숫자들을 피연산자로 인식하여 다시 담아 줄 리스트

    i = 0
    while i < len(infix):
        j = 1
        if infix[i] in numbers:                         # 연산자가 아닐 경우, 즉 숫자 또는 .일 경우
            while i + j < len(infix):                   # 해당 요소의 다음 요소도 숫자 또는 .인지를 판별하고
                if infix[i + j] in numbers:
                    j += 1
                else:
                    break
            recognized.append(''.join(infix[i:i + j]))   # 이들을 하나로, 즉 하나의 숫자로 인식 할 수 있도록 묶어준다
            i += j
        else:                                           # 연산자일 경우엔 리스트에 바로 추가해준다
            recognized.append(infix[i])
            i += 1
    return recognized

priority = {'(': 1, ')': 1, '+': 2, '-': 2, '*': 3, '/': 3}   # 연사자의 우선 순위(숫자가 클수록 더 높은 우선 순위)

# 중위 표기법 수식을 후위 표기법으로 바꿔주는 함수
def in2post(infix):
    s = Stack()                                             # 스택 생성
    postfix = []                                            # 후위 표기법으로 바뀐 수식을 담아 줄 리스트
    for i in infix:
        if i == '(':                                        # 여는 괄호('(')일 경우 스택에 바로 push
            s.push(i)
        elif i == ')':                                      # 닫는 괄호(')')일 경우
            while s.top() != '(':                           # '('와 ')'사이의 연산자들을 모두 postfix 리스트에 추가
                postfix.append(s.pop())
            s.pop()                                         # 그리고 stack에 들어있던 '('는 삭제. (후위 표기법은 괄호를 표시하지 않으므로)
        elif i in priority:                                 # '+ - * /'일 경우
            while not s.isEmpty():                          # 스택이 비어 있지 않을 때
                if priority[s.top()] >= priority[i]:        # 스택의 top에 해당하는 연산자의 우선순위가 비교할 연산자의 우선순위보다 크거나 같을 경우
                    postfix.append(s.pop())                 # 해당 연산자(top)를 postfix 리스트에 추가한다
                else:
                    break
            s.push(i)                                       # 스택이 비어있을 경우엔 해당 연산자를 스택에 바로 push
        else:                                               # 피연산자(숫자)의 경우 리스트에 바로 추가
           postfix.append(i)
    while not s.isEmpty():                                  # '('보다 밑 스택에 남아있던 연산자들을
        postfix.append(s.pop())                             # 모두 리스트에 추가해준다

    return postfix                                          # 변환된 후위 표기식을 반환한다

# 후위 표기법으로 변환된 수식을 계산해주는 함수
def post_Cal(postfix):
    s = Stack()

    for i in postfix:
        if i in priority:                                   # 연산자일 경우
            num1 = s.pop()                                  # 스택에 쌓여 있던 두 피연산자(숫자)를 꺼내
            num2 = s.pop()
            if i == '+':                                    # 덧셈(+)
                s.push(num2 + num1)
            elif i == '-':                                  # 뺄셈(-)
                s.push(num2 - num1)
            elif i == '/':                                  # 나눗셈(/)
                s.push(num2 / num1)
            elif i == '*':                                  # 곱셈(*)
                s.push(num2 * num1)                         # 두 피연산자에 대해 각 연산자에 해당하는 연산을 수행한 값을 스택에 push해준다

        else:                                               # 숫자일 경우
            s.push(float(i))                                # 해당 숫자를 float 자료형으로 스택에 push(실수 계산기이므로)

    return s.pop()                                          # 계산된 값을 반환한다

while True:
    expr = list(input("수식을 입력하세요 : "))                  # 수식을 입력 받음

    if search_Error(expr) != None:                          # 수식의 오류를 찾는다
        print(' ' * 15, ' ' * search_Error(expr), end='')
        print('^이 위치에 오류가 발견되었습니다.')
        continue

    infix = recognize_Operands(expr)                        # 오류가 없을 경우 수식의 연산자를 인식하여 정리한다
    postfix = in2post(infix)                                # 수식을 후위 표기법으로 바꾸어준다
    print('=', post_Cal(postfix))                           # 후위 표기법으로 바뀐 수식을 계산하고, 결과값을 출력한다

위의 그림은 일반적인 다항식의 형태이다. 위와 같은 다항식을 배열 혹은 리스트에 저장하는 방식은 크게 두가지가 있다.

1) 다항식의 모든 항을 저장하는 방식

예를 들어 다음과 같은 다항식이 주어졌을때, 이를 1번 방식으로 배열(리스트)에 저장한 형태는 다음과 같다.

1번 방식의 장단점은 다음과 같다.

• 장점: 다항식의 각종 연산이 간단하다.
• 단점: 항의 계수가 0인 항이 많으면 공간의 낭비가 크다.

위의 다항식을 2번 방식으로 배열(리스트)에 저장한 형태는 다음과 같다.

2번 방식의 장단점은 다음과 같다.

• 장점: 메모리 공간을 효율적으로 활용할 수 있다.
• 단점: 다항식의 각종 연산이 복잡하다.

위의 두가지 방식 각각에 대하여 다음과 같은 프로그램을 작성한다.

⚡️ 프로그램의구성

• 입력된 데이터로부터 다항식을 구성하여 화면에 표시한다.
• 입력된 2개의 다항식의 합과 곱을 화면에 표시한다.
• 4개의 다항식 중 하나를 선택하여 𝒙에 값을 대입하면 그에 대한 결과 값을 표시한다.
• 입력되는 다항식의 차수는 최대 5를 넘지않는다.
  

1. 다항식의 모든 항을 배열에 저장하는 방식

🛠 print_poly1( )

def print_poly1(self):
    for i in range(self.degree):
        if i == self.degree - 1:                        # 상수항인지 판별
            if self.coef[i] != 0.0:
                if self.coef[i] >= 0:                   # 상수항의 부호 판별
                    print(" + ", end='')
                else:
                    print(" - ", end='')
                print("%0.2f" % (abs(self.coef[i])))
            else:                                       # 상수항이 0일 경우 0 출력하지 않고 줄바꿈
                print()
        else:
            if self.coef[i] != 0.0:
                if i == 0:
                    print("%0.2f x^%d" % (self.coef[i], self.degree - i - 1), end='')
                else:
                    if self.coef[i] >= 0:
                        print(" + ", end='')
                    else:
                        print(" - ", end='')
                    print("%0.2f x^%d" % (abs(self.coef[i]), self.degree - i - 1), end='')

poly1 형태로 저장된 다항식 값을 사람이 보기 쉬운 다항식 형태로 표시해주는 메소드이다. 최고 차항의 계수가 양수인지 음수인지, 상수항이 0인지 아닌지, 각 항의 계수가 양수인지 음수인지 등을 판단하고, 그에 따라 각 항에 알맞은 부호를 부여한다.

🛠 find_val( )

def find_val(self, x):
    temp_degree = self.degree
    val = 0
    for i in range(self.degree):
        temp = 1
        for j in range(temp_degree - 1):
            temp *= x
        if temp_degree == 1:
            temp = self.coef[i]
        else:
            temp = temp * self.coef[i]
        val += temp
        temp_degree -= 1
    print('결과 값은 %0.1f' %val)

다항식의 x에 값을 대입하여 해를 찾아주는 메소드이다. 최고차항부터 x에 대입한 값을 차수 번 만큼 제곱해주고, 제곱한 값과 해당 차수의 계수를 곱한다. 상수의 경우 차수 곱 없이 계수의 값만 저장해준다. 그렇게 구해진 각 항의 계산값을 val 에 더해준다. 이때 temp_degree 는 현재 항의 해를 찾기 위한 다항식의 index값이다.

🛠 poly1_add( )

def poly1_add(a,b):
    z = []                  # 두 다항식의 덧셈의 결과값을 담아 줄 리스트
    apos = bpos = 0         # 두 다항식의 현재 위치
    degree_a = a.degree     # 다항식 a의 차수(ex. 2차, 3차, 4차 ...)
    degree_b = b.degree     # 다항식 b의 차수

    while (apos < degree_a) or (bpos < degree_b):
        if degree_a > degree_b:
            z.append(a.coef[apos])
            apos += 1
            degree_a -= 1
        elif degree_a == degree_b:              # 두 다항식에서 현재 위치한 항의 차수가 같은 경우
            z.append(a.coef[apos]+b.coef[bpos]) # 두 항의 계수를 더해준다
            apos += 1
            bpos += 1
        else:
            z.append(b.coef[bpos])
            bpos += 1
            degree_b -= 1
    return poly1(z)

두개의 다항식을 매개변수로 받아서 더해주는 함수이다.

🛠 poly1_mul( )

def poly1_mul(a, b):
    x = []                  # a의 최고차항 * b다항식 전체
    degree_a = a.degree
    degree_b = b.degree

    apos = 0
    for i in range(degree_b):
        x.append(a.coef[apos] * b.coef[i])
    for i in range(degree_a - 1):
        x.append(0)

    x = poly1(x)
    degree_a -= 1
    apos += 1

    while(apos < a.degree):
        y = []              # a의 최고차항 이하의 항 * b다항식 전체
        for i in range(degree_b):
            y.append(a.coef[apos] * b.coef[i])
        for i in range(degree_a - 1):
            y.append(0)
        y = poly1(y)

        x = poly1_add(x, y) # a + b
        apos += 1
        degree_a -= 1
    return x

두개의 다항식을 매개변수로 받아서 곱해주는 함수이다. 첫 번째 다항식인 a 의 각항을 두번째 다항식 b 와 곱해주고, 그 결과값들을 poly1_add함수를 통해 모두 더해주는 방식으로 작동한다.

1) a의 최고차항과 b다항식 전체를 곱해준 결과값을 x 리스트에 넣어준다. 2) 이후 순서대로 a의 최고차항 이하의 항들과 b다항식 전체를 곱한 값을 y 리스트에 넣어준다. 3) x와 y를 poly1_add 함수를 통해 더해준다. 4) a의 마지막 항까지 위의 과정을 반복해준다.

🛠 print_val( )

def print_val():
    while True:
        e = list(map(float, input("수식에 값을 넣으세요 ").split(' ')))
        if e[0] == 1:           # 수식1을 선택할 경우
            a.find_val(e[1])    
        elif e[0] == 2:         # 수식2를 선택할 경우
            b.find_val(e[1])    
        elif e[0] == 3:         # 수식3(수식1 + 수식2)을 선택할 경우
            c.find_val(e[1])  
        elif e[0] == 4:         # 수식4(수식1 * 수식2)를 선택할 경우
            d.find_val(e[1])
        else:                   # 범위(1~4)를 벗어난 값이 입력된 경우
            print('잘못된 값을 입력하셨습니다!')

사용자가 선택한 다항식에 값을 대입할 경우 그 결과 값을 출력해주는 함수. 우선 첫번째로 입력 받은 숫자를 통해 몇번째 다항식에 값을 대입할지 판단하는데, 이때 범위(1~4)를 벗어나는 숫자가 입력되면 값을 다시 입력받는다. 두번째로 입력 받은 숫자를 find_val 메소드를 통해 선택한 다항식에 대입하여 그 결과값을 구해준다.

📌 실행결과

📌 전체코드

class poly1():
    def __init__(self, coef):
        self.coef = coef
        self.degree = len(coef)

    def print_poly1(self):
        for i in range(self.degree):
            if i == self.degree - 1:                        # 상수항인지 판별
                if self.coef[i] != 0.0:
                    if self.coef[i] >= 0:                   # 상수항의 부호 판별
                        print(" + ", end='')
                    else:
                        print(" - ", end='')
                    print("%0.2f" % (abs(self.coef[i])))
                else:                                       # 상수항이 0일 경우 0 출력하지 않고 줄바꿈
                    print()
            else:
                if self.coef[i] != 0.0:
                    if i == 0:
                        print("%0.2f x^%d" % (self.coef[i], self.degree - i - 1), end='')
                    else:
                        if self.coef[i] >= 0:
                            print(" + ", end='')
                        else:
                            print(" - ", end='')
                        print("%0.2f x^%d" % (abs(self.coef[i]), self.degree - i - 1), end='')

    def find_val(self, x):
        temp_degree = self.degree
        val = 0
        for i in range(self.degree):
            temp = 1
            for j in range(temp_degree - 1):
                temp *= x
            if temp_degree == 1:
                temp = self.coef[i]
            else:
                temp = temp * self.coef[i]
            val += temp
            temp_degree -= 1
        print('결과 값은 %0.1f' %val)

def poly1_add(a,b):
    z = []                  # 두 다항식의 덧셈의 결과값을 담아 줄 리스트
    apos = bpos = 0         # 두 다항식의 현재 위치
    degree_a = a.degree     # 다항식 a의 차수(ex. 2차, 3차, 4차 ...)
    degree_b = b.degree     # 다항식 b의 차수

    while (apos < degree_a) or (bpos < degree_b):
        if degree_a > degree_b:
            z.append(a.coef[apos])
            apos += 1
            degree_a -= 1
        elif degree_a == degree_b:              # 두 다항식에서 현재 위치한 항의 차수가 같은 경우
            z.append(a.coef[apos]+b.coef[bpos]) # 두 항의 계수를 더해준다
            apos += 1
            bpos += 1
        else:
            z.append(b.coef[bpos])
            bpos += 1
            degree_b -= 1
    return poly1(z)

def poly1_mul(a, b):
    x = []                  # a의 최고차항 * b다항식 전체
    degree_a = a.degree
    degree_b = b.degree

    apos = 0
    for i in range(degree_b):
        x.append(a.coef[apos] * b.coef[i])
    for i in range(degree_a - 1):
        x.append(0)

    x = poly1(x)
    degree_a -= 1
    apos += 1

    while(apos < a.degree):
        y = []              # a의 최고차항 이하의 항 * b다항식 전체
        for i in range(degree_b):
            y.append(a.coef[apos] * b.coef[i])
        for i in range(degree_a - 1):
            y.append(0)
        y = poly1(y)

        x = poly1_add(x, y) # a + b
        apos += 1
        degree_a -= 1
    return x

def print_val():
    while True:
        e = list(map(float, input("수식에 값을 넣으세요 ").split(' ')))
        if e[0] == 1:           # 수식1을 선택할 경우
            a.find_val(e[1])
        elif e[0] == 2:         # 수식2를 선택할 경우
            b.find_val(e[1])
        elif e[0] == 3:         # 수식3(수식1 + 수식2)을 선택할 경우
            c.find_val(e[1])
        elif e[0] == 4:         # 수식4(수식1 * 수식2)를 선택할 경우
            d.find_val(e[1])
        else:                   # 범위(1~4)를 벗어난 값이 입력된 경우
            print('잘못된 값을 입력하셨습니다!')

a = list(map(float, input("수식 1을 입력하세요 : ").split(' ')))
while len(a) > 6:
    a = list(map(float, input("최대 차수를 초과하였습니다. 다시 입력해주세요! : ").split(' ')))
b = list(map(float, input("수식 2를 입력하세요 : ").split(' ')))
while len(b) > 6:
    b = list(map(float, input("최대 차수를 초과하였습니다. 다시 입력해주세요! : ").split(' ')))

a = poly1(a)
b = poly1(b)
c = poly1_add(a, b)
d = poly1_mul(a, b)

print('수식 1은 ', end='')
a.print_poly1()
print('수식 2는 ', end='')
b.print_poly1()
print('수식 1 + 2는 ', end='')
c.print_poly1()
print('수식 1 * 2는 ', end='')
d.print_poly1()

print_val()

2. 다항식 중 계수가 0이 아닌 항만을 배열에 저장하는 방식

🛠 print_poly2( )

def print_poly2(self):
    for i in range(self.degree):
        if i == self.degree - 1:                 # 맨 마지막 항의
            if self.coef_deg[i][0] != 0.0:       # 계수가 0이 아닐 경우
                if self.coef_deg[i][0] >= 0:     # 항의 부호 판별
                    print(" + ", end='')         # 양수일 경우엔 '+'를
                else:
                    print(" - ", end='')         # 음수일 경우엔 '-'를

                if self.coef_deg[i][1] == 0:     # 상수일 경우엔 계수만 출력한다
                    print("%0.2f" % (abs(self.coef_deg[i][0])))
                else:                            # 상수가 아닐 경우엔 "계수 x^차수"형태로 출력한다.
                    print("%0.2f x^%d" % (abs(self.coef_deg[i][0]), self.coef_deg[i][1]))
            else:
                print()                          # 맨 마지막 항이 상수가 아니고 계수가 0일 경우엔 아무것도 출력하지 않는다
        else:
            if self.coef_deg[i][0] != 0.0:       # 계수가 0일경우 아무것도 출력하지 않는다
                if i == 0:                       # 첫 항의 부호를 출력하기 위해 따로 출력
                    print("%0.2f x^%d" % (self.coef_deg[i][0], self.coef_deg[i][1]), end="")
                else:
                    if self.coef_deg[i][0] >= 0:
                        print(" + ", end='')
                    else:
                        print(" - ", end='')
                    print("%0.2f x^%d" % (abs(self.coef_deg[i][0]), self.coef_deg[i][1]), end="")

2차원 리스트로 저장된 다항식을 진짜 다항식 형태로 변환해주는 메소드이다.

1) 우선 다항식의 마지막 항이 상수이고, 그 값이 0인 경우에는 굳이 출력을 하지 않도록 코드를 수정하였다. 2) 또한 마지막 항이 상수는 아니지만 계수가 0일 경우에도 아무것도 출력하지 않도록 수정하였다. 3) 마지막으로 맨 첫번째 항의 계수의 부호도 표시할 수 있도록 코드를 수정하였다.

🛠 find_val( )

def find_val(self, x):
    val = 0                                         # 최종 결과 값을 반영해 줄 변수 val 선언
    for i in range(self.degree):                    # 각 항을 돌며
        temp = 1
        for j in range(int(self.coef_deg[i][1])):   # 각 항의 차수 만큼(횟수)
            temp *= x                               # 입력받은 x의 값을 곱해준다
        if self.coef_deg[i][1] == 0:                # 차수가 0일 경우는 상수이므로
            temp = self.coef_deg[i][0]              # 해당 항의 계수가 곧 temp값이 된다
        else:
            temp = temp * self.coef_deg[i][0]
        val += temp                                 # val에 temp값을 더해준다
    print('결과 값은 %0.2f' %val)

다항식의 x에 값을 대입하여 해를 찾아주는 메소드이다. 우선 최종 결과 값을 담을 변수 val 을 선언하고 0으로 초기화해준다. 그리고 각 항의 계산 결과값을 담을 변수 temp 를 선언하고 1로 초기화해준다. 전체 항을 돌며 각 항마다 각 항의 차수 만큼(횟수) 반복하여 입력 받은 값을 temp에 곱해주고, 그 값에 다시 각 항의 계수를 곱해준다. 이때 차수가 0인 항은 상수이므로 해당 항의 계수가 곧 temp값이 된다. 그렇게 구해진 각 temp값들을 val에 더해주면 최종 계산 결과값이 될 것이다.

🛠 poly2_add( )

def poly2_add(a,b):
    z = []
    apos = bpos = 0
    term_a = a.degree
    term_b = b.degree

    while(apos < term_a) and (bpos < term_b):
        if a.coef_deg[apos][1] > b.coef_deg[bpos][1]:
            z.append([a.coef_deg[apos][0], a.coef_deg[apos][1]])
            apos += 1
        elif a.coef_deg[apos][1] == b.coef_deg[bpos][1]:
            z.append([a.coef_deg[apos][0] + b.coef_deg[bpos][0], a.coef_deg[apos][1]])
            apos += 1
            bpos += 1
        else:
            z.append([b.coef_deg[bpos][0], b.coef_deg[bpos][1]])
            bpos += 1

        if apos >= term_a:
            while bpos < term_b:
                z.append([b.coef_deg[bpos][0], b.coef_deg[bpos][1]])
                bpos += 1
        elif bpos >= term_b:
            while apos < term_a:
                z.append([a.coef_deg[apos][0], a.coef_deg[apos][1]])
                apos += 1
    return poly2(z)

입력 받은 두 다항식을 서로 더하고, 그 결과 값을 반환하는 함수이다.

🛠 poly2_mul( )

def poly2_mul(a, b):
    x = []                                                                                           # 최종 결과 값을 담아 줄 빈 리스트 x 선언
    apos = 0
    for i in range(b.degree):
        x.append([a.coef_deg[apos][0]*b.coef_deg[i][0], a.coef_deg[apos][1] + b.coef_deg[i][1]])     # 각 항의 계수끼리는 곱하고, 차수끼리는 더해준다.
    x = poly2(x)                                                                                     # 위 연산의 결과 값을 x에 담아준다
    apos += 1

    while (apos < a.degree):
        y = []                                                                                       # 중간 결과 값을 담아 줄 빈 리스트 y 선언
        for i in range(b.degree):
            y.append([a.coef_deg[apos][0]*b.coef_deg[i][0], a.coef_deg[apos][1] + b.coef_deg[i][1]]) # 위와 같은 방식의 연산 수행
        y = poly2(y)                                                                                 # 위 연산의 결과 값을 y에 담아준다

        x = poly2_add(x, y)                                                                          # x와 y를 더해준 값을 x에 담아준다
        apos += 1
    return x

우선 최종 결과값을 담게 될 리스트 x 를 선언해준다. 그리고 a 의 첫번째 요소(ex. [1, 2])와 b 전체에 대하여 coef_deg[i][0] , 즉 각 항의 계수에 대해서는 곱셈을, coef_deg[i][1] , 즉 차수에 대해서는 덧셈 연산을 수행하고 그 결과값을 리스트 x에 추가 해준다.

다음으론 while문 안에 중간 결과 값을 반영할 리스트 y 를 선언해준다. a의 두번째 요소부터 위와 같은 방식의 연산을 수행한 결과값을 y에 추가 해주고, 이를 poly2_add( ) 함수를 통해 x와 더해주고 그 결과값을 다시 x에 대입한다. 위와 같은 과정을 a의 마지막 요소까지 반복해서 수행하고, 연산이 모두 끝난 후에는 리스트 x를 반환하도록 한다.

📌 실행결과

📌 전체코드

class poly2():
    def __init__(self, coef):
        self.coef_deg = coef        # 다항식의 각 항의 계수와 차수를 나타내는 변수
        self.degree = len(coef)     # 각 다항식의 항의 개수를 나타낼 변수

    def print_poly2(self):
        for i in range(self.degree):
            if i == self.degree - 1:                 # 맨 마지막 항의
                if self.coef_deg[i][0] != 0.0:       # 계수가 0이 아닐 경우
                    if self.coef_deg[i][0] >= 0:     # 항의 부호 판별
                        print(" + ", end='')         # 양수일 경우엔 '+'를
                    else:
                        print(" - ", end='')         # 음수일 경우엔 '-'를

                    if self.coef_deg[i][1] == 0:     # 상수일 경우엔 계수만 출력한다
                        print("%0.2f" % (abs(self.coef_deg[i][0])))
                    else:                            # 상수가 아닐 경우엔 "계수 x^차수"형태로 출력한다.
                        print("%0.2f x^%d" % (abs(self.coef_deg[i][0]), self.coef_deg[i][1]))
                else:
                    print()                          # 맨 마지막 항이 상수가 아니고 계수가 0일 경우엔 아무것도 출력하지 않는다
            else:
                if self.coef_deg[i][0] != 0.0:       # 계수가 0일경우 아무것도 출력하지 않는다
                    if i == 0:                       # 첫 항의 부호를 출력하기 위해 따로 출력
                        print("%0.2f x^%d" % (self.coef_deg[i][0], self.coef_deg[i][1]), end="")
                    else:
                        if self.coef_deg[i][0] >= 0:
                            print(" + ", end='')
                        else:
                            print(" - ", end='')
                        print("%0.2f x^%d" % (abs(self.coef_deg[i][0]), self.coef_deg[i][1]), end="")

    def find_val(self, x):
        val = 0                                         # 최종 결과 값을 반영해 줄 변수 val 선언
        for i in range(self.degree):                    # 각 항을 돌며
            temp = 1
            for j in range(int(self.coef_deg[i][1])):   # 각 항의 차수 만큼(횟수)
                temp *= x                               # 입력받은 x의 값을 곱해준다
            if self.coef_deg[i][1] == 0:                # 차수가 0일 경우는 상수이므로
                temp = self.coef_deg[i][0]              # 해당 항의 계수가 곧 temp값이 된다
            else:
                temp = temp * self.coef_deg[i][0]
            val += temp                                 # val에 temp값을 더해준다
        print('결과 값은 %0.2f' %val)

def print_val():
    while True:
        e = list(map(float, input("수식에 값을 넣으세요 ").split(' ')))
        if e[0] == 1:
            a.find_val(e[1])
        elif e[0] == 2:
            b.find_val(e[1])
        elif e[0] == 3:
            c.find_val(e[1])
        elif e[0] == 4:
            d.find_val(e[1])
        else:
            print('잘못된 값을 입력하셨습니다!')

def poly2_add(a,b):
    z = []
    apos = bpos = 0
    term_a = a.degree
    term_b = b.degree

    while(apos < term_a) and (bpos < term_b):
        if a.coef_deg[apos][1] > b.coef_deg[bpos][1]:
            z.append([a.coef_deg[apos][0], a.coef_deg[apos][1]])
            apos += 1
        elif a.coef_deg[apos][1] == b.coef_deg[bpos][1]:
            z.append([a.coef_deg[apos][0] + b.coef_deg[bpos][0], a.coef_deg[apos][1]])
            apos += 1
            bpos += 1
        else:
            z.append([b.coef_deg[bpos][0], b.coef_deg[bpos][1]])
            bpos += 1

        if apos >= term_a:
            while bpos < term_b:
                z.append([b.coef_deg[bpos][0], b.coef_deg[bpos][1]])
                bpos += 1
        elif bpos >= term_b:
            while apos < term_a:
                z.append([a.coef_deg[apos][0], a.coef_deg[apos][1]])
                apos += 1
    return poly2(z)

def poly2_mul(a, b):
    x = []                                                                                           # 최종 결과 값을 담아 줄 빈 리스트 x 선언
    apos = 0
    for i in range(b.degree):
        x.append([a.coef_deg[apos][0]*b.coef_deg[i][0], a.coef_deg[apos][1] + b.coef_deg[i][1]])     # 각 항의 계수끼리는 곱하고, 차수끼리는 더해준다.
    x = poly2(x)                                                                                     # 위 연산의 결과 값을 x에 담아준다
    apos += 1

    while (apos < a.degree):
        y = []                                                                                       # 중간 결과 값을 담아 줄 빈 리스트 y 선언
        for i in range(b.degree):
            y.append([a.coef_deg[apos][0]*b.coef_deg[i][0], a.coef_deg[apos][1] + b.coef_deg[i][1]]) # 위와 같은 방식의 연산 수행
        y = poly2(y)                                                                                 # 위 연산의 결과 값을 y에 담아준다

        x = poly2_add(x, y)                                                                          # x와 y를 더해준 값을 x에 담아준다
        apos += 1
    return x

a = list(map(float, input("수식 1을 입력하세요 : ").split(' ')))
while a[1] > 6: # 최고 차항이 6이상이면 값을 다시 입력받는다
    a = list(map(float, input("최대 차수를 초과하였습니다. 다시 입력해주세요! : ").split(' ')))
temp = []
for i in range(0, len(a), 2):
    temp.append(a[i:i+2])
a = poly2(temp)

b = list(map(float, input("수식 2를 입력하세요 : ").split(' ')))
while b[1] > 6: # 최고 차항이 6이상이면 값을 다시 입력받는다
    b = list(map(float, input("최대 차수를 초과하였습니다. 다시 입력해주세요! : ").split(' ')))
temp = []
for i in range(0, len(b), 2):
    temp.append(b[i:i+2])
b = poly2(temp)

c = poly2_add(a, b)
d = poly2_mul(a, b)

print('수식 1은 ', end='')
a.print_poly2()
print('수식 2는 ', end='')
b.print_poly2()
print('수식 1 + 2는 ', end='')
c.print_poly2()
print('수식 1 * 2는 ', end='')
d.print_poly2()

print_val()

다음과 같은 미로가 maze1.txt라는 텍스트 파일에 작성되어있다. 이때 해당 파일을 읽어 미로를 화면에 표시하는 프로그램을 작성한다.

⚡️ 프로그램의구성

• 파일에서 데이터를 읽는다.
• 읽은 미로 데이터를 어디엔가 저장한다.
• 미로 데이터를 출력함수를 이용하여 화면에표시한다.

⚡️ 조건

• maze1.txt 파일의 크기는 531 바이트인데, 이 파일의 데이터(미로)를 저장하는 공간의 크기를 최소화 해야한다.
• 즉 완성된 프로그램이 미로를 저장하는 형태는 원본 파일과 다를 수 있다.
• 하지만 출력시엔 파일에 저장된것과 같은 형태로 화면에 표시해야한다.
• 단, 파일에서 그대로 읽어서 그대로 표시하는 것은 “공간의 크기를 최소화”하는 조건에 부합하지 않는다.

📌 미로를 어떻게 저장할 것인가?

f = open('maze2.txt', 'r')     # 파일 읽기 모드로 열기

line = f.readline()             # 첫 줄(ex. 9X12, 10X10)은 생략
width = int(line.split()[0])    # 미로의 가로(너비)값 저장
height = int(line.split()[1])   # 미로의 세로(높이)값 저장

우선 미로를 담고 있는 파일을 읽기 모드로 열어준 뒤, 미로의 첫번째 줄(ex. “9x12”, “10x10”)은 생략해준다. (굳이 필요 없으므로) 그리고 미로의 가로(너비)와 세로(높이)를 구하여 각각 width와 height 변수에 넣어준다.

maze = []     # 미로의 정보를 담을 리스트
line_Num = 0 # 행 번호

while True:
    disk = []
    line = f.readline().strip()   
    line_Num += 1
    if not line: break

    # 홀수 행일 경우
    # 각 행의 짝수번째 요소들만 남겨준다
    if line_Num % 2 == 1:
        for i in range(len(line))[1::2]:
            disk.append(line[i])
        disk = ("".join(disk))

    # 짝수 행일 경우
    # 각 행의 홀수번째 요소들만 남겨준다
    else:
        for i in range(len(line))[0::2]:
            disk.append(line[i])
        disk = ("".join(disk))

다음으론 미로의 데이터를 가공하여 담아 줄 리스트 maze를 선언해준다. 그 후 텍스트 파일을 한 줄씩 가져와 line에 저장한다. 이때, line_Num을 통해 각 행의 번호를 파악하고, 홀수 행일 경우에는 각 행의 짝수 번째 요소들만 남겨준다. 이렇게 하는 이유는 홀수 행의 홀수 번째 요소들은 모두 +, -, | 문자들로 이루어져 있으므로, 해당 위치가 공백이 아니라 문자로 이루어져 있다는 사실만 인지하고 있으면 되기 때문이다. (ex. "+---+---+" -> "----")

비슷한 이유로 짝수 행일 경우, 각 행의 홀수 번째 요소들만 남겨주는데, 짝수 행의 짝수 번째 요소들은 모두 공백 문자이기 때문에 굳이 저장할 필요가 없다. (ex. "| | | |" -> "| | | |")

str = disk.replace('-', '1')    # 각 줄의 '-', '|'기호를 '1'로 변환
str1 = str.replace('|', '1')
str2 = str1.replace(' ', '0')   # 각 줄의 공백 문자를 '0'으로 변환

이제 이렇게 가공된 행들의 -, | 문자는 숫자 1로, 공백 문자는 숫자 0으로 치환하여 각 행을 이진수 형태로 변환해준다.

dec_Num = int(str2, 2)   # 각 이진수를 10진수로 변환한 값을 저장할 변수
maze.append(dec_Num)     # 변환된 10진수를 maze에 저장

위의 과정들을 거쳐 미로 파일의 각 행(문자열)들은 하나의 이진수로 변환되었는데, 이렇게 얻어진 이진수들을 10진수 dec_Num으로 변환한 후 maze에 차례로 넣어준다.

이때 주어진 미로의 규격이 9x12이므로 각 행의 이진수들은 모두 910자리수 이므로 **911비트 범위 내이다. 이는 바이트로 환산해보아도 2바이트가 채 되지 않아 short범위 내에 속한다.**

즉 위의 과정들을 거쳐 각 행을 2바이트 이내의 용량으로 저장할 수 있게 된 것이고 이는 기존의 저장 방식(각 행의 용량: 19바이트)에 비해 훨씬 적은 용량으로 미로의 데이터를 저장할 수 있게 되었음을 의미한다.

미로의 저장 공간의 크기는 최대 50바이트가 될 것이다. (2바이트(short의 크기) * 25(총 행의 개수) = 50)

📌 미로를 어떻게 출력할 것인가?

# maze에 저장된 데이터를 바탕으로 미로를 다시 출력해 줄 함수
def draw_maze(maze, width, height):     
    output = []             # output list 생성
    row_C = width * 2 + 1   # 미로의 실제 가로 길이(너비)(텍스트 파일 기준)
    col_C = height * 2 + 1  # 미로의 실제 세로 길이(높이)(텍스트 파일 기준)

    for i in range(len(maze)):
        # maze에 저장되어있던 각 10진수들을 다시 2진수로 변환
        bi_Num = list(bin(maze[i])[2:].zfill(width))

우선 maze에 저장된 데이터를 바탕으로 미로를 다시 출력해 줄 함수 draw_maze를 선언하고, maze에 저장되어 있던 각 10진수들을 다시 2진수 bi_Num으로 변환해준다.

if i % 2 == 0:
    bi_Num = "1".join(bi_Num)
    full_Bi = list(bi_Num)
    full_Bi.insert(0, '1')
    full_Bi.append('1')

이때 홀수 행의 경우, 생략했던 홀수 번째 요소들(1)을 복구시켜 full_Bi에 담아준다.

else:
    bi_Num = "0".join(bi_Num)
    full_Bi = list(bi_Num)

짝수 행의 경우, 생략했던 짝수 번째 요소들(0)을 복구시켜 full_Bi에 담아준다. 위의 과정들을 거쳐 maze에 가공된 형태로 저장되어 있던 데이터는 원래 미로의 너비와 같은 길이의 이진수로 변환된다.

output.append(full_Bi)

그리고 이렇게 복구된 이진수들을 output이라는 2차원 리스트에 차례로 담아준다.

이때 변환된 이진수들을 (ex. 1000101001) 1차원 리스트(ex. [ '1000101001' , '1010001010' ] ) 형태로 저장하지 않고 2차원 리스트(ex. [ [1,0,0,0,1,0,1,0,0,1] , [1,0,1,0,0,0,1,0,1,0] ] ) 형태로 저장하는 이유는, 한 줄의 데이터에서 짝수 번째 요소와 홀수 번째 요소를 나누어서 데이터를 변환해야 하는데, 2차원 리스트가 이에 용이하기 때문이다.

이제 출력할 차례이다. 이진수 형태로 저장된 미로를 다시 실제 미로처럼 바꾸는 과정은 다음과 같다.

1. 미로의 가장자리 벽 4변을 실제 미로 모양으로 바꾼다.

# 위쪽 가장자리 벽 정리
for j in range(row_C):
    if output[1][j] == '1':
        del output[0][j]
        output[0].insert(j, '+')
    else:
        del output[0][j]
        output[0].insert(j, '-')

    # 아래쪽 가장자리 벽 정리
    if output[-2][j] == '1':
        del output[-1][j]
        output[-1].insert(j, '+')
    else:
        del output[-1][j]
        output[-1].insert(j, '-')

• 이때 맨 위쪽과 맨 아래쪽 벽은 -, + 로만 구성되어 있다.
• 이 중 맨 위의 다음 줄, 그리고 맨 아래의 이전 줄에 1의 값이 저장된 경우엔 + 로 변환한다.
• 그 외의 경우엔 모두 - 로 변환한다.
  

# 왼쪽 가장자리 벽 정리
for i in range(col_C)[1:-1]:
    if output[i][1] == '1':
        del output[i][0]
        output[i].insert(0, '+')
    else:
        del output[i][0]
        output[i].insert(0, '|')

    # 오른쪽 가장자리 벽 정리
    if output[i][-2] == '1':
        del output[i][-1]
        output[i].append('+')
    else:
        del output[i][-1]
        output[i].append('|')

• 맨 왼쪽과 맨 오른쪽의 가벽의 경우는 | , + 로만 구성되어 있다.
• 이 중 가장 왼쪽의 오른쪽 열, 그리고 가장 오른쪽의 왼쪽열에 ‘1’의 값이 저장된 경우엔 + 로 변환한다.
• 그 외의 경우엔 - 로 변환한다.

# 홀수행 정리
# 홀수행 중 짝수열 값 정리
for i in range(col_C)[2:-1:2]:
    for j in range(row_C)[1::2]:                                    
        if output[i][j] == '1':
            del output[i][j]
            output[i].insert(j, '-')
        else:
            del output[i][j]
            output[i].insert(j, ' ')
# 홀수행 중 홀수열 값 정리
    for j in range(row_C)[2:-1:2]:
        if output[i][j-1] == '-' and output[i][j+1] == '-' \
            and output[i+1][j] == ' ' and output[i-1][j] == ' ':    
            del output[i][j]
            output[i].insert(j, '-')
        elif output[i-1][j] == '|' and output[i+1][j] == '|' \
            and output[i][j-1] == ' ' and output[i][j+1] == ' ':    
            del output[i][j]
            output[i].insert(j, '|')
        else:                                                       
            del output[i][j]
            output[i].insert(j, '+')

• 홀수 행: 실제 미로의 홀수 행은 +, -, | , 공백, 총 4가지 요소로 이루어져 있다.
• 이는 다시 짝수 열과 홀수 열로 나누어서 살펴본다.

• 짝수 열의 경우 공백문자와 - 문자로만 이루어져 있다.
• 따라서 output에 저장된 홀수번째 데이터의 짝수번째 값이 1이면 - 문자로, 0이면 공백문자로 변환한다.

• 홀수 열의 경우 공백문자를 제외한 모든 요소들로 구성된다.
• 따라서 output에 저장된 홀수번째 데이터의 홀수번째 값들은 모두 1이다.

• 이 1들도 다음과 같은 규칙에 의해서 +, - , | 으로 변환된다. 1) 홀수 행의 홀수 열을 기준으로 왼쪽과 오른쪽 열에 - 인 벽이 존재하고, 위쪽과 아래쪽 행에 공백으로 벽이 없을 경우: - 문자 2) 홀수 행의 홀수 열을 기준으로 왼쪽과 오른쪽 열에 공백으로 벽이 없고, 위쪽과 아래쪽 행에 | 인 벽이 존재할 경우: | 문자 3) 홀수 행의 홀수 열이 - 또는 | 로 변환되는 기준에 해당하지 않는 모든 경우: + 문자

# 미로 출력
for i in output:
    print("".join(i))

마지막으로 이중리스트 형태로 저장된 output을 join메소드를 통해서 하나의 문자열로 통합한 후 출력해준다.

위와 같은 방법으로 10진수로 저장되어 있던 데이터를 다시 원래 미로의 형태로 출력할 수 있었다.

📌 실행결과

📌 전체코드

f = open('maze1.txt', 'r') # 파일 읽기 모드로 열기

line = f.readline()             # 첫 줄(ex. 9X12, 10X10)은 생략
width = int(line.split()[0])    # 미로의 가로(너비)값 저장
height = int(line.split()[1])   # 미로의 세로(높이)값 저장

maze = []   # 미로의 정보를 담을 리스트
line_Num = 0 # 행 번호

while True:
    disk = []
    line = f.readline().strip()   # 2번째 줄 부터 끝까지 파일의 정보를 한 줄씩 가져 온다
    line_Num += 1
    if not line: break

    # 홀수 행일 경우
    # 각 행의 짝수번째 요소들만 남겨준다
    # why? -> 홀수 행의 홀수번째 요소들은 모두 '+'혹은 '-'문자로 이루어져 있기 때문에, 해당 위치에 문자가 존재 한다는 사실만 알고 있으면 되기 때문
    # ex. "+---+---+" -> "----"
    if line_Num % 2 == 1:
        for i in range(len(line))[1::2]:
            disk.append(line[i])
        disk = ("".join(disk))

    # 짝수 행일 경우
    # 각 행의 홀수번째 요소들만 남겨준다
    # why? -> 짝수 행의 짝수번째 요소들은 모두 공백 문자이기 때문에 굳이 저장할 필요가 없다.
    # ex. "|   |   |   |" -> "| | | |"
    else:
        for i in range(len(line))[0::2]:
            disk.append(line[i])
        disk = ("".join(disk))

    str = disk.replace('-', '1')    # 각 줄의 '-', '|'기호를 '1'로 변환
    str1 = str.replace('|', '1')
    str2 = str1.replace(' ', '0')   # 각 줄의 공백 문자를 '0'으로 변환

#==================== 위의 과정을 거쳐 각 줄(문자열)은 이진수로 변환된다. =======================#

    dec_Num = int(str2, 2)   # 각 이진수를 10진수로 변환한 값을 저장할 변수
    maze.append(dec_Num)     # 변환된 10진수를 maze에 저장
f.close()
#============================ maze에 미로 데이터 입력 완료 =================================#

def draw_maze(maze, width, height):     # maze에 저장된 데이터를 바탕으로 미로를 다시 출력해 줄 함수
    output = []             # output list 생성
    row_C = width * 2 + 1   # 미로의 실제 가로 길이(너비)(텍스트 파일 기준)
    col_C = height * 2 + 1  # 미로의 실제 세로 길이(높이)(텍스트 파일 기준)

    for i in range(len(maze)):
        # 1. maze에 저장되어있던 각 10진수들을 다시 2진수로 변환
        bi_Num = list(bin(maze[i])[2:].zfill(width))

        # 2. 홀수행의 경우, 홀수번째 요소들을 복구시킨다.
        if i % 2 == 0:
            bi_Num = "1".join(bi_Num)
            full_Bi = list(bi_Num)
            full_Bi.insert(0, '1')
            full_Bi.append('1')

        # 3. 짝수행의 경우, 짝수번째 요소들을 복구시킨다.
        else:
            bi_Num = "0".join(bi_Num)
            full_Bi = list(bi_Num)
        # 즉, 위의 과정들을 거쳐 maze에 가공되어 저장되어 있던 데이터들은 원래 미로의 너비와 같은 길이의 이진수의 형태로 변환된다.

        # 4. 복구된 리스트들을 output이라는 2중 리스트에 담아준다.
        output.append(full_Bi)

    # 미로의 첫번째 줄 정리
    for j in range(row_C):
        if output[1][j] == '1':
            del output[0][j]
            output[0].insert(j, '+')
        else:
            del output[0][j]
            output[0].insert(j, '-')

        # 미로의 마지막 줄 정리
        if output[-2][j] == '1':
            del output[-1][j]
            output[-1].insert(j, '+')
        else:
            del output[-1][j]
            output[-1].insert(j, '-')

    # 왼쪽 가벽 정리
    for i in range(col_C)[1:-1]:
        if output[i][1] == '1':
            del output[i][0]
            output[i].insert(0, '+')
        else:
            del output[i][0]
            output[i].insert(0, '|')

        # 오른쪽 가벽 정리
        if output[i][-2] == '1':
            del output[i][-1]
            output[i].append('+')
        else:
            del output[i][-1]
            output[i].append('|')

    #=========== 가벽 안의 값들 정리 =============#
    # 짝수 행 정리
    for i in range(col_C)[1::2]:
        for j in range(row_C)[1:-1:]:
            if output[i][j] == '1':
                del output[i][j]
                output[i].insert(j, '|')
            else:
                del output[i][j]
                output[i].insert(j, ' ')

    # 홀수 행 정리 (2가지 과정)
    # 홀수 행 중 짝수열 값 정리
    for i in range(col_C)[2:-1:2]:
        for j in range(row_C)[1::2]:                                    #홀수 행의 짝수 열이 '1'이면 '-' 아니면 공백
            if output[i][j] == '1':
                del output[i][j]
                output[i].insert(j, '-')
            else:
                del output[i][j]
                output[i].insert(j, ' ')
    # 남은 홀수 행 중 홀수열 값 정리
        for j in range(row_C)[2:-1:2]:
            if output[i][j-1] == '-' and output[i][j+1] == '-' \
                and output[i+1][j] == ' ' and output[i-1][j] == ' ':    #홀수 행의 홀수 열 중 '-'가 되는 조건
                del output[i][j]
                output[i].insert(j, '-')
            elif output[i-1][j] == '|' and output[i+1][j] == '|' \
                and output[i][j-1] == ' ' and output[i][j+1] == ' ':    #홀수 행의 홀수 열 중 '|'가 되는 조건
                del output[i][j]
                output[i].insert(j, '|')
            else:                                                       #나머지는 '+'로 표시
                del output[i][j]
                output[i].insert(j, '+')

    # 미로 출력
    for i in output:
        print("".join(i))

draw_maze(maze, width, height)          # 가공하여 저장했던 미로 다시 출력