IT's me

여러가지 1 문제 빙고 (정올)

간단한 문제인 줄 알았지만, 상당히 코드가 길다.

내가 좀 비효율적으로 푼 것 같기도 하다..

가로, 세로, 크로스로 체크하는 함수를

따로 두어서 그 함수에서 체크된 빙고 수를 리턴

입력, 출력 등등 여러가지

알고리즘을 풀기 전에 기초부터 제대로 잡고 들어가야 할 것 같다.

그리고 코딩 테스트에서 알고리즘보다 이러한 문제 풀이형식의

문제가 더욱 많이 출제 되는 것 같다. 분발하자.

문자열 관련 문제 02 (정올)

비밀 편지, 단어 집합(하), 소수문자열, 단어세기

01. 비밀 편지

02. 단어 집함(하)

03. 소수 문자열

소수를 체크하는 부분에서 좀 더 효율적인 코드를 생각해보자.

04. 단어 세기

경고가 뜨는 이유에 대해서 좀 더 생각해보자.

알고리즘 기초 문자열 문제 (정올)

1. 그릇

2. 문자열 찾기

3. 문자열 변환

알고리즘 테스트에 자주 등장하는 것이 바로 문자열!

그래서 오늘부터 문자열에 대한 문제를 풀어보기로 했다.

01. 그릇

03. 문자열 변환

02. 문자열 찾기

백트래킹 알고리즘 02 해밀턴 순환회로

답은 다 맞았지만 시간초과..

그래도 푸는 시간이 N queen 보다 대폭 줄었다.

다음엔 재귀가 아닌 스텍으로 풀어보겠다.

01 선언 및 초기화

02 재귀 함수 호출

03 답 출력 그리고 메인 함수

백트래킹도 대충 어떤 느낌인지 알겠다.

익숙해지기만 하면 될 듯하다.

백트래킹 알고리즘 N Queen (정올)

이 문제를 푸는데 10시간은 걸린 듯하다.

어떤 식으로 풀어야 한다는 것은 머리에 그려졌지만

대각선 방향으로의 체크를 어떤 식으로 진행해야 할지

방법이 떠오르지 않았다. 내가 수학문제를 푸는지

프로그래밍을 하고 있는지 모르겠다. 맘에 안든다.

01. 문제 개요

02. 선언

03. 체크 방법

04. 답 찾기

06. 메인

제발 이런 문제는 테스트에 나오지 않길..

그리디 알고리즘 06 공주님의 정원

처음으로 한방에 성공~

01 클래스 선언

02 초기화

03 정렬

04 재귀함수 호출 그리고 답 출력

05 메인 함수

이제 백트래킹으로 넘어가 봅시다~

그리디 알고리즘04 도서관 문제

이번 문제는 푸는 동안 자연스럽게 흘러 가는게 아니라

뭔가 끼워 맞추듯 부자연스러운 느낌이 강했다.

뭔가 더 좋은 방법이 있을거 같은데..

01. 클래스 선언

02. 초기화

03. 정렬

04. 답 찾기 그리고 답 출력

05. 메인 함수

대충 흐름은 알겠고..

조금만 더 빨리 푸는 연습을 해야 할 거같다.

그리디 알고리즘03 냉장고 문제 (정올)

그리디 알고리즘02 소시지 공장 (정올)

며칠 전에 소시지공장의 터무니 없는 풀이를 올렸었다.

계속 풀어도 똑같은 결과가 나오길래 이상하다 싶었는데

문제 자체를 잘못 이해하고 있었다.

제대로된 풀이를 올리려는 포스팅은 아니지만

그래도 100점이 나와서 한번 올려본다.

(어차피 보는 사람도 없겠지만..)

한창 STL을 공부하고 있고, 클래스 디자인에 관심이 많을 때라

클래스라던지, 함수 객체, 벡터 등 왜 굳이 이렇게 풀어야할까..

의문이 드는 부분이 있겠지만, 공부하는 입장에서 이곳 저곳에서

써보면서 좀 익숙해지려고 생각나는 대로 다 써보았다.

따라서 절대 정답이 될 수 없는 풀이이다.

이렇게 푸는 놈도 있구나.. 하고 참고하시길

1. 클래스 선언

2. 초기화

3. 정렬을 위한 함수 객체 선언

4. 알고리즘과 함수 객체를 이용한 정렬 그리고 재귀 함수 호출

5. 답을 찾는 재귀 함수 구현

w_FindAnswer() 또한 같은 방법으로 구현

6. 답을 출력하는 함수와 메인 함수

코드가 복잡하다. 하지만 풀었다는 것에 의의를 두겠다.

그럼 다음 알고리즘 풀이로 돌아오겠다.

그리디 알고리즘01 회의실 배정 (정올)

처음으로 100점이 나왔다.

정말 쉬운 문제이긴 하지만

답을 보지 않고 처음부터 끝까지

내가 푼 문제라 더 뿌듯하다.

물론 최적화된 코드는 절대 아니다.

1. 일단 종료시간을 기준으로 오름차순으로 정렬

2. 정렬된 후에 맨 앞에 있는 회의는 무조건 맨 처음에 들어갈 수 있다.

따라서 FindAnswer(0) 으로 함수를 호출한다.

3. if(0번 째 회의라면) 넌 답이니까 v에 들어가라.

4. 그리고 다음 회의를 찾아간다.

for문으로 자신의 오른쪽 방향으로 하나씩 탐색.

맨 처음에 들어갈 회의가 결정났기 때문에

맨 처음 회의의 종료시간과 그 다음 회의의

시작시간을 비교 if(종료시간 <= 다음 놈 시작시간)

5. 해당하는 회의를 찾았다면 그 회의의 num을

v에다가 집어 넣고, 그 회의의 인덱스로

다시 FindAnswer(index) 함수 호출.

그리고 본 함수는 종료시켜준다. return;

6. 재귀를 통해 답을 찾다가

해당하는 회의가 없어 for문 루프를 빠져나오면

함수를 종료 시킨다. return;