대학교 3학년에 조교를 했던 교수님의 제안으로 그 해 겨울 방학 기간에 인턴을 시작하게 됐었다. 2022년 12월 19일부터 2023년 03월 29일까지 총 100일 정도의 인턴 생활을 했었다.

한창 졸업 후 대학원을 갈지, 회사를 다닐지 엄청 고민하던 때라 나에게는 회사 생활을 체험해 볼 수 있는 너무 좋은 기회가 되었다. 대학원 생활은 학부 연구생을 통하여 체험을 해봤었다. 인턴까지 해보고 이후에 내 진로의 확답을 주고 싶었다.

인턴을 하며 생각보다 많은 일들을 할 수 있었다. 내가 맡은 일은 Unity로 Hololens와 Nreal 기기에서 작동하는 재활 치료 프로그램에 합류하여 함께 콘텐츠 개발하는 일이었다.

Unity는 몇 년간 수도 없이 봐와서 익숙했지만 VR 기기는 처음이었다. 아니 학부 연구생을 하며 옆에서 제작하는 것을 봤어도 직접 만드는 것은 처음이었다.

처음 접하는 문제들

개발을 하며 나에게는 매번 처음 하게 되는 일들 천지였다. 맨 처음 맡은 일은 현재 Hololens로 돌아가는 프로그램을 Nreal로 돌리는 일이었다. Hololens도 처음인데 Nreal은 또 뭔지... 그 SDK가 있다는데 또 뭘 어떻게 써야 할지...

Nreal에서 로그인을 위해서 UUID를 가져오는 방식을 찾아보는 것도 맡았었는데 하다가 결국 실패했었다.

나는 처음 해보는 일을 접하고 개발하는 건 많이 해봐서 그냥 두 가지 생각을 갖고 임한다.

• 내가 발생하는 오류는 이미 누군가는 접했을 것이다.

내가 신대륙을 개척해나가는 일이 아닌 이상 누군가는 이미 밝은 발자국이 있을 것이다.

오류들을 구글링해 보면 대게 이미 그 오류를 접한 사람들이 있었다. 기존 프로젝트에 작성된 코드는 사수님께 물어보면 알 수 있었던 내용이었다.

나에게는 새로운 문제들이더라도 누군가에게는 익숙한 문제이며 어떤 사람들은 이미 그 지도를 그려놨을지도 모른다.

• 방법의 정답은 없다. 그저 최선책과 차선책들이 존재할 뿐이다.

게임 개발에 관한 비하인드 스토리를 본 적이 있다. 폴아웃 3에서 탈것을 만들 수 없어 기차를 머리에 씌워서 문제를 해결했다는 이야기다. (출처)

게임 개발에 있어서 어떻게 가든 목적지에만 잘 도착한다면 문제가 없다고 생각한다. 효율적인 방법으로 갈 줄 안다면 그것이야말로 게임 개발에서는 기술이고 테크닉이지 않을까...

어떤 문제를 접했을 때 여러 방안을 제시하고 그중 장단점으로 최선책과 차선책으로 나눠 테스트를 해보며 최선책이 실력이나 현 상황이나 어떤 문제로 불가능하다면 다른 차선책으로 구현하는 방식으로 해결했다.

배우고 성장한 점

• 기술적인 측면에서 배운 점

나는 인턴십을 하면서 100일이라는 시간 동안 코드 스타일이 또 한 번 대격변이 일어났다.

1. SDK를 사용하니 편했다.

Unity에서 Hololens2 콘텐츠를 만들려면 MRTK라는 SDK를 사용한다. Nreal 기기를 만들려면 MRTK에 NRSDK까지 추가하여 사용한다. 기존 나는 기본 Unity만 사용하다가 SDK를 사용하며 처음 접하는 새로운 기술들을 접하게 됐다.

SDK가 그저 누군가 이미 잘 만들어놓은 여러 코드와 리소스, 오브젝트, 프리팹 등이었고, 내가 원하는 기능들을 덧붙여서 만드는 기술이 필요했다.

마이크로소프트에서 작성해놓은 위키도 보며, 갑자기 나타난 버그들도 구글링해 보며, 사수님께 조언도 구하며 일들을 해결해나갔다.

SDK를 사용하면서 이 짤 이 생각났다. 우리가 개발을 하며 지금 해야 하는 일은 바퀴 하나부터 만드는 일이 아니고 이미 만들어진 서비스를 갖고 개선해 더 멋진 작품을 만드는 일이라는 것이다. 내가 무얼 만들 때 이미 만들어진 기술이 있는지 찾아보고 응용하는 능력을 키워야 할 것 같다.

2. 잘 작성된 다른 사람 코드를 모방하게 되었다.

첫날에는 이미 작성된 프로젝트의 코드를 사수님께서 하나하나 설명해 주셨다. 코드를 보며 감탄을 금치 못했다. 싱글톤이나 프로젝트를 분리하고 상속하며 열거형을 사용하고 등등 그냥 학교에서 배워서 알고 있는 내용을 응용하여 적용시킨 것이었다.

"내가 아는 식재료들로 이런 요리까지 가능하다고?" 하는 듯한 느낌이었다.

배울 게 있다면 내 것으로 흡수해야지! 그렇게 나는 그 코드 스타일에서 좋았다고 생각되는 점들을 모방하게 되었다.

그렇게 그 이후 첫 게임잼에 가서 다른 초보 개발자들에게 그런 코드 스타일을 보여줬다. 그분들도 내 첫날과 같은 반응을 하길래 엄청 웃겼었다.

3. 빌드가 시간은 오래걸려도 투자해야 한다.

노트북과 Hololens를 연동시켜 Unity에서 실행했을 때는 렉 안 걸렸는데 Hololens에 빌드 해서 했을 때는 렉 걸리고... Nreal은 노트북과 연결해서 실행하는 방법이 없다 보니 계속 빌드 하면서 실행해 봤고, 빌드 할 때마다 새로운 문제점들이 수도 없이 터져 나오고 끝없는 수정을 했었다.

과장님께서는 실제 실행할 환경에서 테스트를 해보는 것을 강조하셨다.

실제 환경은 얼마나 열악한지 좋은 컴퓨터로 작업하는 나는 몰랐다. 다 될 줄 알았지...

4. 렉과 최적화는 개발자만의 몫은 아니구나...

콘텐츠를 추가하고, 새로운 코드들과 오브젝트를 추가하다 보니 렉이 걸렸다. 나는 비효율적인 내 코드 때문인가? 싶어서 한참을 고민하고 어떻게 리팩토링을 해야 할지 생각했다.

계속 찾아보니 렉이 걸리는 이유가 간단한 3D 오브젝트였는데 삼각형 개수가 많아서 Unity에서 화면에 비치는 Triangle 수를 보니 million을 넘어가서 렉 걸리는 거였다...

렉이 그냥 Update 문에 비효율적인 코드 때려 박아서 걸리는 줄 알았는데 디자인도 매우 큰 부분을 차지한다는 것을 보고 최적화의 무겁던 무게를 약간 내려놓았다.

• 동료와의 협업에서 배운 점

누구든 배울점이 있었고 나에게 흡수하기 위해 노력했다.

1. 많이 물어보자...

인턴십을 하면서 모르는 거 투성이였다. Unity를 빼고 다 모르는 것들이었다. MR 기기도 처음이었고, SDK도 처음이었고, 회사 생활도 처음이었다.

모르는 게 많은 게... 아니 전부 모르는 게 당연한 거였다.

인턴십을 하면서 많은 일들을 물어봤고, 혼자 끙끙대며 해결해 보겠다고 붙잡아보기도 했다. 어느 날은 하루 종일 해결 못해 하루를 통째로 버리기도 했고, 계속 물어보느라 대화하다 하루가 끝난 날도 있었다.

이러면서 느낀 점은 물어보는 게 그래도 어떤 일을 해결하는 데 가장 빠른 일이라는 것이다. 질문이라는 것은 너 나 할 것 없이 모두가 했고, 협업에서의 질문은 모르는 것을 물어보는 부분보다 내 생각을 확인하고 이해하며 같은 방향으로 향하도록 하는 부분이 크다는 것을 느꼈다.

2. 문서가 있으니 편했다.

학교에서 프로젝트를 만들 때면 정형적인 문서가 많지 않다. 있더라도 관리가 안 되고 있거나, 틀린 정보들도 수두룩했다.

회사에서는 누군가 관리하고 편집하고 내용 수정되면 추가하여 공유하고 모르는 점들은 질문하며 생각을 공유할 수 있었다.

회사에서 쓰는 문서들의 용도나 방식을 배울 수 있어서 좋았다. 일단 뭐라도 확인하며 이게 맞는지 볼 수 있는 자료가 있어 개발하며 길을 헤매지 않았던 것 같다.

여러 문서들을 배우고 이번 졸업 작품에 적용해 볼까 한다. 이번에 졸업 작품에서 WBS를 작성할까 한다.

다시 한번 문서의 중요성을 느꼈다.

3. 매일매일 뭐 했는지 기록했다.

인턴을 하면서 매일매일 오전에는 뭐 했고, 오후에는 뭐 했고, 이슈 사항은 뭐가 있는지 기록했다. 이렇게 기록하고 주간 보고를 위하여 한 주를 돌아보면 한 주 만에 수많은 일들을 해왔다는 것을 알 수 있었다.

예전 개발했던 것들을 보며 "아 맞다! 이렇게 했었지!"라며 참고하기도 했고 해결한 일들을 보며 다음엔 뭘 해야 할지 방향을 잡기도 했다. 버그를 고쳤던 기록을 보며 똑같은 실수를 더 빠르게 해결했다.

최근부턴가 기록의 중요성을 느꼈다. 내 친구는 블로그를 관리하고, 게임잼에서 만난 어느 개발자분은 Unity에서 범주로 사용하는 기술들로 라이브러리를 만들고 있었다.

누군가가 그랬다. 기록이 없으면 안한 것과 다름없다고...

4. 배울 점은 업무와 관련된 것 외에 많다.

사수님께서 게임계의 해커톤인 게임잼을 알려주셨고 새로운 도전을 했었다. 덕분에 새로운 인맥을 얻었고 나의 실력을 볼 수 있었다.

대리님께서 좋은 회사의 조건들을 알려주셨다. 나중에 회사를 선택할 때 어떤 것들은 보면 좋을지, 뭘 주의해야 하는지...

과장님께서 책임감과 배려에 대하여 보여주셨다. 사소한 일에도 오해할 것 같아 배려해 주고 설명해 주시거나 자신의 일, 누군가 해야 하는 일까지도 책임감을 갖고 하시는 모습이 멋있었다.

이외에도 다른 사람들과의 협업에서는 혼자는 느끼지 못할 수많은 것들을 배울 수 있었다.

개선할 점과 앞으로의 계획

기록의 중요성, 협업의 장점, 커뮤니케이션의 효과 등 이번 100일간의 경험을 통하여 많은 것을 느꼈다.

글 쓰는 게 귀찮아서 중요하다는 것은 알고 있으나 실천을 안 하고 있었다. 귀찮아서... 방치해놨던 이 블로그에 다시 글을 열심히 끄적여보려 한다. 기록이 없으면 안한 것과 다름없으니 예전에 했던 일들도 차차 정리해 볼까 한다. 내가 들려주고 싶은 이야기는 수없이 많으니까!

혼자서만 개발하다가 같이 고민하고 의견을 나눌 수 있다는 것의 큰 이점을 이번 기회에 배울 수 있었다. 지금 계속 만들고 있는 졸업 작품에 어떻게 적용할 수 있을지 고민하는 계기가 되었다. 함께 프로젝트를 만들 때 우리에게 있어서 서로 대화하며 의견을 공유할 수 있는 시간이 많이 필요한 것 같다. 그래서 이번에 2주간 계속 붙어서 집중해서 졸업 작품 개발을 해볼까 한다.

끝으로

나는 어떤 새로운 시도를 할 때마다 많은 고민을 한다. 수많은 사람들에게 조언을 구하고 생각해 본다.

그러면서 하나 배운 점이 있다. 어느 누구에게 물어보든 "해보는 게 좋을 것 같다."라는 답변이 올 것 같으면 무조건 하는 게 맞는 것 같다.

그게 나에게 많이 껄끄럽거나 귀찮거나 힘들거나 스트레스를 많이 받을 수 있는 상황이라도...

이번 인턴도 그랬다. 새로운 시도는 언제나 많은 스트레스를 불러온다. 하나 그만큼 더 많은 것을 얻을 수 있다.

몹 충돌처리

체력바 UI 제작

임의로 체력바를 만들어줬다. Background UI에 hp icon이 총 3개 들어간다.

기초 오브젝트 호출

const player = getObject("player")  // Player Object
const ghosts = []                   // Monster Ghost Objects
const health = []                     // 체력 UI

// 1~3까지 순회하며 오브젝트를 찾아 배열에 추가해준다.
for (let i=1; i<=3; i++)  health.push(getObject("hp" + i))
for (let i=1; i<=10; i++) ghosts.push(getObject("ghost" + i))

각각 오브젝트가 따로 작동해야하기 때문에 이름을 달리하여 반복문으로 가져와준다.

충돌 감지도 각각 오브젝트마다 따로 설정해야한다. 한꺼번에 불러오니 충돌 발생 시 모든 오브젝트에 한꺼번에 이벤트가 실행됐었다...

기초 값 설정

// Variables
let hp = 3

현재 체력을 저장할 변수를 하나 설정해준다. 저 값으로 UI도 컨트롤할 것이다.

로직 코드

ghosts.forEach((ghost) => { // 배열 순회하며 실행
    ghost.onCollide(player, function() {  // 충돌 처리
        ghost.kill()        // 충돌된 유령 삭제
        health[--hp].hide() // 체력 1깎고 UI 숨기기
    })
})

충돌 처리 함수이다. 모든 오브젝트에 스크립트로 누구와 충돌됐을 시 어떤 코드가 실행될지 정의해 줘야 한다.

결과!

Unity에서는 transform.Lerp와 LookAt으로 이미 만들어져 있는 함수로 쉽게 구현이 가능하지만, RedBrick에서는 없기 때문에 만들어보자.

몹 따라오기

기초 몹 호출

몹을 따라오는 함수를 사용하려면 일단 몹을 불러와야 한다.

몬스터는 여러 마리 존재하기 때문에 배열로 호출하여 불러왔다. 따라갈 플레이어도 불러와준다.

const player = getObject("player")          // Player Object
const ghosts = getObjectsByName("ghost")    // Monster Ghost Objects

getObject(string)는 Title 기준으로 하나의 객체만 불러오고, getObjectsByName(string)은 Title 기준으로 동일한 친구들을 모두 불러온다.

코드 Ver 1.0

const speed = 10.0;

setInterval(() => 
{
    for (var i=0; i<ghosts.length; i++)
    {
        ghosts[i].moveX(player.getPosition().x - ghosts[i].getPosition().x, speed)
        ghosts[i].moveY(player.getPosition().y - ghosts[i].getPosition().y + 1, speed)
        ghosts[i].moveZ(player.getPosition().z - ghosts[i].getPosition().z, speed)
    }
})

움직이는 함수는 moveX(dx, speed), moveY(dy, speed), moveZ(dz, speed)를 사용하였다. 자신 위치를 기준으로 얼만큼(dx, dy, dz)을 몇의 속도(speed)로 움직인다.

goTo는 한번에 그 위치로 이동하는 함수여서 따로 또 Lerp값을 구해줘야해서 자신 기준으로 움직이는 함수를 사용하였다.

자신의 위치를 기준으로 플레이어의 방향으로 크기만큼 시간에 걸쳐 이동하게 된다.

문제점

이러면 몹들이 잘 따라오긴 하는데 문제점이 하나 생겼다. x, y, z 모두 동일한 속도로 이동하면 (a)와 같이 x 거리와 y 거리가 같다면 문제가 없지만 (b)와 같이 거리가 다르다면 x축을 먼저 모두 이동해버리고, y축을 이동하여 부자연스러운 느낌이 발생했다.

코드 Ver 2.0

function monsterFollow(monster)
{
  let _disX = player.getPosition().x - monster.getPosition().x
  let _disY = player.getPosition().y - monster.getPosition().y
  let _disZ = player.getPosition().z - monster.getPosition().z

  let _dis = abs(sqrt(_disX * _disX + _disY * _disY + _disZ * _disZ))

  monster.moveX(_disX     , abs(_disX) / _dis * monsterMoveSpeed)
  monster.moveY(_disY + 1 , abs(_disY) / _dis * monsterMoveSpeed) // +1 해줘야 몸을 타겟으로 따라감
  monster.moveZ(_disZ     , abs(_disZ) / _dis * monsterMoveSpeed)
}

사용이 쉽도록 함수로 묶어줬고, 속도에 플레이어까지 길이 비율을 곱했다. 길이가 짧으면 천천히가고, 길면 더 빨리 가도록 코드를 수정하여 해결하였다.

결과!

몹 따라오기 완성!

레드브릭에서 주최하는 공모전에 신청해서 참가 선정이 되었다!

이번 공모전의 주제는 하이퍼 캐주얼 게임이었다. 하이퍼 캐주얼이면... 조작감은 쉬워야 되고 뭔가 직관적이어야 된다고 생각했다.

그래서 어릴 때 재미있게 했던 "Tilt to live"라는 모바일 게임을 레드브릭 툴을 사용하여 만들어보려 했다.

빨간 점들이 따라와서 캐릭터를 잡고, 캐릭터는 움직이면서 아이템을 먹는다. 아이템마다 효과가 있고, 그 효과들로 빨간 점을 잡을 수 있게 된다.

2D의 모바일 게임을 3D의 레드브릭에서 구현하고, 빨간 점들은 유령으로 디자인을 바꿔 귀신 놀이동산으로 재탄생 시켰다.

유령을 피해서 제한 시간동안 살아남는 게임!

✅ 환경 세팅은 이전 글들을 확인해주세요!

SURF 알고리즘 코드

SURF 알고리즘은 크게 2가지의 과정으로 진행된다.

1. 각 이미지에서 키포인트를 검출한다!
2. 키포인트로 두 이미지를 매칭한다!

테스트 이미지는 같은 물체가 있는 각도가 다른 두 사진으로 진행하였다.

전체 코드

import cv2

# 이미지 불러오기 (확장자까지 적기!)
photo01 = cv2.imread("image01.jpg")
photo02 = cv2.imread("image02.jpg")

# 이미지가 너무 커서 사이즈 조절
photo01 = cv2.resize(photo01, (346, 462), cv2.INTER_LINEAR)
photo02 = cv2.resize(photo02, (346, 462), cv2.INTER_LINEAR)

# SURF 알고리즘 객체 생성 (500은 Threshold_임계값)
feature = cv2.xfeatures2d.SURF_create(500)

# 각 이미지에서 키포인트 추출
keyPoint01, descriptors01 = feature.detectAndCompute(photo01, None)
keyPoint02, descriptors02 = feature.detectAndCompute(photo02, None)

# Brute-force 방식으로 매칭
matcher = cv2.BFMatcher(cv2.NORM_L1, True)
matches = matcher.match(descriptors01, descriptors02)

# 키포인트 및 매칭 결과를 이미지에 그리기
keyPointImage01 = cv2.drawKeypoints(photo01, keyPoint01, None, None, cv2.DRAW_MATCHES_FLAGS_DEFAULT)
keyPointImage02 = cv2.drawKeypoints(photo02, keyPoint02, None, None, cv2.DRAW_MATCHES_FLAGS_DEFAULT)
matchImage = cv2.drawMatches(photo01, keyPoint01, photo02, keyPoint02, matches, None)

# 이미지 출력
cv2.imshow("keyPoint Image 01", keyPointImage01)
cv2.imshow("keyPoint Image 02", keyPointImage02)
cv2.imshow("match Image", matchImage)
cv2.waitKey(0)

일단 전체 코드를 확인하고 하나하나 분석을 해보자.

이미지 전처리 과정

# 이미지 불러오기 (확장자까지 적기!)
photo01 = cv2.imread("image01.jpg")
photo02 = cv2.imread("image02.jpg")

# 이미지가 너무 커서 사이즈 조절
photo01 = cv2.resize(photo01, (512, 512), cv2.INTER_LINEAR)
photo02 = cv2.resize(photo02, (512, 512), cv2.INTER_LINEAR)

이미지는 불러오자마자 쓸 수 있는 상태가 되면 더 없이 좋겠지만 아닐 가능성이 높다. 이미지가 너무 커서 불러와 한 번 조절하는 과정을 진행하였다.

※ 참조 : 두 이미지의 크기가 달라도 상관없다.

키포인트 추출

# SURF 알고리즘 객체 생성 (500은 Threshold_임계값)
feature = cv2.xfeatures2d.SURF_create(500)

# 각 이미지에서 키포인트 추출
keyPoint01, descriptors01 = feature.detectAndCompute(photo01, None)
keyPoint02, descriptors02 = feature.detectAndCompute(photo02, None)

왼쪽부터 임계값이 0일때, 500일때, 1000일때 이다.

SURF 알고리즘 객체를 생성할 때 값 안에 넣는 임계값에 따라 검출되는 키포인트 개수가 달라진다. 임계값이 높을수록! 키포인트 값이 높아야 하므로! 더 적은 키포인트가 검출된다.

• 임계값은 500정도가 적당한 개수의 키포인트가 검출된다.

이후 각 이미지에서 키포인트를 검출해주고 저장한다.

키포인트 매칭

# Brute-force 방식으로 매칭
matcher = cv2.BFMatcher(cv2.NORM_L1, True)
matches = matcher.match(descriptors01, descriptors02)

키포인트를 매칭할때는 Brute-force 방식으로 매칭한다. 각각 하나씩 대칭해보면서 가장 적절한 키포인트와 매칭하는 방식이다.

matcher.match()함수는 첫번째 키포인트들을 두번째 키포인트에 매칭하는 방식이다. 그래서 두 순서가 바뀐다면 값이 다르게 나올 수 있다!

키포인트 및 매칭 결과 그리기

# 키포인트 및 매칭 결과를 이미지에 그리기
keyPointImage01 = cv2.drawKeypoints(photo01, keyPoint01, None, None, cv2.DRAW_MATCHES_FLAGS_DEFAULT)
keyPointImage02 = cv2.drawKeypoints(photo02, keyPoint02, None, None, cv2.DRAW_MATCHES_FLAGS_DEFAULT)
matchImage = cv2.drawMatches(photo01, keyPoint01, photo02, keyPoint02, matches, None)

# 이미지 출력
cv2.imshow("keyPoint Image 01", keyPointImage01)
cv2.imshow("keyPoint Image 02", keyPointImage02)
cv2.imshow("match Image", matchImage)
cv2.waitKey(0)

이미지에 keyPoint를 그릴 때 cv2.drawKeypoints()를 사용 매칭된 결과를 그릴 때 cv2.drawMatches()를 사용

keyPoint 그리기

cv2.drawKeypoints(image: Mat, keypoints: Any, outImage: Any, color: ... = ..., flags: int = ...) drawKeypoints 함수의 형태이다.

• image : keyPoint를 그릴 원본 이미지
• keypoints : 검출한 키포인트 값
• outImage : 저장할 변수 (안할거면 None)
• color : 키포인트 색깔 (랜덤이면 None)
• flags : 값을 표현하는 방식에 대한 태그

color

좌측의 경우 랜덤 None, 우측의 경우 Cyan (255, 255, 0)

color의 경우 (blue, green, red)의 형태로 0~255를 넣으면 대응하는 색으로 키포인트가 표시된다. None으로 할 경우 각 키포인트마다 랜덤한 색이 부여된다.

flags

좌측의 경우 키포인트 위치만 출력 cv2.DRAW_MATCHES_FLAGS_NOT_DRAW_SINGLE_POINTS 우측의 경우 키포인트 크기와 방향까지 출력 cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS

flags에 cv2.DRAW_MATCHES_FLAGS_DEFAULT나 cv2.DRAW_MATCHES_FLAGS_NOT_DRAW_SINGLE_POINTS를 넣으면 위치 값만 보여주는 작은 점들로 그려진다. cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS를 넣으면 위치 뿐만 아니라 크기 및 방향까지 보여준다.

Matching 결과 그리기

cv2.drawMatches(img1, keypoints1, img2, keypoints2, matches1to2, outImg, matchColor=..., singlePointColor=..., matchesMask=..., flags: int = ...) drawMatches 함수의 형태이다.

• img1 : 매칭에 사용한 이미지 원본 1
• keypoints1 : img1의 키포인트
• img2 : 매칭에 사용한 이미지 원본 2
• keypoints2 : img2의 키포인트
• matches1to2 : 매칭 결과값
• outImg : 저장할 변수 (안할거면 None)
• matchColor : 매칭된 선 색깔 (랜덤이면 None)
• singlePointColor : 매칭되지 않은 키포인트 색깔 (랜덤이면 None)
• matchesMask : 매칭을 시도할 부분의 마스크 (값 없으면 모든 키포인트를 매칭)
• flags : 값을 표현하는 방식에 대한 태그

matchColor, singlePointColor

matchColor를 Cyan (255, 255, 0), singlePointColor를 Red (0, 0, 255)로 설정

매칭이 된 키포인트와 선은 matchColor가 되며, 매칭이 되지 않은 키포인트는 singlePointColor가 된다. 각각 None일 경우 랜덤한 색깔로 설정된다.

flags

flags는 총 3가지가 있다. DEFAULT, NOT_DRAW_SINGLE_POINTS, DRAW_RICH_KEYPOINTS

• DEFAULT 키포인트는 위치 값만, 모든 키포인트를 표현하는 방식

• NOT_DRAW_SINGLE_POINTS 매칭된 키포인트들만 표현하는 방식

• DRAW_RICH_KEYPOINTS 키포인트가 위치 뿐만 아니라 크기와 방향까지 표현하는 방식

SURF 알고리즘을 사용하려면 OpenCV 모듈을 사용해야 한다. 그리고 SURF 알고리즘이 특허가 걸려서 사용하기 위해서는 OpenCV 이전 버전을 사용해야 한다. 본 글에서는 OpenCV 및 SURF 알고리즘을 하기 위한 세팅 방법을 알아보자.

환경 세팅 방법

OpenCV는 Python, C++, C# 등 많은 언어로 모듈을 지원하고 있다. 그 중 환경 설정이 비교적 쉬운 Python으로 OpenCV 환경을 설정하는 방법을 알아보자.

Anaconda 설치

Anaconda Website Anaconda | The World's Most Popular Data Science Platform 아나콘다 웹 사이트로 들어가서 Download 버튼을 눌러 설치하면 된다.

실행하면 이런 창이 뜰 것이다. Click (Next >) Click (I Agree) Check (Just Me (recommended)) Click (Next >) Click (Next >)

만약 에러 창이 뜬다면! 1. Directory '경로' is not empty, please choose a different location.

• 아나콘다 설치는 빈 폴더에만 가능하다. 저 폴더에 뭔가 들어가 있다는 문제이니 폴더를 비우거나 새로운 폴더를 만들어서 경로를 변경해주면 해결 가능하다.

2. Error. Path 경로 is not writable. Please check permissions or try respawning the installer with elevated privileges.

• 경로에 파일 생성 권한이 없어서 설치를 못하는 문제다. 경로의 권한이 있는 곳에 폴더를 만들어 경로를 변경하고 설치하면 해결 가능하다.

고급 옵션들이나 OpenCV에서는 그냥 설치를 진행해보자. Click (Install)

이후에는 자동으로 설치가 진행된다.

가상환경 생성

설치가 완료되면 Anaconda Navigator를 실행시켜준다. 가상환경을 만들기 위해서는 옆의 Environments를 클릭 이런 창이 뜰 텐데 가상환경 별로 설치된 모듈을 볼 수 있는 창이다. 우리는 새로운 가상환경을 만들어야 하니 아래 Create를 클릭

가상환경을 만드는 이유!

• 하나의 컴퓨터에서 Python으로 머신러닝도 하고, OpenCV도 하고, 크롤링도 하고... 등등 여러 가지 작업을 할 수 있으므로 버전 관리와 모듈 관리를 위해서 가상환경을 만들어서 관리하는 것이 좋다.

Name : 가상환경의 이름 Packages : 프로그래밍 언어의 버전

이름은 자신이 알 수 있는 형태로 지어놓으면 되고, (ex. "OpenCV"나 "SURF" 등) 버전은 SURF 알고리즘을 사용하기 위해 Python 3.7.15로 설정하여 생성한다.

OpenCV 모듈 설치

SURF 알고리즘이 특허가 걸려서 사용하기 위해서는 OpenCV 이전 버전을 사용해야 한다.

이전 버전 친구들 다운로드 링크

• OpenCV_Python_3.4.2.16
• OpenCV_Contrib_Python_3.4.2.16

두 링크 다 들어가면 이런 형식의 사이트가 나올 것이다.

우리가 다운받아야 될 친구는

• opencv_python-3.4.2.16-cp37-cp37m-win_amd64.whl
• opencv_contrib_python-3.4.2.16-cp37-cp37m-win_amd64.whl

위 파일 이름의 뜻은 이것이다. (다른 친구를 다운받지 않도록 조심)

• 둘 다 동일한 버전 (3.4.2.16)
• 아까 설치한 python 3.7.15 버전(cp37)
• 운영체제 윈도우 (win_amd64)

다운을 받았다면 가상환경에 모듈을 설치해 보자. 다시 Anaconda Navigator를 켜주고, Environments를 들어가면 아까 만든 가상환경이 보일 것이다.

그 친구를 눌러주면 옆에 초록색 화살표가 생기는데 거기에 Open Terminal을 눌러준다. 그러면 이런 cmd 창이 뜰 것이다. (가상환경 이름) 경로> 우리는 다운로드한 whl 파일 두 개의 위치로 가서 설치를 해야 한다. cd 경로를 입력한다. (ex. 다운로드 폴더에 있으면 cd C:\Users\~\Downloads 이런 느낌으로 하면 된다.) 옆의 경로가 방금 입력한 경로로 변한 것을 볼 수 있다.

그럼 이제 다운받은 모듈들을 설치해 보자! (설치 순서도 동일하게 opencv_python을 먼저 설치해 준다.)

• pip install opencv_python-3.4.2.16-cp37-cp37m-win_amd64.whl
• pip install opencv_contrib_python-3.4.2.16-cp37-cp37m-win_amd64.whl

두 명령어를 복사하여 실행해주면 설치가 된다.

VS Code에서 Python 파일 생성

많은 IDE가 있겠지만 우리는 Visual Studio Code를 사용해 보자.

Visual Studio Code Website Visual Studio Code - Code Editing. Redefined 위의 링크에서 VS Code 다운로드 및 설치

VS Code를 실행시켜 옆의 네모 박스 쌓인 아이콘(Extensions)을 눌러 검색창에 python과 Code Runner를 검색하여 Install 해주고 VS Code를 껐다가 다시 실행해준다.

이후 File에서 New File로 Python 파일을 생성하거나 Open Folder로 폴더를 열 수 있다.

1. New File로 파일 생성

File → New File... → Python File 위 방식으로 누르면 Untitled-1 이름으로 파일이 생성될 것이다. 이때 꼭 Ctrl+S(저장하기)를 눌러서 원하는 위치에 저장하고 코드를 작성하는 것을 추천한다.

2. Open Folder로 폴더 열기

File → Open Folder... 위 방식으로 누르면 폴더를 선택할 수 있는 창이 뜬다. 이 때 파일을 관리할 폴더를 선택해준다. 폴더를 선택해주면 좌측 종이가 겹쳐 그려진 아이콘(Explorer)을 클릭하면 옆 창에 선택한 폴더 안 파일들이 보인다. (현재는 빈 폴더이므로 아무것도 안보인다.)

(현 사진에서는 Python이라는 이름의 폴더를 선택하였다.) 옆의 파일+ 아이콘을 눌러 파일을 추가하거나, 폴더+ 아이콘을 눌러 폴더를 추가하면 된다. ※ 파일 만들 때 ~.py 확장자까지 작성해야 파이썬 파일이 된다.

OpenCV 코드 테스트

import cv2

# 버전을 출력하는 코드
print(cv2.__version__)

위 코드를 작성하고 Ctrl+F5를 눌러 실행하면 아래와 같이 OpenCV 버전인 3.4.2가 출력되면 성공! 그리고 아래 빨간 박스를 보면 가상환경의 이름과 파이썬 버전이 보이는 것을 확인할 수 있다.

이후 SURF 알고리즘 코드를 작성하는 것은 다음 글에서 알아보자.

OpenCV 모듈 가져오기

import cv2

# 만약 ModuleNotFoundError가 날 경우, 하단 코드를 터미널에 입력
# pip install opencv-python

이미지 불러오기

기본 형태

cv2.imread(filename, flags='IMREAD_COLOR') ->    retval

• filename : 불러올 파일 경로
  • 파일의 경로는 상대 경로와 절대 경로 둘 다 가능합니다.
    • 상대 경로 : 실행되는 코드 기준으로 경로가 지정됩니다.
      • ex) filename = 'imagesFolder/flower.png'
    • 절대 경로 : 컴퓨터의 기준으로 경로가 지정됩니다.
      • ex) filename = 'C:/Users/Default/imagesFolder/flower.png'
• flags : 이미지 불러오는 모드 (기본값 : ‘IMREAD_COLOR’)
  • 이미지 불러오는 모드는 다양한 종류가 있지만 크게 두 종류가 있습니다.
    • IMREAD_COLOR : 컬러 색상으로 이미지를 불러옵니다.
    • IMREAD_GRAYSCALE : 회색조 색상으로 이미지를 불러옵니다.

※ 이미지를 읽을 수 없는 경우(파일 누락, 부적절한 권한, 지원되지 않거나 잘못된 형식으로 인해) 함수는 빈 행렬(NULL)을 반환합니다.

읽을 수 있는 파일 목록

• Windows 비트맵 - *.bmp, *.dib
• JPEG 파일 - *.jpeg, *.jpg, *.jpe
• JPEG 2000 파일 - *.jp2
• 휴대용 네트워크 그래픽 - *.png
• WebP - *.webp
• 휴대용 이미지 형식 - *.pbm, *.pgm, *.ppm *.pxm, *.pnm
• Sun 래스터 - *.sr, *.ras
• TIFF 파일 - *.tiff, *.tif
• OpenEXR 이미지 파일 - *.exr
• Radiance HDR - *.hdr, *.pic
• GDAL에서 지원하는 래스터 및 벡터 지리 공간 데이터

코드 사용 예시

import cv2 # OpenCV 모듈 불러오기

# 절대 경로로 바탕화면의 sky.jpg를 불러와 img 변수에 저장
img = cv2.imread('C:/Users/Default/Desktop/sky.jpg', cv2.IMREAD_COLOR)

이미지 출력

기본 형태

cv2.imshow(winname, mat) ->    None

• winname : 열리는 창의 이름
• mat : 출력할 이미지 Mat

코드 사용 예시

import cv2 # OpenCV 모듈 불러오기

# 절대 경로로 바탕화면의 sky.jpg를 불러와 img 변수에 저장
image1 = cv2.imread('C:/Users/Default/Desktop/sky.jpg', cv2.IMREAD_COLOR)

# 'this is sky'라는 창에 image1을 출력합니다.
cv2.imshow('this is sky', image1)
cv2.waitKey() # waitKey는 창을 확인하기 위하여 추가합니다. (없을시 코드가 바로 종료됩니다.)

이미지 크기 변경

기본 형태

cv.resize(src, dsize, fx = 0, fy = 0, interpolation = cv2.INTER_LINEAR) -> dst

• src : 크기를 변경할 이미지 Mat
• dsize : 변경할 이미지 절대 크기 (가로, 세로)
• fx : 가로 상대 크기 (기본 값 : 0)
• fy : 세로 상대 크기 (기본 값 : 0)
• interpolation : 보간법 (기본 값 : cv2.INTER_LINEAR)

| cv2.INTER_NEAREST | 최근접 이웃 보간 |
| --- | --- |
| cv2.INTER_LINEAR | 쌍선형 보간법 |
| cv2.INTER_LINEAR_EXACT | 비트 쌍 선형 보간법 |
| cv2.INTER_CUBIC | 바이큐빅 보간법 |
| cv2.INTER_AREA | 영역 보간법 |
| cv2.INTER_LANCZOS4 | Lanczos 보간법 |

※ dsize, fx, fy가 모두 0일 시 오류가 발생합니다.

※ 상대 크기로 변경하려면 절대 크기가 (0, 0) 이어야 합니다.

→ 상대 크기로 이미지 변경 후 절대 크기로 변경하는 순서이기 때문

코드 사용 예시

import cv2 # OpenCV 모듈 불러오기

# 절대 경로로 바탕화면의 sky.jpg를 불러와 img 변수에 저장
image1 = cv2.imread('C:/Users/Default/Desktop/sky.jpg', cv2.IMREAD_COLOR)

# image1의 크기를 512, 512로 변경하고 nowImage에 저장
nowImage = cv2.resize(image1, (512, 512), 0, 0, cv2.INTER_CUBIC)

# 'this is sky'라는 창에 image1을 출력합니다.
cv2.imshow('this is sky', nowImage)
cv2.waitKey() # waitKey는 창을 확인하기 위하여 추가합니다. (없을시 코드가 바로 종료됩니다.)

이미지 저장

기본 형태

cv2.imwrite(filename, img) -> retval

• filename : 저장할 파일 경로
  • 파일의 경로는 상대 경로와 절대 경로 둘 다 가능합니다.
    • 상대 경로 : 실행되는 코드 기준으로 경로가 지정됩니다.
      • ex) filename = 'imagesFolder/flower.png'
    • 절대 경로 : 컴퓨터의 기준으로 경로가 지정됩니다.
      • ex) filename = 'C:/Users/Default/imagesFolder/flower.png'
• img : 저장할 이미지 Mat

코드 사용 예시

import cv2

image1 = cv2.imread('C:/Users/Default/Desktop/sky.jpg', cv2.IMREAD_GRAYSCALE)
cv2.imwrite('graySky.png', image1)

참조

• https://076923.github.io/posts/Python-opencv-8/
• https://docs.opencv.org/3.4/

💡 논문 작성하며 공부했던 내용을 정리해 보았다!

SURF 알고리즘

SURF 알고리즘이란?

Speeded-Up Robust Features 알고리즘 특징점을 통하여 동일한 장면이나 물체를 찾는 알고리즘입니다.

기존 SIFT 알고리즘의 이미지 사이즈 변경시키며 특징점을 찾는 방식에서 박스 필터의 사이즈를 변경시키며 찾음으로써 시간을 단축시켜 더 빠른 성능의 알고리즘입니다.

SURF 알고리즘의 방식

1. SIFT vs SURF

SURF에서는 Gaussian filter 형태의 단순화한 Box filter를 사용하여 필터의 스케일을 키우면서 극점을 찾는다. 그래서 이미지 크기를 직접 줄이며 찾는 SIFT보다 필터의 사이즈를 늘리며 찾는 SURF가 3배 더 빠른 속도가 나온다.

2. Hessian Matrix

$$ H(x,y,\sigma)={D_{xx}(x,y,\sigma)D_{xy}(x,y,\sigma) \brack D_{xy}(x,y,\sigma)D_{yy}(x,y,\sigma)} $$

$$ det(H_{approx})=D_{xx}D_{yy}-(0.9D_{xy})^2 $$

가우시안 필터를 대체한 Box filter에서 Hessian Determinant 추출한다.

$$ w={{\vert L_{xy}(1.2) \vert F~ \vert D{yy}(9) \vert F} \over {\vert L{yy}(1.2) \vert F~ \vert D{xy}(9) \vert _F}}=0.912... \simeq 0.9 $$

(0.9를 곱하는 이유는 Box filter가 9x9, σ=1.2인 가우시안 2차 미분 함수에 대한 근사이기 때문이다.)

3. 특징점 추출

1. X 지점의 Hessian Determinant가 Threshold 보다 큰지 판별
2. 크다면 인접 8개의 픽셀보다 큰지 판별
3. 상하 박스 필터 사이즈의 3x3 범위와 비교하여 가장 클 경우 특징점으로 검출

4. 방향 할당 (Orientation Assignment)

반지름 6 scale 원 안에서 x및 y 방향으로 Haar-wavelet 응답(responses)의 합을 계산한 다음, 가장 큰 합을 가진 방향을 찾을 때까지 스캔 방향을 변경하고(+π/3, 60°) 다시 계산한다.

이 방향이 특징점의 주 방향 성분[fig.5 right]

5. 기술자 구성 요소 (Descriptor Components)

1. 특징점을 중심으로 이전 과정을 통해 얻은 방향을 따라 20 Scale 크기의 정사각형 영역을 구성한다.
2. 해당 영역은 균등하게 4x4 하위 영역으로 분할, 각 하위 영역에 대해 일정한 간격의 5x5 샘플 포인트에서 dx, dy 계산, 각 하위 영역은 각각의 기본 강도 구조인 V = (∑dx, ∑dy, ∑|dx|, ∑|dy|) 4x4x4 = 64 길이의 Descriptor 벡터 생성한다.

SURF 알고리즘의 특징

1. 물체의 기울기, 크기, 방향, 밝기 등의 차이에 영향이 적다.
   • 특이점을 찾고 그 특이점의 크기와 방향을 비교하다 보니 위의 변화에 비교적 적은 영향을 받는다.
2. 이미지의 크기가 다르더라도 매칭이 가능하다.
   • 박스 필터를 사용하여 특이점을 찾고 그 특이점을 통하여 매칭을 시도하다 보니 이미지의 크기가 달라도 문제가 되지 않는다.

참조

• Bay, H., Tuytelaars, T., Van Gool, L. (2006). SURF: Speeded Up Robust Features. In: Leonardis, A., Bischof, H., Pinz, A. (eds) Computer Vision – ECCV 2006. ECCV 2006. Lecture Notes in Computer Science, vol 3951. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/11744023_3
• Y. Do, Y. Jeong. “Hardware Design of SURF-based Feature extraction and description for Object Tracking” Journal of The Institute of Electronics Engineers of Korea, vol. 50, 5. DOI: https://doi.org/10.5573/ieek.2013.50.5.083

2751 - 수 정렬하기 2

#include <iostream>
#include <list>

using namespace std;

int main() {
    int times;
    list <int> numList;
    cin >> times;

    for (int i=0; i<times; i++) {
        int num;
        cin >> num;

        numList.push_back(num);
    }

    numList.sort();

    for (int n:numList)
        cout << n << "\n";

    return 0;
}

2869 - 달팽이는 올라가고 싶다

#include <iostream>

using namespace std;

int main() {
    int up, down, height;
    double days;
    cin >> up >> down >> height;

    days = double (height - down) / (up - down);

    cout << int(days) + ((int(days) != days) ? 1 : 0);

    return 0;
}

7568 - 덩치

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int times;
    cin >> times;

    vector <pair<int, int>> infoList;
    vector <int> rank(times, 1);

    for (int i=0; i<times; i++) {
        int weight, height;
        cin >> weight >> height;

        infoList.push_back({weight, height});
    }

    for (int i=0; i<times; i++) 
        for (int j=0; j<times; j++) 
            if (infoList[i].first < infoList[j].first && infoList[i].second < infoList[j].second)
                rank[i]++;

    for (int r:rank)
        cout << r << " ";


    return 0;
}

10814 - 나이순 정렬

#include <iostream>
#include <string>
#include <list>

using namespace std;

bool cmp(pair<pair<int, string>, int> user1, pair<pair<int, string>, int> user2) {
    if (user1.first.first != user2.first.first)
        return user1.first.first < user2.first.first;

    return user1.second < user2.second;
}

int main() {
    list <pair<pair<int, string>, int>> userList;
    int times;
    cin >> times;

    for (int i=0; i<times; i++) {
        int age;
        string name;
        cin >> age >> name;

        userList.push_back({{age, name}, i});
    }

    userList.sort(cmp);

    for (pair<pair<int, string>, int> u:userList)
        cout << u.first.first << " " << u.first.second << "\n";

    return 0;
}

11650 - 좌표 정렬하기

#include <iostream>
#include <list>

using namespace std;

bool cmp(pair<int, int> pos1, pair<int, int> pos2) {
    if (pos1.first != pos2.first)
        return pos1.first < pos2.first;

    return pos1.second < pos2.second;
}

int main() {
    list <pair<int, int>> posList;
    int times;
    cin >> times;

    for (int i=0; i<times; i++) {
        int x, y;
        cin >> x >> y;

        posList.push_back({x, y});
    }

    posList.sort(cmp);

    for (pair<int, int> p:posList)
        cout << p.first << " " << p.second << "\n";

    return 0;
}

10989 - 수 정렬하기 3

#include <iostream>
#include <vector>

using namespace std;

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int testCase;
    vector <int> numList(10001, 0);

    cin >> testCase;

    for (int i=0; i<testCase; i++) {
        int num;
        cin >> num;

        numList[num]++;
    }

    for (int i=1; i<=10000; i++)
        for (int j=0; j<numList[i]; j++) 
            cout << i << "\n";

    return 0;
}

11050 - 이항 계수 1

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, r, result = 1;
    cin >> n >> r;

    for (int i = n; i > 1; i--) {
        result *= i;

        if (i <= r)
            result /= i;

        if (i <= n - r)
            result /= i;
    }

    cout << result;

    return 0;
}

1181 - 단어 정렬

#include <iostream>
#include <string>
#include <list>

using namespace std;

bool cmp(string first, string second) {
    if (first.length() != second.length())
        return first.length() < second.length();

    return first < second;
}

int main() {
    list <string> strList;
    int num;

    cin >> num;

    for (int i=0; i<num; i++) {
        string str;
        cin >> str;

        strList.push_back(str);
    }

    strList.sort(cmp);
    strList.unique();

    for (string s:strList)
        cout << s << "\n";

    return 0;
}

1436 - 영화감독 숌

#include <iostream>
#include <string>

using namespace std;

int main() {
    int num, result = 665;
    cin >> num;

    while (num) {
        result++;

        if (to_string(result).find("666") != string::npos)
            num--;
    }

    cout << result;

    return 0;
}

1978 - 소수 찾기

#include <iostream>
#include <cmath>

using namespace std;

bool isPrime(int num) {
    if (num <= 1)
        return false;

    for (int i=2; i<=sqrt(num); i++)
        if (num % i == 0)
            return false;

    return true;
}

int main() {
    int times, result = 0;
    cin >> times;

    for (int i=0; i<times; i++) {
        int num;
        cin >> num;

        if (isPrime(num))
            result++;
    }

    cout << result;

    return 0;
}

2798 - 블랙잭

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int cardNum, limitScore, maxScore = 0;
    vector<int> cardList;

    cin >> cardNum >> limitScore;

    for (int i=0; i<cardNum; i++) {
        int card;
        cin >> card;

        cardList.push_back(card);
    }

    for (int i=0; i<cardNum-2; i++) {
        for (int j=i+1; j<cardNum-1; j++) {
            for (int k=j+1; k<cardNum; k++) {
                int cardSum = cardList[i] + cardList[j] + cardList[k];

                if (cardSum <= limitScore && cardSum > maxScore) 
                    maxScore = cardSum;
            }
        }
    }

    cout << maxScore << "\n";

    return 0;
}

15829 - Hashing

#include <iostream>
#include <string>

using namespace std;

int main() {
    int strLength;
    string inputStr;
    long long result = 0;
    long long primeNum = 1;

    cin >> strLength >> inputStr;

    for (int i = 0; i < strLength; i++) {
        int alphabetNum = inputStr[i] - 'a' + 1;

        result += alphabetNum * primeNum;
        result %= 1234567891;

        primeNum *= 31;
        primeNum %= 1234567891;
    }

    cout << result << "\n";

    return 0;
}

1259 - 팰린드롬수

#include <iostream>
#include <string>

using namespace std;

int main() {
    while (true) {
        int num;
        string numToStr;
        bool isPalindrome = true;

        cin >> num;

        if (num == 0)
            break;

        numToStr = to_string(num);

        for (int i=0; i<(numToStr.length() >> 1); i++) {
            int idxFront = i;
            int idxBack  = numToStr.length() - i - 1;

            if (numToStr[idxFront] != numToStr[idxBack]) {
                isPalindrome = false;
                break;
            }
        }

        cout << ((isPalindrome) ? "yes" : "no") << "\n";
    }

    return 0;
}

2609 - 최대공약수와 최소공배수

#include <iostream>
#include <numeric>

using namespace std;

int main() {
    int num1, num2;

    cin >> num1 >> num2;

    cout << gcd(num1, num2) << "\n" << lcm(num1, num2);

    return 0;
}

#include <iostream>

using namespace std;

int main() {
    int num1, num2;
    int gcd, lcm;

    cin >> num1 >> num2;

    if (num1 < num2) 
        swap(num1, num2);

    for (int i = num1; i >= 1; i--) {
        if (num1 % i == 0 && num2 % i == 0) {
            gcd = i;
            break;
        }
    }

    lcm = num1 * num2 / gcd;

    cout << gcd << "\n" << lcm;

    return 0;
}

2775 - 부녀회장이 될테야

#include <iostream>

using namespace std;

int main() {
    int testCase;

    cin >> testCase;

    for (int i=0; i<testCase; i++) {
        int floor, roomNumber;
        long long result = 1;

        cin >> floor >> roomNumber;

        for (int i = floor + roomNumber; i >= 2; i--) {
            result *= i;

            if (i <= roomNumber - 1)
                result /= i;

            if (i <= floor + 1)
                result /= i;
        }

        cout << result << "\n";
    }

    return 0;
}

1085 - 직사각형에서 탈출

#include <iostream>

using namespace std;

int main() {
    int x, y, w, h, result = 1000;
    cin >> x >> y >> w >> h;

      if (result > x) result = x;
    if (result > y) result = y;
    if (result > w-x) result = w-x;
    if (result > h-y) result = h-y;

    cout << result;

    return 0;
}

4153 - 직각삼각형

#include <iostream>

using namespace std;

int main() {
    while (true) {
        int side1, side2, hypotenuse;
        cin >> side1 >> side2 >> hypotenuse;

        if (side1 + side2 + hypotenuse == 0)
            break;

        if (hypotenuse < side1) {
            int num = side1;
            side1 = hypotenuse;
            hypotenuse = num;
        }

        if (hypotenuse < side2) {
            int num = side2;
            side2 = hypotenuse;
            hypotenuse = num;
        }

        cout << ((side1 * side1 + side2 * side2 == hypotenuse * hypotenuse) ? "right\n" : "wrong\n");
    }

    return 0;
}

10250 - ACM 호텔

#include <iostream>
#include <string>

using namespace std;

int main() {
    int times;
    cin >> times;

    for (int i=0; i<times; i++) {
        int h, w, n;
        cin >> h >> w >> n;

        string floor, room;

        room = to_string((n - 1) / h + 1);
        floor = to_string((n % h == 0) ? h : n % h) + ((room.length() != 2) ? "0" : "");

        cout << floor << room << "\n";
    }

    return 0;
}

2231 - 분해합

#include <iostream>

using namespace std;

int main() {
    int num, result = 0;
    cin >> num;

    for (int i=0; i<num; i++) {
        int nowValue = i;

        for (int j=i; j>0; j/=10) 
            nowValue += j % 10;

        if (nowValue == num) {
            result = i;
            break;
        }
    }

    cout << result;

    return 0;
}

2292 - 벌집

#include <iostream>

using namespace std;

int main() {
    int num;
    cin >> num;

    for (int i=1, maxRoom=1; maxRoom <= num; i++) 
        maxRoom += 6 * i;

    return 0;
}

여행경로

1차 시도

#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<string> BFS(unordered_map<string, unordered_multiset<string>> ticket_field, string prev_airport, string now_airport) {
    if (prev_airport.size()) {
        ticket_field[prev_airport].erase(ticket_field[prev_airport].find(now_airport));
    }

    vector<string> optimal_route;

    for (string next_airport:ticket_field[now_airport]) {
        vector<string> route = BFS(ticket_field, now_airport, next_airport);

        if (optimal_route.size() < route.size()) optimal_route = route;
        else if (optimal_route.size() == route.size()) {

            for (int i=0; i<optimal_route.size(); i++) {
                if (optimal_route[i] != route[i]) {
                    if (optimal_route[i] > route[i]) optimal_route = route;

                    break;
                }
            }
        }
    }

    optimal_route.insert(optimal_route.begin(), now_airport);

    return optimal_route;
}

vector<string> solution(vector<vector<string>> tickets) {
    unordered_map<string, unordered_multiset<string>> ticket_field;

    for (int i=0; i<tickets.size(); i++) {
        ticket_field[tickets[i][0]].insert(tickets[i][1]);
    }

    return BFS(ticket_field, "", "ICN");
}

정확성  테스트
  테스트 1 〉    통과 (297.06ms, 3.95MB)
  테스트 2 〉    통과 (0.02ms, 3.93MB)
  테스트 3 〉    통과 (0.02ms, 3.96MB)
  테스트 4 〉    통과 (0.02ms, 3.97MB)

채점 결과 정확성: 100.0 합계: 100.0 / 100.0

이분탐색

입국심사

1차 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());

    long long left = 1, right = (long long)n * (long long)times.back(), mid = (left + right)>>1;

    while (left < right) {
        long long check_people = 0;
        bool isMultiple = false;

        for (int t:times) {
            check_people += mid / t;

            if (mid % t == 0) isMultiple = true;

            if (check_people > n) break;
        }

        if (check_people > n) {
            right = mid;
        } else if (check_people < n) {
            left = mid + 1;
        } else if (!isMultiple) {
            left--;
            right--;
        } else break;

        mid = (left + right)>>1;
    }

    return mid;
}

정확성  테스트
  테스트 1 〉    통과 (0.01ms, 3.97MB)
  테스트 2 〉    통과 (0.02ms, 3.89MB)
  테스트 3 〉    통과 (343.67ms, 3.94MB)
  테스트 4 〉    통과 (338.15ms, 6.8MB)
  테스트 5 〉    통과 (200.64ms, 6.88MB)
  테스트 6 〉    통과 (30.10ms, 6.54MB)
  테스트 7 〉    통과 (518.44ms, 6.74MB)
  테스트 8 〉    통과 (2854.43ms, 6.86MB)
  테스트 9 〉    통과 (0.01ms, 3.95MB)

채점 결과 정확성: 100.0 합계: 100.0 / 100.0

```

네트워크

1차 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> computers) {
    vector <int> networks;
    for (int i=0; i<n; i++) networks.push_back(i);

    for (int i=0; i<computers.size(); i++) {
        for (int j=i+1; j<computers.size(); j++) {
            if (computers[i][j]) {
                int base_network = networks[i];
                int replace_network = networks[j];

                for (int k=0; k<networks.size(); k++) {
                    if (networks[k] == replace_network) networks[k] = base_network;
                }
            }
        }
    }

    sort(networks.begin(), networks.end());
    auto iter = unique(networks.begin(), networks.end());
    networks.erase(iter, networks.end());

    return networks.size();
}

정확성  테스트
  테스트 1 〉    통과 (0.01ms, 3.95MB)
  테스트 2 〉    통과 (0.01ms, 3.94MB)
  테스트 3 〉    통과 (0.01ms, 3.96MB)
  테스트 4 〉    통과 (0.02ms, 3.89MB)
  테스트 5 〉    통과 (0.01ms, 3.93MB)
  테스트 6 〉    통과 (0.04ms, 3.89MB)
  테스트 7 〉    통과 (0.01ms, 3.93MB)
  테스트 8 〉    통과 (0.02ms, 3.93MB)
  테스트 9 〉    통과 (0.02ms, 3.89MB)
  테스트 10 〉    통과 (0.02ms, 3.93MB)
  테스트 11 〉    통과 (0.06ms, 4.01MB)
  테스트 12 〉    통과 (0.05ms, 3.88MB)
  테스트 13 〉    통과 (0.03ms, 3.94MB)

채점 결과 정확성: 100.0 합계: 100.0 / 100.0

단어 변환

1차 시도

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

int DFS(string begin, string target, vector<string> words, unordered_set<string> checked, int dipth) {
    if (words.size() < dipth) return 0;

    checked.insert(begin);

    for (int i=0; i<words.size(); i++) {
        if (checked.find(words[i]) != checked.end()) continue;

        int canReplace = 0;

        for (int j=0; j<begin.length(); j++) {
            if (begin[j] != words[i][j]) canReplace++;

            if (canReplace > 1) break;
        }

        if (canReplace == 1) {
            if (words[i] == target) return dipth;

            int s = DFS(words[i], target, words, checked, dipth + 1);
            if (s != 0) return s;
        }
    }

    return 0;
}

int solution(string begin, string target, vector<string> words) {
    return DFS(begin, target, words, {}, 1);
}

정확성  테스트
  테스트 1 〉    통과 (0.01ms, 3.94MB)
  테스트 2 〉    통과 (0.01ms, 3.96MB)
  테스트 3 〉    통과 (0.03ms, 3.95MB)
  테스트 4 〉    통과 (0.01ms, 3.95MB)
  테스트 5 〉    통과 (0.01ms, 3.72MB)

채점 결과 정확성: 100.0 합계: 100.0 / 100.0

테스트 1
  입력값 〉    "hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]
  기댓값 〉    4
  실행 결과 〉    실행한 결괏값 5이(가) 기댓값 4와(과) 다릅니다.
테스트 2
  입력값 〉    "hit", "cog", ["hot", "dot", "dog", "lot", "log"]
  기댓값 〉    0
  실행 결과 〉    테스트를 통과하였습니다.
테스트 3
  입력값 〉    "hit", "cog", ["cog", "log", "lot", "dog", "hot"]
  기댓값 〉    4
  실행 결과 〉    테스트를 통과하였습니다.
테스트 4
  입력값 〉    "1234567000", "1234567899", ["1234567800", "1234567890", "1234567899"]
  기댓값 〉    3
  실행 결과 〉    테스트를 통과하였습니다.
테스트 5
  입력값 〉    "hit", "hot", ["hot", "dot", "dog", "lot", "log"]
  기댓값 〉    1
  실행 결과 〉    테스트를 통과하였습니다.
테스트 6
  입력값 〉    "hot", "dog", ["hot", "dog"]
  기댓값 〉    0
  실행 결과 〉    테스트를 통과하였습니다.

테스트 결과 (˘▾˘) 6개 중 5개 성공

2차 시도

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

int BFS(string begin, string target, vector<string> words, unordered_set<string> checked, int dipth) {
    if (words.size() < dipth) return 0;

    int min = words.size()+1;

    checked.insert(begin);

    for (int i=0; i<words.size(); i++) {
        if (checked.find(words[i]) != checked.end()) continue;

        int canReplace = 0;

        for (int j=0; j<begin.length(); j++) {
            if (begin[j] != words[i][j]) canReplace++;

            if (canReplace > 1) break;
        }

        if (canReplace == 1) {
            if (words[i] == target) return dipth;

            int value = BFS(words[i], target, words, checked, dipth + 1);

            if (value != 0 && min > value) min = value;
        }
    }

    return (min != words.size()+1) ? min : 0;
}

int solution(string begin, string target, vector<string> words) {
    return BFS(begin, target, words, {}, 1);
}

정확성  테스트
  테스트 1 〉    통과 (0.01ms, 3.76MB)
  테스트 2 〉    통과 (0.02ms, 3.96MB)
  테스트 3 〉    통과 (0.04ms, 3.72MB)
  테스트 4 〉    통과 (0.01ms, 3.95MB)
  테스트 5 〉    통과 (0.01ms, 3.95MB)

채점 결과 정확성: 100.0 합계: 100.0 / 100.0

```

도둑질

1차 시도

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> money) {
    vector<int> money_reverse(money.rbegin(), money.rend());
    int forward = 0, reverse = 0;

    for (int i=0; i<money.size()-1; i += 2) {
        int now_choice = money[i] - (money[(i-1+money.size())%money.size()] + money[(i+1)%money.size()]);
        int next_choice = money[i+1] - (money[i] + money[(i+2)%money.size()]);

        if (now_choice > next_choice) {
            if (i==0) money.back() = 0;
            forward += money[i];
        } else {
            if (i==0) money.push_back(0);
            forward += money[i+1];
            i++;
        }
    } 

    for (int i=0; i<money_reverse.size()-1; i += 2) {
        int now_choice = money_reverse[i] - (money_reverse[(i-1+money_reverse.size())%money_reverse.size()] + money_reverse[(i+1)%money_reverse.size()]);
        int next_choice = money_reverse[i+1] - (money_reverse[i] + money_reverse[(i+2)%money_reverse.size()]);

        if (now_choice > next_choice) {
            if (i==0) money_reverse.back() = 0;
            reverse += money_reverse[i];
        } else {
            if (i==0) money_reverse.push_back(0);
            reverse += money_reverse[i+1];
            i++;
        }
    } 

    return (forward > reverse) ? forward : reverse;
}

정확성  테스트
  테스트 1 〉    실패 (0.02ms, 3.94MB)
  테스트 2 〉    실패 (0.04ms, 3.75MB)
  테스트 3 〉    실패 (0.02ms, 3.95MB)
  테스트 4 〉    실패 (0.01ms, 3.95MB)
  테스트 5 〉    실패 (0.01ms, 3.96MB)
  테스트 6 〉    실패 (0.03ms, 3.95MB)
  테스트 7 〉    실패 (0.02ms, 3.96MB)
  테스트 8 〉    실패 (0.01ms, 3.93MB)
  테스트 9 〉    실패 (0.06ms, 3.94MB)
  테스트 10 〉    실패 (0.01ms, 3.93MB)

효율성 테스트 테스트 1 〉 실패 (25.73ms, 40.6MB) 테스트 2 〉 실패 (24.14ms, 38.2MB) 테스트 3 〉 실패 (26.67ms, 39.6MB) 테스트 4 〉 실패 (38.17ms, 40MB) 테스트 5 〉 실패 (22.08ms, 33.6MB) 테스트 6 〉 실패 (25.48ms, 38.5MB) 테스트 7 〉 실패 (13.05ms, 22MB) 테스트 8 〉 실패 (15.51ms, 24.5MB) 테스트 9 〉 실패 (16.73ms, 28.2MB) 테스트 10 〉 실패 (26.07ms, 38.8MB)

채점 결과 정확성: 0.0 효율성: 0.0 합계: 0.0 / 100.0

테스트 1
  입력값 〉    [1, 2, 3, 1]
  기댓값 〉    4
  실행 결과 〉    테스트를 통과하였습니다.
테스트 2
  입력값 〉    [90, 0, 0, 95, 1, 1]
  기댓값 〉    185
  실행 결과 〉    테스트를 통과하였습니다.
테스트 3
  입력값 〉    [91, 90, 5, 7, 5, 7]
  기댓값 〉    104
  실행 결과 〉    테스트를 통과하였습니다.
테스트 4
  입력값 〉    [90, 0, 0, 95, 1, 1]
  기댓값 〉    185
  실행 결과 〉    테스트를 통과하였습니다.
테스트 5
  입력값 〉    [91, 90, 5, 7, 5, 7]
  기댓값 〉    104
  실행 결과 〉    테스트를 통과하였습니다.
테스트 6
  입력값 〉    [1, 2, 3]
  기댓값 〉    3
  실행 결과 〉    테스트를 통과하였습니다.
테스트 7
  입력값 〉    [11, 0, 2, 5, 100, 100, 85, 1]
  기댓값 〉    198
  실행 결과 〉    테스트를 통과하였습니다.
테스트 8
  입력값 〉    [0, 0, 0, 0, 100, 0, 0, 100, 0, 0, 1, 1]
  기댓값 〉    201
  실행 결과 〉    테스트를 통과하였습니다.
테스트 9
  입력값 〉    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  기댓값 〉    30
  실행 결과 〉    테스트를 통과하였습니다.
테스트 10
  입력값 〉    [1000, 0, 0, 0, 0, 1000, 0, 0, 0, 0, 0, 1000]
  기댓값 〉    2000
  실행 결과 〉    테스트를 통과하였습니다.
테스트 11
  입력값 〉    [1000, 1, 0, 1, 2, 1000, 0]
  기댓값 〉    2001
  실행 결과 〉    테스트를 통과하였습니다.
테스트 12
  입력값 〉    [1000, 0, 0, 1000, 0, 0, 1000, 0, 0, 1000]
  기댓값 〉    3000
  실행 결과 〉    테스트를 통과하였습니다.
테스트 13
  입력값 〉    [1, 1, 4, 1, 4]
  기댓값 〉    8
  실행 결과 〉    테스트를 통과하였습니다.

테스트 결과 (˘▾˘) 13개 중 13개 성공

2차 시도

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> money) {
    vector <int> stolen_first_house = {money[0], money[0]};
    vector <int> stolen_second_house = {0, money[1]};

    for (int i=2; i<money.size()-1; i++) {
        if (stolen_first_house[i-2] + money[i] > stolen_first_house[i-1]) {
            stolen_first_house.push_back(stolen_first_house[i-2] + money[i]);
        } else {
            stolen_first_house.push_back(stolen_first_house[i-1]);
        }
    }

    for (int i=2; i<money.size(); i++) {
        if (stolen_second_house[i-2] + money[i] > stolen_second_house[i-1]) {
            stolen_second_house.push_back(stolen_second_house[i-2] + money[i]);
        } else {
            stolen_second_house.push_back(stolen_second_house[i-1]);
        }
    }

    return (stolen_first_house[money.size()-2] > stolen_second_house[money.size()-1]) ? stolen_first_house[money.size()-2] : stolen_second_house[money.size()-1];
}

정확성  테스트
  테스트 1 〉    통과 (0.02ms, 3.95MB)
  테스트 2 〉    통과 (0.02ms, 3.89MB)
  테스트 3 〉    통과 (0.02ms, 3.96MB)
  테스트 4 〉    통과 (0.01ms, 3.95MB)
  테스트 5 〉    통과 (0.01ms, 3.96MB)
  테스트 6 〉    통과 (0.02ms, 3.96MB)
  테스트 7 〉    통과 (0.02ms, 3.89MB)
  테스트 8 〉    통과 (0.02ms, 3.96MB)
  테스트 9 〉    통과 (0.03ms, 3.9MB)
  테스트 10 〉    통과 (0.01ms, 3.95MB)

효율성 테스트 테스트 1 〉 통과 (16.82ms, 43MB) 테스트 2 〉 통과 (15.77ms, 40.7MB) 테스트 3 〉 통과 (16.89ms, 42.2MB) 테스트 4 〉 통과 (17.35ms, 42.6MB) 테스트 5 〉 통과 (14.33ms, 36.9MB) 테스트 6 〉 통과 (15.50ms, 41.2MB) 테스트 7 〉 통과 (9.06ms, 24.9MB) 테스트 8 〉 통과 (9.04ms, 25.6MB) 테스트 9 〉 통과 (12.94ms, 31.8MB) 테스트 10 〉 통과 (16.32ms, 41.6MB)

채점 결과 정확성: 50.0 효율성: 50.0 합계: 100.0 / 100.0

깊이/너비 우선 탐색(DFS/BFS)

타겟 넘버

1차 시도

#include <string>
#include <vector>

using namespace std;

int DFS(vector<int> numbers, int target, int now_number, int depth) {
    if (depth == numbers.size()) {
        return (now_number == target) ? true : false;
    }

    int plus = DFS(numbers, target, now_number + numbers[depth], depth + 1);
    int minus = DFS(numbers, target, now_number - numbers[depth], depth + 1);

    return plus + minus;
}

int solution(vector<int> numbers, int target) {
    return DFS(numbers, target, 0, 0);
}

정확성  테스트
  테스트 1 〉    통과 (65.63ms, 3.82MB)
  테스트 2 〉    통과 (69.89ms, 3.97MB)
  테스트 3 〉    통과 (0.08ms, 3.93MB)
  테스트 4 〉    통과 (0.31ms, 3.96MB)
  테스트 5 〉    통과 (2.23ms, 3.96MB)
  테스트 6 〉    통과 (0.16ms, 3.94MB)
  테스트 7 〉    통과 (0.08ms, 3.94MB)
  테스트 8 〉    통과 (0.64ms, 3.95MB)

채점 결과 정확성: 100.0 합계: 100.0 / 100.0

```

정수 삼각형

1차 시도

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;

    for (int i=1; i<triangle.size(); i++) {
        triangle[i][0] += triangle[i-1][0];

        for (int j=1; j<triangle[i].size()-1; j++) {
            triangle[i][j] += (triangle[i-1][j-1] > triangle[i-1][j]) ? triangle[i-1][j-1] : triangle[i-1][j];
        }

        triangle[i][triangle[i].size()-1] += triangle[i-1][triangle[i-1].size()-1];
    }

    for (int n:triangle[triangle.size()-1]) {
        if (answer < n) answer = n;
    }

    return answer;
}

정확성  테스트
  테스트 1 〉    통과 (0.01ms, 3.97MB)
  테스트 2 〉    통과 (0.01ms, 3.97MB)
  테스트 3 〉    통과 (0.01ms, 3.97MB)
  테스트 4 〉    통과 (0.01ms, 3.95MB)
  테스트 5 〉    통과 (0.02ms, 3.97MB)
  테스트 6 〉    통과 (0.01ms, 3.92MB)
  테스트 7 〉    통과 (0.03ms, 3.96MB)
  테스트 8 〉    통과 (0.02ms, 3.96MB)
  테스트 9 〉    통과 (0.01ms, 3.91MB)
  테스트 10 〉    통과 (0.01ms, 3.94MB)

효율성 테스트 테스트 1 〉 통과 (0.28ms, 7.6MB) 테스트 2 〉 통과 (0.23ms, 6.55MB) 테스트 3 〉 통과 (0.31ms, 8.09MB) 테스트 4 〉 통과 (0.31ms, 7.82MB) 테스트 5 〉 통과 (0.28ms, 7.29MB) 테스트 6 〉 통과 (0.30ms, 8.39MB) 테스트 7 〉 통과 (0.33ms, 8.08MB) 테스트 8 〉 통과 (0.24ms, 7.13MB) 테스트 9 〉 통과 (0.28ms, 7.26MB) 테스트 10 〉 통과 (0.32ms, 7.84MB)

채점 결과 정확성: 64.3 효율성: 35.7 합계: 100.0 / 100.0

등굣길

1차 시도

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    vector<vector<int>> field(m, vector<int> (n, 1));

    for (auto p:puddles) field[p[0]-1][p[1]-1] = 0;

    for (int i=1; i<m; i++) {
        for (int j=1; j<n; j++) {
            if (field[i][j] == 0) continue;
            field[i][j] = field[i-1][j] + field[i][j-1];
        }
    }

    return field[m-1][n-1];
}

정확성  테스트
  테스트 1 〉    실패 (0.01ms, 3.96MB)
  테스트 2 〉    통과 (0.01ms, 3.96MB)
  테스트 3 〉    통과 (0.01ms, 3.98MB)
  테스트 4 〉    통과 (0.01ms, 3.96MB)
  테스트 5 〉    통과 (0.01ms, 3.9MB)
  테스트 6 〉    통과 (0.01ms, 3.97MB)
  테스트 7 〉    통과 (0.01ms, 3.92MB)
  테스트 8 〉    통과 (0.01ms, 3.89MB)
  테스트 9 〉    실패 (0.01ms, 3.98MB)
  테스트 10 〉    실패 (0.01ms, 3.8MB)

효율성 테스트 테스트 1 〉 실패 (0.04ms, 3.96MB) 테스트 2 〉 실패 (0.02ms, 3.95MB) 테스트 3 〉 실패 (0.02ms, 3.92MB) 테스트 4 〉 실패 (0.03ms, 3.96MB) 테스트 5 〉 실패 (0.03ms, 3.98MB) 테스트 6 〉 실패 (0.04ms, 3.96MB) 테스트 7 〉 실패 (0.02ms, 3.92MB) 테스트 8 〉 실패 (0.03ms, 3.97MB) 테스트 9 〉 실패 (0.04ms, 3.96MB) 테스트 10 〉 실패 (0.03ms, 3.96MB)

채점 결과 정확성: 35.0 효율성: 0.0 합계: 35.0 / 100.0

2차 시도

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    vector<vector<long long>> field(m, vector<long long> (n, 1));

    for (auto p:puddles) {
        field[p[0]-1][p[1]-1] = 0;

        if (p[0]-1 == 0) for (int i=p[1]; i<n; i++) field[p[0]-1][i] = 0;
        if (p[1]-1 == 0) for (int i=p[0]; i<m; i++) field[i][p[1]-1] = 0;
    }

    for (int i=1; i<m; i++) {
        for (int j=1; j<n; j++) {
            if (field[i][j] == 0) continue;
            field[i][j] = (field[i-1][j] + field[i][j-1]) % 1000000007;
        }
    }

    return field[m-1][n-1];
}

정확성  테스트
  테스트 1 〉    통과 (0.01ms, 3.93MB)
  테스트 2 〉    통과 (0.01ms, 3.92MB)
  테스트 3 〉    통과 (0.01ms, 3.96MB)
  테스트 4 〉    통과 (0.01ms, 3.95MB)
  테스트 5 〉    통과 (0.01ms, 3.95MB)
  테스트 6 〉    통과 (0.01ms, 3.92MB)
  테스트 7 〉    통과 (0.01ms, 3.96MB)
  테스트 8 〉    통과 (0.01ms, 3.89MB)
  테스트 9 〉    통과 (0.01ms, 3.96MB)
  테스트 10 〉    통과 (0.01ms, 3.9MB)

효율성 테스트 테스트 1 〉 통과 (0.08ms, 3.96MB) 테스트 2 〉 통과 (0.03ms, 3.79MB) 테스트 3 〉 통과 (0.04ms, 3.72MB) 테스트 4 〉 통과 (0.05ms, 3.96MB) 테스트 5 〉 통과 (0.05ms, 3.73MB) 테스트 6 〉 통과 (0.08ms, 3.96MB) 테스트 7 〉 통과 (0.04ms, 3.91MB) 테스트 8 〉 통과 (0.06ms, 3.94MB) 테스트 9 〉 통과 (0.06ms, 3.97MB) 테스트 10 〉 통과 (0.06ms, 3.97MB)

채점 결과 정확성: 50.0 효율성: 50.0 합계: 100.0 / 100.0

```

단속카메라

1차 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> routes) {

    sort(routes.begin(), routes.end());

    vector<vector<int>> camera = {routes.front()};

    for (int i=1; i < routes.size(); i++) {

        if (camera.back()[1] < routes[i][0]) {
            camera.push_back(routes[i]);
            continue;
        }

        if (camera.back()[0] < routes[i][0]) camera.back()[0] = routes[i][0];
        if (camera.back()[1] > routes[i][1]) camera.back()[1] = routes[i][1];
    }

    return camera.size();
}

정확성  테스트
  테스트 1 〉    통과 (0.02ms, 3.94MB)
  테스트 2 〉    통과 (0.01ms, 3.99MB)
  테스트 3 〉    통과 (0.02ms, 3.77MB)
  테스트 4 〉    통과 (0.02ms, 3.95MB)
  테스트 5 〉    통과 (0.02ms, 3.9MB)

효율성 테스트 테스트 1 〉 통과 (0.26ms, 3.95MB) 테스트 2 〉 통과 (0.14ms, 3.99MB) 테스트 3 〉 통과 (0.60ms, 3.97MB) 테스트 4 〉 통과 (0.03ms, 3.97MB) 테스트 5 〉 통과 (0.63ms, 3.95MB)

채점 결과 정확성: 50.0 효율성: 50.0 합계: 100.0 / 100.0

동적계획법(Dynamic Programming)

N으로 표현

1차 시도

#include <string>
#include <vector>

using namespace std;

int recursive(int N, int now_number, int number, int times) {
    if (times > 8 || now_number <= 0) return 9;
    if (now_number == number) return times;

    string N_type = to_string(N);

    int now_times = 9;

    for (int i=0; i<to_string(number).size(); i++) {
        int Plus = recursive(N, now_number + stoi(N_type), number, times + N_type.size());
        int Minus = recursive(N, now_number - stoi(N_type), number, times + N_type.size());
        int Multiplication = recursive(N, now_number * stoi(N_type), number, times + N_type.size());

        int Divide = 9;
        if (now_number % stoi(N_type) == 0) {
            Divide = recursive(N, now_number / stoi(N_type), number, times + N_type.size());
        }

        if (now_times > Plus) now_times = Plus;
        if (now_times > Minus) now_times = Minus;
        if (now_times > Multiplication) now_times = Multiplication;
        if (now_times > Divide) now_times = Divide;

        N_type += to_string(N);
    }

    return now_times;
}

int solution(int N, int number) {
    int answer = 9;
    string N_type = to_string(N);

    for (int i=0; i<to_string(number).size(); i++) {
        int optimal = recursive(N, stoi(N_type), number, N_type.size());
        N_type += to_string(N);

        if (answer > optimal) answer = optimal;
    }

    if (answer == 9) return -1;

    return answer;
}

정확성  테스트
  테스트 1 〉    실패 (16.18ms, 3.96MB)
  테스트 2 〉    통과 (8.42ms, 3.97MB)
  테스트 3 〉    통과 (14.51ms, 3.87MB)
  테스트 4 〉    통과 (45.78ms, 3.96MB)
  테스트 5 〉    통과 (26.11ms, 3.84MB)
  테스트 6 〉    통과 (15.81ms, 3.97MB)
  테스트 7 〉    통과 (15.18ms, 3.96MB)
  테스트 8 〉    실패 (34.93ms, 3.83MB)
  테스트 9 〉    통과 (0.02ms, 3.83MB)

채점 결과 정확성: 77.8 합계: 77.8 / 100.0

2차 시도

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

int solution(int N, int number) {
    if (N==number) return 1;

    vector<unordered_set<int>> result_list(8);

    result_list[0].insert(N);

    for (int i=1; i<8; i++) {
        string repeat(i+1, '0' + N);
        result_list[i].insert(stoi(repeat));
        for (int j=0; j<i; j++) {
            for (auto iter_01 = result_list[j].begin(); iter_01 != result_list[j].end(); iter_01++) {
                for (auto iter_02 = result_list[i-j-1].begin(); iter_02 != result_list[i-j-1].end(); iter_02++) {
                    result_list[i].insert(*iter_01 + *iter_02);
                    result_list[i].insert(*iter_01 - *iter_02);
                    result_list[i].insert(*iter_01 * *iter_02);
                    if (*iter_02 != 0) result_list[i].insert(*iter_01 / *iter_02);
                }
            }
        }

        if (result_list[i].find(number) != result_list[i].end()) return i+1;
    }

    return -1;
}

정확성  테스트
  테스트 1 〉    통과 (0.26ms, 3.9MB)
  테스트 2 〉    통과 (0.01ms, 3.84MB)
  테스트 3 〉    통과 (0.02ms, 3.95MB)
  테스트 4 〉    통과 (4.11ms, 3.96MB)
  테스트 5 〉    통과 (3.12ms, 4.16MB)
  테스트 6 〉    통과 (0.06ms, 3.95MB)
  테스트 7 〉    통과 (0.08ms, 3.89MB)
  테스트 8 〉    통과 (4.11ms, 3.89MB)
  테스트 9 〉    통과 (0.01ms, 3.97MB)

채점 결과 정확성: 100.0 합계: 100.0 / 100.0

```

구명보트

1차 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;

    sort(people.begin(), people.end());

    while (people.size()) {
        int most_heavy = *--upper_bound(people.begin(), people.end(), limit);
        people.erase(--upper_bound(people.begin(), people.end(), limit));

        if (people.size()) {
            auto second_most_heavy = --upper_bound(people.begin(), people.end(), limit - most_heavy);
            if (second_most_heavy != --people.begin()) people.erase(--upper_bound(people.begin(), people.end(), limit - most_heavy));
        }

        answer++;
    }

    return answer;
}

정확성  테스트
  테스트 1 〉    통과 (0.46ms, 3.92MB)
  테스트 2 〉    통과 (0.27ms, 3.91MB)
  테스트 3 〉    통과 (0.34ms, 3.94MB)
  테스트 4 〉    통과 (0.29ms, 3.93MB)
  테스트 5 〉    통과 (0.16ms, 3.95MB)
  테스트 6 〉    통과 (0.09ms, 3.89MB)
  테스트 7 〉    통과 (0.13ms, 3.88MB)
  테스트 8 〉    통과 (0.02ms, 3.89MB)
  테스트 9 〉    통과 (0.03ms, 3.96MB)
  테스트 10 〉    통과 (0.30ms, 3.89MB)
  테스트 11 〉    통과 (0.29ms, 3.9MB)
  테스트 12 〉    통과 (0.25ms, 3.93MB)
  테스트 13 〉    통과 (0.29ms, 3.95MB)
  테스트 14 〉    통과 (0.31ms, 3.95MB)
  테스트 15 〉    통과 (0.03ms, 3.84MB)

효율성 테스트 테스트 1 〉 실패 (시간 초과) 테스트 2 〉 통과 (4.91ms, 4.68MB) 테스트 3 〉 실패 (시간 초과) 테스트 4 〉 통과 (4.84ms, 4.82MB) 테스트 5 〉 통과 (4.23ms, 4.56MB)

채점 결과 정확성: 75.0 효율성: 15.0 합계: 90.0 / 100.0

2차 시도

#include <string>
#include <vector>
#include <set>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;

    multiset <int> weight(people.begin(), people.end());
    weight.insert(-1);

    while (weight.size() > 1) {
        auto most_heavy_iter = --weight.lower_bound(limit + 1);
        int most_heavy = *most_heavy_iter;
        weight.erase(most_heavy_iter);

        if (weight.size() > 1) {
            auto second_most_heavy = --weight.lower_bound(limit - most_heavy + 1);
            if (*second_most_heavy != -1) weight.erase(second_most_heavy);
        }

        answer++;
    }

    return answer;
}

정확성  테스트
  테스트 1 〉    통과 (0.94ms, 3.86MB)
  테스트 2 〉    통과 (0.62ms, 3.87MB)
  테스트 3 〉    통과 (0.65ms, 3.89MB)
  테스트 4 〉    통과 (0.60ms, 3.96MB)
  테스트 5 〉    통과 (0.35ms, 3.95MB)
  테스트 6 〉    통과 (0.19ms, 3.91MB)
  테스트 7 〉    통과 (0.31ms, 3.91MB)
  테스트 8 〉    통과 (0.04ms, 3.95MB)
  테스트 9 〉    통과 (0.06ms, 3.71MB)
  테스트 10 〉    통과 (0.62ms, 3.89MB)
  테스트 11 〉    통과 (0.52ms, 3.98MB)
  테스트 12 〉    통과 (0.46ms, 3.97MB)
  테스트 13 〉    통과 (0.63ms, 3.93MB)
  테스트 14 〉    통과 (0.72ms, 3.94MB)
  테스트 15 〉    통과 (0.07ms, 3.93MB)

효율성 테스트 테스트 1 〉 실패 (시간 초과) 테스트 2 〉 실패 (시간 초과) 테스트 3 〉 실패 (시간 초과) 테스트 4 〉 실패 (시간 초과) 테스트 5 〉 실패 (시간 초과)

채점 결과 정확성: 75.0 효율성: 0.0 합계: 75.0 / 100.0

3차 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;

    sort(people.begin(), people.end(), greater<>());

    for (int left=0, right=people.size()-1; left<=right; left++) {
        if (people[left] + people[right] <= limit) {
            right--;
        }

        answer++;
    }

    return answer;
}

정확성  테스트
  테스트 1 〉    통과 (0.17ms, 3.94MB)
  테스트 2 〉    통과 (0.11ms, 3.96MB)
  테스트 3 〉    통과 (0.13ms, 3.91MB)
  테스트 4 〉    통과 (0.12ms, 3.95MB)
  테스트 5 〉    통과 (0.08ms, 3.95MB)
  테스트 6 〉    통과 (0.04ms, 3.92MB)
  테스트 7 〉    통과 (0.06ms, 3.89MB)
  테스트 8 〉    통과 (0.01ms, 3.96MB)
  테스트 9 〉    통과 (0.02ms, 3.93MB)
  테스트 10 〉    통과 (0.11ms, 3.97MB)
  테스트 11 〉    통과 (0.11ms, 3.83MB)
  테스트 12 〉    통과 (0.10ms, 3.97MB)
  테스트 13 〉    통과 (0.11ms, 3.94MB)
  테스트 14 〉    통과 (0.12ms, 3.94MB)
  테스트 15 〉    통과 (0.02ms, 3.84MB)

효율성 테스트 테스트 1 〉 통과 (1.67ms, 4.66MB) 테스트 2 〉 통과 (1.43ms, 4.63MB) 테스트 3 〉 통과 (1.42ms, 4.76MB) 테스트 4 〉 통과 (1.21ms, 4.79MB) 테스트 5 〉 통과 (1.21ms, 4.6MB)

채점 결과 정확성: 75.0 효율성: 25.0 합계: 100.0 / 100.0

섬 연결하기

1차 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> costs) {
    int answer = -1;

    vector<vector<int>> field(n, vector<int> (n, -1));
    vector<int> road;

    for (auto a:costs) {
        field[a[0]][a[1]] = a[2];
        field[a[1]][a[0]] = a[2];
    }

    for (int i=0; i<n; i++) road.push_back(i);

    do{
        int score = 0;
        bool isRoad = true;

        for (int i=0; i<n-1; i++) {
            if (field[road[i]][road[i+1]] == -1) {
                isRoad = false;
                break;
            }

            score += field[road[i]][road[i+1]];
        }

        if (isRoad && (answer == -1 || answer > score)) {
            answer = score;
        }
    } while (next_permutation(road.begin(), road.end()));

    return answer;
}

정확성  테스트
  테스트 1 〉    통과 (0.01ms, 3.9MB)
  테스트 2 〉    통과 (0.01ms, 3.72MB)
  테스트 3 〉    실패 (1.99ms, 3.89MB)
  테스트 4 〉    실패 (시간 초과)
  테스트 5 〉    실패 (0.27ms, 3.77MB)
  테스트 6 〉    실패 (시간 초과)
  테스트 7 〉    실패 (시간 초과)
  테스트 8 〉    실패 (0.02ms, 3.96MB)

채점 결과 정확성: 25.0 합계: 25.0 / 100.0

2차 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;

    sort(costs.begin(), costs.end(), [] (vector<int> a, vector<int> b) {return a[2] < b[2];});
    vector<vector<int>> choose_node = {costs[0]};
    vector <int> parent;

    for (int i=0; i<n; i++) parent.push_back(i);
    parent[choose_node[0][1]] = parent[choose_node[0][0]];

    for (int i=1; i<costs.size(); i++) {
        if (choose_node.size() == n - 1) break;
        if (parent[costs[i][0]] == parent[costs[i][1]]) continue;

        choose_node.push_back(costs[i]);
        parent[choose_node.back()[1]] = parent[choose_node.back()[0]];
    }

    for (vector<int> a:choose_node) {
        answer += a[2];
    }

    return answer;
}

정확성  테스트
  테스트 1 〉    통과 (0.01ms, 3.95MB)
  테스트 2 〉    통과 (0.01ms, 3.96MB)
  테스트 3 〉    실패 (0.02ms, 3.94MB)
  테스트 4 〉    실패 (0.02ms, 3.97MB)
  테스트 5 〉    실패 (0.02ms, 3.98MB)
  테스트 6 〉    통과 (0.04ms, 3.72MB)
  테스트 7 〉    실패 (0.04ms, 3.77MB)
  테스트 8 〉    통과 (0.01ms, 3.96MB)

채점 결과 정확성: 50.0 합계: 50.0 / 100.0

3차 시도

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;

    sort(costs.begin(), costs.end(), [] (vector<int> a, vector<int> b) {return a[2] < b[2];});
    vector<vector<int>> choose_node = {costs[0]};
    vector <int> group;

    for (int i=0; i<n; i++) group.push_back(i);

    group[choose_node[0][1]] = group[choose_node[0][0]];

    for (int i=1; i<costs.size(); i++) {
        if (choose_node.size() == n - 1) break;
        if (group[costs[i][0]] == group[costs[i][1]]) continue;

        choose_node.push_back(costs[i]);
        for (int i=0, change_group = group[choose_node.back()[1]]; i<group.size(); i++) {
            if (group[i] == change_group) group[i] = group[choose_node.back()[0]];
        }
    }

    for (vector<int> a:choose_node) {
        answer += a[2];
    }

    return answer;
}

정확성  테스트
  테스트 1 〉    통과 (0.01ms, 3.98MB)
  테스트 2 〉    통과 (0.01ms, 3.95MB)
  테스트 3 〉    통과 (0.02ms, 3.95MB)
  테스트 4 〉    통과 (0.02ms, 3.97MB)
  테스트 5 〉    통과 (0.02ms, 3.77MB)
  테스트 6 〉    통과 (0.06ms, 3.96MB)
  테스트 7 〉    통과 (0.05ms, 3.89MB)
  테스트 8 〉    통과 (0.01ms, 4MB)

채점 결과 정확성: 100.0 합계: 100.0 / 100.0

```

단체사진 찍기

1차

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

bool CanPosition(string pos, vector<string> data) {
    for (int i=0; i<data.size(); i++) {
        int diff = abs(int(pos.find(data[i][0]) - pos.find(data[i][2]))) - 1;
        int condition = data[i][4] - '0';

        switch(data[i][3]) {
            case '=':
                if (diff != condition) {
                    return false;
                }
                break;
            case '>':
                if (diff <= condition) {
                    return false;
                }
                break;
            case '<':
                if (diff >= condition) {
                    return false;
                }
                break;
        }
    }

    return true;
}

int solution(int n, vector<string> data) {
    int answer = 0;
    string pos = "ACFJMNRT";

    do {
        if (CanPosition(pos, data)) {
            answer++;
        }
    } while (next_permutation(pos.begin(), pos.end()));

    return answer;
}

정확성  테스트
  테스트 1 〉    통과 (2704.51ms, 4.04MB)

채점 결과 정확성: 100.0 합계: 100.0 / 100.0 ```

체육복

1차 시도

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector <int> have_clothes(n, 1);

    for (int n:lost) have_clothes[n]--;
    for (int n:reserve) have_clothes[n]++;

    for (int i=0; i<have_clothes.size(); i++) {
        if (have_clothes[i] == 0) {
            if (i > 0 && have_clothes[i-1] == 2) {
                have_clothes[i-1]--;
                have_clothes[i]++;
            } else if (i < have_clothes.size()-1 && have_clothes[i+1] == 2) {
                have_clothes[i+1]--;
                have_clothes[i]++;
            }
        }

        if (have_clothes[i] >= 1) answer++;
    }

    return answer;
}

정확성  테스트
  테스트 1 〉    실패 (0.01ms, 3.85MB)
  테스트 2 〉    실패 (0.01ms, 3.97MB)
  테스트 3 〉    통과 (0.01ms, 3.95MB)
  테스트 4 〉    통과 (0.01ms, 3.96MB)
  테스트 5 〉    실패 (0.01ms, 3.95MB)
  테스트 6 〉    통과 (0.01ms, 3.91MB)
  테스트 7 〉    통과 (0.01ms, 3.97MB)
  테스트 8 〉    통과 (0.01ms, 3.96MB)
  테스트 9 〉    실패 (0.01ms, 3.72MB)
  테스트 10 〉    통과 (0.01ms, 3.96MB)
  테스트 11 〉    실패 (0.01ms, 3.89MB)
  테스트 12 〉    통과 (0.01ms, 3.91MB)

채점 결과 정확성: 58.3 합계: 58.3 / 100.0

### 2차 시도
```cpp
#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector <int> have_clothes(n, 1);

    for (int n:lost) have_clothes[n-1]--;
    for (int n:reserve) have_clothes[n-1]++;

    for (int i=0; i<have_clothes.size(); i++) {
        if (have_clothes[i] == 0) {
            if (i > 0 && have_clothes[i-1] == 2) {
                have_clothes[i-1]--;
                have_clothes[i]++;
            } else if (i < have_clothes.size()-1 && have_clothes[i+1] == 2) {
                have_clothes[i+1]--;
                have_clothes[i]++;
            }
        }

        if (have_clothes[i] >= 1) answer++;
    }

    return answer;
}

정확성  테스트
  테스트 1 〉    통과 (0.01ms, 3.97MB)
  테스트 2 〉    통과 (0.01ms, 3.97MB)
  테스트 3 〉    통과 (0.01ms, 3.78MB)
  테스트 4 〉    통과 (0.01ms, 3.93MB)
  테스트 5 〉    통과 (0.01ms, 3.97MB)
  테스트 6 〉    통과 (0.01ms, 3.82MB)
  테스트 7 〉    통과 (0.01ms, 3.8MB)
  테스트 8 〉    통과 (0.01ms, 3.97MB)
  테스트 9 〉    통과 (0.01ms, 3.91MB)
  테스트 10 〉    통과 (0.01ms, 3.97MB)
  테스트 11 〉    통과 (0.01ms, 3.99MB)
  테스트 12 〉    통과 (0.01ms, 3.92MB)

채점 결과 정확성: 100.0 합계: 100.0 / 100.0

## 조이스틱
### 1차 시도
```cpp
#include <string>
#include <vector>

using namespace std;

int optimal_distance(string name, int * pos) {
    int left_move = 0, right_move = 0;

    for (int i=0; i<name.length(); i++) {
        if ((name[*pos] != 'A') || (left_move != 0 && right_move != 0)) break;

        if (left_move == 0 && name[(*pos - i + name.length()) %  name.length()] != 'A') left_move = i;
        if (right_move == 0 && name[(*pos + i) %  name.length()] != 'A') right_move = i;
    }

    *pos = (*pos + ((left_move < right_move) ? name.length()-left_move : right_move)) % name.length();

    return (left_move < right_move) ? left_move : right_move;
}

int solution(string name) {
    int answer = 0;
    int pos = 0;

    vector <int> alphabet_code = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    for (string c(name.length(), 'A'); c != name; name[pos] = 'A') {
        answer += optimal_distance(name, &pos) + alphabet_code[name[pos] - 'A'];
    }

    return answer;
}

정확성  테스트
  테스트 1 〉    통과 (0.01ms, 3.93MB)
  테스트 2 〉    통과 (0.01ms, 3.95MB)
  테스트 3 〉    통과 (0.01ms, 3.95MB)
  테스트 4 〉    통과 (0.01ms, 3.89MB)
  테스트 5 〉    통과 (0.01ms, 3.95MB)
  테스트 6 〉    통과 (0.01ms, 3.95MB)
  테스트 7 〉    통과 (0.01ms, 3.97MB)
  테스트 8 〉    통과 (0.01ms, 3.93MB)
  테스트 9 〉    통과 (0.01ms, 3.89MB)
  테스트 10 〉    통과 (0.01ms, 3.96MB)
  테스트 11 〉    통과 (0.01ms, 3.95MB)

채점 결과 정확성: 100.0 합계: 100.0 / 100.0 ```