시뮬레이터에 원래 있는 mano hand model 말고 prosthetic hand model로 교체하고자 함

시뮬레이터에 들어가는 mano hand model은 .urdf 파일 이었고, 의수 hand model은 mujoco haptix의 MPL (Modular Prosthetic Limbs)였다. 교체할 MPL hand model은 mujoco 시뮬레이터에 import할 수 있는 mjcf 형태의 .xml 로 되어있었다.

처음에는 xml2urdf를 서치했는데 방법들이 마땅치 않아서 무작정 .urdf파일 형식을 공부해서 직접 변환하려고 .urdf 를 공부했다. (바보였음...)

공부를 하다가 mjcf2urdf라는 패키지가 있음을 발견하게 되었다.

바로 설치후 변환을 해보았다.

설치방법

pip install mjcf2urdf

사용방법

mjcf2urdf <변환할 mjcf 파일> --out <변환한 파일 저장 경로>

간단하게 해결 완료했다!

주의사항

변환 후 .stl파일들이 unknown으로 제대로 연결되지 않을 수도 있으므로 이 부분만 다시 제대로 연결해주면 된다!

reference

https://pypi.org/project/mjcf2urdf/ https://github.com/philtabor/PyBullet-Hand-Example

• Proxy Pattern - 하나의 객체가 다른 객체를 대신하게 함
• Chain of Responsibility Pattern - 요청을 보내는 쪽과 받는 쪽의 결합을 피함
• Flyweight Pattern - 본질적인 것과 부가적인 것을 구분함

프록시 패턴

• 요약
  • 특정 객체에 접근(access)을 조절하기 위하여 대리자(프록시)를 세움
  • 필요할 때만 비싼 대가의 기능을 접근하도록 프록시를 사이에 둠
  • 보이지 않는 부분을 proxy로 갖고있다가 나중에 보여질 때 원본을 가져옴
• 역할
  • 시간이 많이 소요되는 불필요한 복잡한 객체를 생성하는 시간을 간단한 객체로 줄임
  • ex) 웹 페이지 - 실제 화면에 출력할 필요가 있는 객체만 생성하고 밑에 있는 것들은 proxy로 갖고있다가 active되면 original을 가져옴 → 처음부터 original을 가져오면 웹 페이지를 처음 가져올 때 시간이 너무 오래 걸림 → 비요휼적임
• 기존 설계(예제: 문서편집기)

• Proxy Pattern 적용한 설계(예제: 문서편집기)
  • 대리자(proxy)로 original객체를 대신하고 proxy는 요청을 받았을 때 original 객체를 가져옴 → 효율적 운영
  • proxy가 original의 요청을 받으면 original이 있는지 확인해서 있으면 바로 주고 없으면 original을 불러옴
  • 따라서 proxy는 original의 위치를 알고있어야 함
  • 클래스 다이어그램

• 구조 및 구성요소

  • 일반적인 구조

    → Client가 proxy / original 에 대해 같은 인터페이스로 이용할 수 있도록

- 구성 요소

    → Proxy[대리자]: Subject인터페이스를 구현하여 RealSubject객체를 대신할 수 있음. RealSubject객체에 대한 레퍼런스 유지 및 접근 조절, 해당 객체의 생성과 소멸을 책임 질 수도 있음. 

    → Subject[인터페이스]: RealSubject와 Proxy의 공통 인터페이스

    → RealSubject[실제객체]: Proxy가 대신할 original객체

- 프록시는 클라이언트의 요청을 RealSubject 객체에 보냄 → association

• 프록시 종류
  • 리모트 프록시: 다른 공간에 존재하는 객체에 대한 로컬 표현 (disk→screen)
  • 가상 프록시: 복잡한 객체를 필요할 때 생성 (ex. game)
  • 보호(protection) 프록시: 원래 객체에 대한 접근 권한을 제한 (ex.인증 과정 거쳐서 접근)
  • 스마트 레퍼런스: 객체 접근시 추가적인 액션 수행, 객체의 참조 회수 관리 or 객체를 수정할 수 없도록 locking
• 적용 결과
  • 투명성: 리모트 프록시는 객체가 다른 주소공간에 존재하는 사실을 숨길 수 있게 함 → Client입장에서는 차이를 못느낌 but, 시간은 빨라짐
  • 최적화: 가상 프록시는 객체를 필요할 때 생성하여 최적화 수행. 불필요한 다운로드 또는 heavy work 피함
  • 보호 프록시와 스마트 레퍼런스는 객체가 접근할 때 추가적인 housekeeping작업을 수행한다. (ex. 관리를 위해 count, traffic, 가격 계산 등등 추가적인 것들)

책임 체인 패턴

• 요약
  • 요청을 보내는 객체(sender)와 요청을 처리하는 객체(receiver)를 분리
  • 요청에 대하여 자신이 처리할 수 있으면 요청을 처리하고 처리할 수 없으면 연결된 다음 객체에 요청을 넘긴다.
• 역할
  • 요청을 보내는 객체와 요청을 처리하는 객체를 분리하여 결합도를 줄여 추가, 수정시 코드 변경 영향을 줄인다.
  • 결합도를 낮춤: 요청을 보내는 쪽은 어떤 객체에 전달할지 고려 안해도 되고 요청을 처리할 수 있는 객체들의 reference를 모두 가질 필요가 없다. 첫번 째 객체에게 요청을 보내면 그 다음부터는 연결고리 객체들이 자동으로 요청을 전파함 → 따라서 결합도를 낮출 수 있음
  • 객체에 책임 배정이 융통적임: 연결고리 객체들을 동적으로 삽입, 삭제할 수 있음 → 수정, 변경 융통적, 객체들 간의 책임 분산이 동적으로 이루어짐
• 기존 설계(예제: 도움말GUI)
  • 도움말 기능을 전담하는 객체 정의 → coupling이 높음(switch문) → 수정 및 기능 추가시 코드 변경이 많이 됨
  • 장점: 도움말 관련 기능을 한 군데로 모임 → 관리와 기능 확장이 용이
  • 단점: setState()함수를 이용하여 사용자의 현재 상태를 설정 → coupling 높음 → 새로운 상태와 기능이 추가 혹은 변경시 영향받는 범위 커짐.

• Chain of Responsibility Pattern 적용한 설계(예제: 도움말GUI)
  • 클래스 다이어그램

- 특정 요청에 대하여 이를 처리하는 객체를 고정하지 않고 요청을 처리하는 객체 group에 이 요청을 보냄
- 요청을 보내는 객체(sender)와 요청을 처리하는 객체(receiver)를 분리
- 객체들의 연결 고리(chain)

    → 요청에 대하여 각 객체는 자신이 처리할 수 있으면 처리

    → 처리할 수 없으면 연결된 다음 객체에 요청을 넘김(chain of responsibility)

• 구조 및 구성요소

  • 클래스 다이어그램

  • 요청 전파를 위해 상속 구조

  • 요청을 처리하지 못한 경우 이 요청을 다음 객체로 전달할 수 있도록 지정되어야함

  • 처리 확신 불가: 연결고리에 있는 객체들 모두가 특정 요청을 처리할 수 없는 경우 있을 수 있음 → sender는 요청 처리를 확신할 수 없음

• 구현

  • 후속 체인의 구현

    → 기존에 존재하는 링크를 이용: 상속 관계로 인한 연결 레퍼런스 존재, 이 링크를 "책임 체인"링크로 사용할 수 있음

    → 체인을 구성하기 위한 링크를 새로 정의: 일반적으로 핸들러 클래스에서 구현

  • 다음 처리(successor) 연결

    → 링크를 새로 정의하는 경우, 링크에 대한 관리와 호출을 구현해야 함

  • 요청이 하나가 아니고 여러개라면

    → 각 요청에 대하여 개별적인 함수 구현

    → 요청을 표현하는 객체(Request)를 만들어서 이를 handleRequest()함수의 인자로 넘김

플라이웨이트 패턴

• 요약
  • 수많은 작은 객체를 생성할 때 사용되는 많은 객체의 생성을 관리하는 객체를 따로 두어 이를 통해 필요한 객체를 참조형태로 사용한다.
  • 본질적인 것과 부가적인 것을 구분하려 할 때 사용
• 역할
  • 클래스가 데이터를 무겁게 갖고있을 때 공유할 필요가 있는 것과 없는 것을 나누어 공유할 수 있는 것을 분리하여 따로 관리하며 필요할 때 마다 참조해서 사용하도록 한다.
• 기존 설계(예제: 게임 캐릭터)
  • 클래스다이어그램

• Flyweight Pattern 적용한 설계(예제: 게임 캐릭터)
  • 클래스다이어그램

→ 공유되는 것과 공유되지 않는 것을 분리하고 링크로 공유 객체를 가져옴

• 공유객체 관리

  • 싱글톤 패턴 사용하기 공유 객체는 하나만 있어도 되므로 static으로 선언. 싱글톤 패턴을 사용하여 공유 객체는 하나만 생기도록 한다.
  • 팩토리 사용하기 공유 서브클래스 객체를 생성하는 팩토리 클래스 생성 → 객체 생성 위임 각 객체는 자신에 맞는 공유 객체 생성을 팩토리에 요청 팩토리는 각 공유 서브 클래스마다 단 하나의 객체만 생성되도록 보장 → 팩토리 패턴을 적용하여 공유 객체 생성을 위임 → 만들어져있는 공유 객체가 있으면 반환하고 없으면 새로 만들어서 반환

• 구조 및 구성요소

  • 클래스다이어그램

- Flyweight: 공통 인터페이스. extrinsic data를 넘겨받아 연산 수행.
- ConcreteFlyweight: 공유될 수 있는 객체들. Flyweight 인터페이스를 구현하고 intrinsic data를 보관
- UnsharedConcreteFlyweight: 공유하지 않지만 공유되는 객체들과 같이 취급되는 객체들을 표현
- FlyweightFactory: flyweight객체를 생성하고 관리. 공유를 책임짐. 싱글톤 패턴 적용하여 객체 하나만 만들어지도록(공유 객체의 유일성 보장)
- Client: (필요하다면) extrinsic data를 보관하거나 계산한다.

    → Client는 직접적으로 ConcreteFlyweight 객체를 생성하지 않고, FlyweightFactory 객체를 통해 공유객체 생성

    → Unshared 객체를 부르고 Unshared 객체가 share 객체 불러서 합침

• 적용 및 구현

  • 객체의 상태: Intrinsic state, Extrinsic state

    → Intrinsic state: 공유될 수 있는 상태 정보. ConcreteFlyweight 객체에 보관됨

    → Extrinsic state: 공유될 수 없는 상태나 상황(context) 정보. Client에서 보관되거나 계산됨

    → Extrinsic state가 차지하는 메모리 공간이 적거나, 저장하지 않고도 간단한 계산을 통해서 얻어질 수 있는 경우라면 객체 공유로 얻을 수 있는 효과가 큼

    → Intrinsic state가 클 수록 효과적임

  • 적용 범위

    → 공통되는 부분이 많을 때 & 객체간 구별 필요 없을 때

    → 많은 객체의 사용으로 저장 공간에 대한 부담이 클 때

    → Extrinsic state 제외하면, 대부분의 객체들이 상대적으로 소수의 공유 객체로 대체될 수 있을 때

    → 응용 프로그램이 객체들을 서로 구분할 필요가 없을 때

2021 Spring 최은만 교수님 객체지향 패턴 및 설계 수업 필기노트

나는 로컬 서버에 저장된 파일들을 원격 서버로 전송해야 하기 때문에

scp -P <port_number> <file_path>/* <username>@<remote_server_ip>:/home/<username>/<file_path>

를 사용하여 파일을 전송했다.

정리하자면

scp -P <포트번호> <로컬 파일 경로> 원격서버사용자@원격 서버 ip 주소:전송할 경로

원격지 서버가 포트를 기본포트 22번을 사용하는 경우에는 -P <포트 번호>를 생략해도 되지만, 포트를 22번이 아닌 다른 포트번호를 사용하는 경우에는 -P <포트 번호>로 알맞는 포트번호를 지정해야 한다. (대문자로 해야함. 소문자는 다른 옵션이 또 있음)

폴더 안에 여러개의 파일들을 모두 옮길 땐 *<폴더 경로>/ ** 를 하면 한꺼번에 옮길 수 있다.

파일들을 무사히 잘 옮겼다! ** !! 해결 완료 !! **

running install
error: can't create or remove files in install directory

The following error occurred while trying to add or remove files in the
installation directory:

    [Errno 13] Permission denied: '/usr/local/lib/<folder or directory name>/test-easy-install-9739.write-test'

The installation directory you specified (via --install-dir, --prefix, or
the distutils default setting) was:

    /usr/local/lib/<folder name>

Perhaps your account does not have write access to this directory?  If the
installation directory is a system-owned directory, you may need to sign in
as the administrator or "root" account.  If you do not have administrative
access to this machine, you may wish to choose a different installation
directory, preferably one that is listed in your PYTHONPATH environment
variable.

For information on other options, you may wish to consult the
documentation at:

  https://setuptools.readthedocs.io/en/latest/easy_install.html

Please make the appropriate changes for your system and try again.

error를 찬찬히 보던 도중 아래의 문구가 눈에 들어왔다. 권한 문제인듯 하였다. 아무래도 연구실 서버에 컨테이너를 할당받아 사용하는데 기존에 컨테이너를 생성한 계정 말고 다른 새로운 계정을 추가하여 사용하다보니 권한 에러가 자주 발생하는 것 같다.

1st trial chmod 777 명령어로 권한을 변경한다

chmod 777 <folder name>

오류 발생 다음과 같은 오류가 발생했다

chmod: changing permissions of <folder or directory name>: Operation not permitted

2nd trial sudo로 실행하였다.

sudo chmod 777 <folder name>

해결완료 ! 인 줄 알았으나 맨 처음 난 에러가 동일하게 발생함.

ls -l

을 해서 권한을 체크하였는데 권한은 모두 풀려있었지만 root에 한해서만 풀린거였다...! 나는 사용자이기 때문에 사용자를 추가해주어야 했다

sudo chmod ugo+rwx <folder or directory name>

u: 사용자 g: 그룹 o: 다른 사용자 에게 read, wright, execute 권한을 주었다.

권한이 staff에게도 생겼다!

python setup.py install

다시 설치를 진행해 보았다. !! 설치가 성공적으로 진행되었다 !!

** 해결 완료 !! **

1. 프로세스 관리: 여러개의 프로세스가 충돌 없이 원활하게 수행할 수 있도록 관리한다 2. 메모리 관리: 한정된 용량의 주 기억장치에 여러개의 프로그램을 필요에 맞게 효율적으로 사용할 수 있도록 관리한다 3. 저장공간 관리(파일시스템): 파일시스템 기능을 통해 파일을 관리하고 디스크 관리 기능을 통해 보조 기억 장치를 관리한다 4. 디바이스 관리(드라이버): 컴퓨터에 연결된 입출력 장치 및 주변 하드웨어 장치를 인식하고 관리 및 제어한다 5. 네트워크: 프로세스간 정보 교환이 필요할 때에 네트워크를 통해 수행한다

Bootstrap

: 컴퓨터가 구동을 시작하기 위해 수행하는 초기 프로그램

필요한 이유

• 필요한 이유: 컴퓨터가 구동을 시작하기 위해서는 수행할 초기 프로그램이 있어야 하기 때문이다
• ROM에 저장하는 이유: 비휘발성이기 때문에 전원을 꺼도 안 날라감
• 운영체제 패키지에 포함시키지 않는 이유: Bootstrap이 운영체제보다 먼저 실행되어야 하기 때문이다

  수행 기능

  시스템에 전원이 인가되었을 때, 하드웨어를 초기화하고, 하드웨어에 있는 OS를 메모리에 로드한다. OS가 저장된 메모리의 첫번째 주소 값을 PC에 넘겨주어 OS 부팅을 실행한다.

  마지막 명령어

  OS가 저장돼있는 메모리의 첫번째 주소를 PC에 넘겨준다

Multiprogramming

: 처리해야 될 process가 많은 상황. 실행해야 할 program이 2개 이상인 상황. 한 program이 IO를 실행하는 오랜 시간 동안 CPU의 활용도를 높이기 위하여 다른 program들을 실행할 수 있도록 하기 위해 도입되었다

Multiprogramming 또는 multitasking 환경에서 OS

• 필요한 이유: 제한된 컴퓨팅 자원인 CPU, Main Memory, HDD등을 2개 이상의 다수의 프로그램이 공유함으로써 다양한 문제가 발생할 수 있으며, 이를 해결하기 위하여 시스템을 관리하는 소프트웨어가 필요하기 때문에 OS가 필요하다
• CPU: 다수의 프로그램들이 순차적이고 효율적으로 CPU를 사용할 수 있도록 스케줄링이 필요하다
• Main Memory: 다수의 프로그램들이 제한된 메모리 공간을 분할하여 사용할 수 있도록 관리가 필요하다
• HDD: 다수의 프로그램들이 제한된 영구저장 공간을 분할하여 사용할 수 있도록 관리가 필요하다

Multiprogramming 환경에 있어서, 한 process가 IO operation을 포함하지 않는다면 자신이 종료될 때 까지 CPU를 독점할 수 있다.

[문제점]

이와 같은 상황에서 만약 이 process가 실행되는 시간이 매우 길다면 해당 program은 CPU를 최대한 활용하여 신속하게 실행될 수 있지만, 다수의 사용자나 다수의 프로그램 관점에서 본다면 다른 process들이 기다려야 하는 시간(wating time)이 너무 길어지는 문제가 발생하여 시스템 전체의 효율이 낮아진다. 또한, IO subsystem 또한 중요한 자원(resource)인데, 이들의 활용도가 낮아져서 시스템 전체의 활용도가 저하된다.

[해결방안]

Time Slice, Time Quantum, Time sharing : 한 process가 실행될 수 있는 시간을 정해두고 그 시간이 지나면 다른 process로 넘겨준다. 즉, multitasking 방식의 스케줄링 알고리즘을 채택하는 것이 필요하다. 이 해결 방안에 필요한 하드웨어는 clock

[출처] 이강우 교수님 운영체제 수업

논문 원문: https://arxiv.org/pdf/2007.03056.pdf

VPN: 3DConvNet의 top layer로 plugged in 되어서 활용됨.

VPN 구성 요소

1. Attention Network

   1. Pose Backbone: 3D Poses를 Graph로 만들어서 GCN에 넣어서 3D Pose의 feature h* 추출

      input: 3P Pose

      output: h*

   2. spatio-temporal coupler: 3D Poses의 공간적인 특성과 시간적인 특성에 대한 attention weight 생성.

      input: h*

      output: Ast

1. Spatial Embedding

   RGB image와 3P Pose사이의 correspondences 높이기 위한 embedding 학습

   input: fs, z1(from stc)

   training spatial embedding vector through Le

   pose와 rgb 간의 correspondence 측정은 embedding space에서 mapping된 거리 측정

This is a first step towards combining RGB and Pose through an explicit embedding.

→ 동작이 비슷해서 헷갈리는 동작들을 정확하게 인식하기 위해서!

2) VPN++: Rethinking Video-Pose embeddings for understanding Activities of Daily Living

논문 원문: https://arxiv.org/pdf/2105.08141.pdf

https://github.com/srijandas07/vpnplusplus

VPN Accuracy 비교

• VPN++를 하는 이유: 기존의 VPN이 성능은 좋은데 너무 느림
• VPN-F와 VPN-A를 개발하고 이 둘을 합쳐서 VPN++를 만듦. → VPN++ = VPN-F + VPN-A
• VPN++는 training할 때 RGB와 Pose를 사용하고 test할 때는 RGB만 넣어서 VPN보다 속도를 빠르게 함!
• VPN++에 input에 Pose도 같이 넣는 것은 VPN++보다 정확도가 조금 높아지는 것에 비해 시간이 거의 100배 가까이 걸리기 때문에 VPN++이 effective함!

VPN, VPN-F, VPN-A, VPN++

1. VPN

• RGB backbone(i3d)
• Pose backbone(GCN)
• STC
• SE

2. VPN-F

• Teacher-Student Network
• Contrastive Learning
• SE, STC x

→ Contrastive Learning을 통해 RGB 이미지와 3D Pose pair의 correspondence를 학습. (SE x)

→ training시에 Pose feature들을 학습시켜서 student network인 RGB backbone에 넘겨줌

3. VPN-A

• Teacher-Student Network
• Self-attention Mechanism
• Collaborative Learning
• VPN* (w/o SE)

→ 기존 VPN에서 Attention Network가 하는 일을 함

→ Attention weight들을 학습히켜서 Student Network인 Self-attention block에 넘겨줌 (VPN의 STC에서 뱉어내는거랑 같은 웨이트들)

→ VPN teacher network is trained with action labels to learn pose driven attention weights At to modulate its RGB feature map. (Ltc)

→ VPN*가 뱉은 At 랑 self attention block의 As의 MSE로 Loss 설정 (Ld)

4. VPN++

• VPN-F + VPN-A

• (positive, negative) pairs: feature-level distillation

• (positive, positive) pairs: attention-level distillation

• 최종 Loss

  → alpha, beta는 weighting factors

• testing시에는 only use RGB frames as input to compute action classes scores, avoiding the requirement of 3D poses
  → 3D poses는 시간 너무 오래걸려서 뺌

Experiments

• dataset 특이 사항
  • Toyota Smarthome(SH): kinetic 안써서 3D skeletons는 LCRNet으로 추출함
• training time
  • Teacher network for VPN-F: AGCN-J를 Pose backbone으로 사용
  • Teacher network for VPN-A: VPN*(SE없는 VPN) + 2 layer AGCN 를 Pose backbone으로 사용
  • Student network: I3D RGB backbone pretrained on ImageNet and Kinetics-400
  • input: 64 RGB frames
  • self-attention block: additional Non-Local block 을 I3D top에 붙여서 구현
• test time
  • fully convolutional → final classification by max-pooling the softmax scores
  • only use RGB images

npm install --save mysql

var mysql = require('mysql');

var con = mysql.createConnection({
host: 'localhost',
port: 3306,
user:'root',
password: 'password',
database: 'database_name'
});

con.connect();

4. insert db

var sql = 'INSERT INTO table_name(?, ?) VALUES(?, ?)';

con.query(sql, function(err, rows, fields){ if(err){ console.log(err); }else{ console.log(rows.name); } });

5. table 초기화

truncate mollu;

npm update

npm install npm@latest -g   

package.json 생성

1. 수동 생성
npm init
2. 자동 생성 - 모든 것 default로 설정
npm init -y

npm install 로 package install

npm install

필요한 패키지 개별 install

npm install <pkg name>

https://www.acmicpc.net/problem/2792

풀이

# 보석상자
import math, sys
input = sys.stdin.readline
n, m = map(int, input().split())
color = [int(input()) for _ in range(m)]

start = 1
end = max(color)
result = 0
while start <= end:
    mid = (start+end)//2
    total = 0
    for c in color:
        total += math.ceil(c/mid)

    if total > n:
        start = mid + 1
    else:
        result = mid
        end = mid - 1

print(result)

접근

이분탐색을 이용한다.

https://www.acmicpc.net/problem/6603

풀이

# 로또
from itertools import combinations

while True:
    l = list(map(int, input().split()))
    if l[0] == 0:
        break

    s = l[1:]

    rotto = list(combinations(s,6))
    for r in rotto:
        print(' '.join(map(str, r)))

    print()

접근

combination을 이용해서 조합을 사용하여 풀었다. dfs를 재귀로 해서 풀어도 되는데 나중에 해야지.

https://www.acmicpc.net/problem/1049

풀이

# 기타줄
n, m = map(int, input().split())

six = []
one = []
for _ in range(m):
    x, y = map(int, input().split())
    six.append(x)
    one.append(y)

price = set([])
num = n // 6
for s in six:
    for o in one:
        for i in range(num+1):
            temp = 6*i
            price.add(s*i + o*(n-temp))
    if n%6 != 0:
        price.add(s*(num+1))

print(sorted(price)[0])

접근

6개 묶음의 가격과 낱개의 묶음을 따로 입력 받는다. 이중for문을 사용해 가능한 모든 경우의 조합을 다 계산하여 set에 넣는다. 중복 제거와 빠른 연산을 위해 set을 사용하였다. n이 6의 배수가 아닌 경우에만 모두 6개 묶음으로 선택하는 경우를 추가해준다. 가능한 모든 경우의 가격들을 정렬하여 가장 적은 값을 출력한다.

https://www.acmicpc.net/problem/1406

풀이

# 에디터
import sys
from collections import deque
input = sys.stdin.readline

left = deque(input())
right = deque()
m = int(input())
left.pop()
for _ in range(m):
    op = list(map(str, input().split()))
    if op[0] == 'P':
        left.append(op[1])
    elif op[0] == 'L':
        if left:
            right.appendleft(left.pop())
    elif op[0] == 'D':
        if right:
            left.append(right.popleft())
    else:
        if left:
            left.pop()
    print(left, right)
print(''.join(left)+''.join(right))

접근

커서를 직접 움직이는게 아니라 두개의 deque를 사용해서 커서를 기준으로 문자를 왼쪽 deque와 오른쪽 deque로 이동시킨다.

https://www.acmicpc.net/problem/2204

풀이

# 도비의 난독증 테스트
n = int(input())
while n:
  d = {}
  for _ in range(n):
    s = input()
    d[s.lower()] = s
  sortedDict = sorted(d.items())
  print(sortedDict[0][1])
  n = int(input())

접근

0을 입력 받기 전까지 계속 반복한다. 입력받은 n만큼 반복하면서 문자열을 입력받는다. dictionary 자료형을 이용하여 key값에는 입력받은 문자열을 모두 소문자로 변환하여 저장하고, value값에는 입력받은 문자열 그대로 저장한다. key값을 기준으로 dictionary를 정렬하고, 정렬된 리스트의 맨 첫 번째 원소의 value값을 출력한다. dicionary를 sorted함수를 활용해 정렬하면 반환되는 자료형이 list에 원소는 tuple 형태인 것을 주의하자!

https://www.acmicpc.net/problem/3182

풀이

#한동이는 공부가 하기 싫어!
n = int(input())
graph = [0]
result = [0]

for i in range(1, n+1):
  graph.append(int(input()))

def dfs(start):
  visited[start] = True
  if not visited[graph[start]]:
    dfs(graph[start])

for i in range(1, n+1):
  visited = [False] * (n+1)
  dfs(i)
  result.append(visited.count(True))

print(result.index(max(result)))

접근

어차피 한 선배당 한 명 밖에 지목을 못하기 때문에 1차원 리스트로 그래프를 만들고, dfs를 사용해서 시작점부터 어디까지 갈 수 있는지 체크를 한다음 방문한 노드의 개수를 result에 계속 append() 한다. 모든 각각의 노드에서 출발해서 갈 수 있는 노드의 개수를 result에 다 저장한 후에 result의 max값의 index를 출력한다. max값이 같은 것이 여러개인 경우 제일 작은 값을 출력하면 되기 때문에 index(max())를 사용하면 된다.

https://www.acmicpc.net/problem/11478

풀이

1. 다 쪼개서 set으로 중복 제거

#서로 다른 부분 문자열의 개수
s = input()
n = len(s)
count = 0
for i in range(1, n+1):
  compare = []
  for j in range(n-i+1):
    compare.append(s[j:j+i])
    temp = set(compare)
  count+=len(temp)
print(count)

접근

입력받은 문자열을 길이1부터 문자열 길이까지 길이를 1씩 늘려가면서 쪼개서 중복제거해서 중복 제거된 문자열 개수 넣고 그 갯수 카운팅해서 업데이트해주는거 반복함. 근데 다시생각해보니까 너무 비효율적임. dictionary 쓰면 시간 더 효율적으로 줄일 수 있을 듯. 다시 풀어서 업데이트 해야지.

2. dictionary를 사용해서 중복 제거

https://www.acmicpc.net/problem/1874

풀이

1. stack 범벅

#스택 수열
n = int(input())
num = [i for i in range(n, 0, -1)]

seq = [] #수열
oper = [] #push, pop 저장

for _ in range(n):
  seq.append(int(input()))

temp = list(reversed(seq))
seq = ''.join(str(_)for _ in seq)

stack1, stack2 = [], []
s = temp.pop()
stack1.append(num.pop())
oper.append("+")
while num:
  s1 = stack1.pop()
  if s != s1:
    stack1.append(s1)
    stack1.append(num.pop())
    oper.append("+")
  else:
    stack2.append(s1)
    s = temp.pop()
    oper.append("-")
    if len(stack1) == 0:
      stack1.append(num.pop())
      oper.append("+")

for i in stack1:
  oper.append("-")

reversedStack1 = list(reversed(stack1))
result = ''.join(str(_)for _ in stack2) + ''.join(str(_) for _ in reversedStack1)
#print(stack1, stack2)

if seq != result:
  print("NO")
else:
  for op in oper:
    print(op)

접근

stack 두 개를 써서 넣었다 뺐다 하면서 주어진 자연수를 다 쓸 때까지 반복함. 매칭된 스택이랑 매칭 안돼서 남은 스택 합쳐서 입력받은 스택이랑 같으면 +,- 출력 아니면 "NO" 출력함. 근데 그냥 deque로 해도 될 것 같다. 고쳐서 올려야지.

https://www.acmicpc.net/problem/2579

풀이

n = int(input())
stairs = [0]
score = [0] * (n+1) #편하게 하려고 앞에 0 냅두고 한 칸 더 만듦

for _ in range(n):
  stairs.append(int(input()))

#print(stairs)
score[1] = stairs[1]
if n == 1:
  print(score[n])
elif n == 2:
  score[2] = max(stairs[1]+stairs[2], stairs[2])
  print(score[n])
elif n == 3:
  score[2] = max(stairs[1]+stairs[2], stairs[2])
  score[3] = max(stairs[1]+ stairs[3], stairs[2]+ stairs[3])
  print(score[n])
else:
  score[2] = max(stairs[1]+stairs[2], stairs[2])
  score[3] = max(stairs[1]+ stairs[3], stairs[2]+ stairs[3])

  for i in range(4, n+1):
    score[i] = max(score[i-2]+stairs[i], score[i-3]+stairs[i-1]+stairs[i])

  print(score[n])

접근

마지막 계단은 무조건 밟아야 하고, 연속으로 3개의 계단을 밟을 수 없으므로 마지막 계단으로 갈 수 있는 방법은 2가지이다.

1. 마지막 계단 전 계단을 밟은 경우
2. 마지막 계단 전전 계단을 밟은 경우

1번의 경우 연속으로 3개의 계단을 밟을 수 없으므로 마지막 계단 전 계단 값 + 마지막 계단 전전전 계단까지의 최대값 + 마지막 계단 값 이다. 2번의 경우는 마지막 계단 전전 계단까지의 최대값 + 마지막 계단 값이다. 마지막 계단을 n번째 라고 할 때 다음과 같이 표현할 수 있다.(인덱스 1부터 시작이라고 할 때를 가정)

1. 최대값1[n] = 점수[n-1] + 최대값[n-3] + 점수[n]
2. 최대값2[n] = 최대값[n-2] + 점수[n]

최종적으로 최대값은 그 두 가지 방법의 최대값을 구하는 것이기 때문에 아래와 같이 표현할 수 있다.

최대값[n] = max(최대값1[n], 최대값2[n])

현재 값을 구하기 위해서는 그 전 값이 필요하기 때문에 DP(Dynamic Programming)으로 접근을 했다. 재귀 함수 호출식은 시간 초과가 일어날 가능성이 높기 때문에 단순 반복문을 사용하는 Bottom-up 형태로 구현함.

score[n] = max(score[n-3] + stair[n-1], score[n-2]) + stair[n]

근데 계속 런타임 에러로 IndexError가 나서 보니 n이 4보다 작은 경우들 각각에 대해 처리를 해주지 않았다. 각각의 경우는 그 뒤의 연산들이 index가 없어서 불가능하기 때문에 따로 처리해주어서 해결하였다.

https://www.acmicpc.net/problem/2606

풀이

from collections import deque

n = int(input())
pair = int(input())

computer = [[] for _ in range(n+1)] # 연결된 컴퓨터 그래프
visited = [0]*(n+1) # 감염된 컴퓨터인지 아닌지 확인하기 위한 방문 체크용

# 연결 쌍 입력받고 그래프 생성하기
for i in range(pair):
  p1, p2 = map(int, input().split())
  computer[p1].append(p2)
  computer[p2].append(p1)

# 처음 시작한 컴퓨터에 연결되어있는 컴퓨터들을 찾아야하므로 넓이우선탐색 적용
def bfs(start):
  result = 0
  queue = deque()
  queue.append(start)

  while queue:
    x = queue.popleft()
    visited[x] = 1
    for i in computer[x]:
      if not visited[i]:
        queue.append(i)

  for i in visited:
    if i:
      result += 1
  return result-1

print(bfs(1))

접근

처음 시작한 컴퓨터로부터 연결되어있는 노드들을 타고 갈 수 있는 최대한 멀리 가야하므로 넓이 우선 탐색 (BFS) 사용함. 처음 시작 노드를 큐에 넣고 큐에서 뺀 후에 방문 표시를 해준다. 큐에서 뺀 노드에 연결되어있는 노드들 중 아직 방문하지 않은 노드들을 큐에 넣는다. 큐가 빌 때 까지 반복한다. 방문하지 않은 노드는 시작 노드로부터 갈 수 없는 노드이기 때문에 바이러스에 감염되지 않은 노드이므로 마지막에 방문한 노드만 카운트한다.

https://www.acmicpc.net/problem/5397

풀이

1. list 1개

n = int(input()) #testcase number
testcase = []
for _ in range(n):
  testcase.append(input())
# lisf의 마지막 칸을 표시하기 위한 '/'
password = [['/']for _ in testcase]
print(password)

for i, L in zip(range(n), testcase):
  cursor = -1
  for s in L:
    if s=='<':
      if cursor>=0:
        cursor -= 1
    elif s=='>':
      if password[i][cursor+1] != '/':
        cursor += 1
    elif s=='-':
      if cursor>=0:
        del password[i][cursor]
        cursor -= 1
    else:
      cursor += 1
      password[i].insert(cursor, s)

for i in password:
  print(''.join(i[:-1]))

결과는 시간초과

2. list 2개

n = int(input())
testcase = []
for _ in range(n):
  testcase.append(input())

for L in testcase:
  stack1, stack2 = [], []
  for s in L:
    if s == '<':
      if stack1:
        stack2.append(stack1.pop())
    elif s == '>':
      if stack2:
        stack1.append(stack2.pop())
    elif s == '-':
      if stack1:
        stack1.pop()
    else:
      stack1.append(s)
  print(''.join(stack1)+''.join(reversed(stack2)))

접근

리스트 하나로 했을 때 시간초과가 떠서 커서를 중심으로 리스트를 두 개로 나눔. 처음에 리스트 하나로 할 때는 커서의 위치를 옮겼었는데 리스트 두 개로 할 때는 커서는 가만히 놔두고 커서를 중심으로 문자를 옮김. 리스트 두 개는 stack으로 해서 문자를 옮기기 편하게 함. 커서 오른쪽 stack은 마지막에 뒤집어서 합쳐줌.