IT's me

BFS 알고리즘 백준의 토마토 문제

정말 오랜만에 BFS 알고리즘 문제를 풀어 보았다.

그저께 DFS 알고리즘 문제를 풀다가 2시간 멘붕이 와서

사실 자심감이 많이 떨어진 상태..

BFS, DFS만은 자신 있었는데.. 꾸준히 해야겠다는 생각이 든다.

이 문제도 40분 걸렸지만, 한 번에 성공했다는 것에 만족~

01. 구조체 , 큐, 박스 등등

02. 초기화

03. 체크 함수

04. 모두 익었니? 아니면 덜 익은게 있니?

05. BFS 알고리즘

06. 메인 함수

BFS 알고리즘을 이용하여 백준의 토마토 문제를 풀어보았다.

한동안 알고리즘에 손 떼고 있다가 풀어보니 낯설다..

무엇이든 꾸준함이 가장 중요한 것 같다.

다이나믹 (동적 계획법) 알고리즘 : 동전 교환 문제 (정올)

다이나믹 알고리즘의 가장 대표적인 문제가 아닌가 한다.

차곡차곡 저장된 데이터를 기반으로 답을 찾아간다는

단순한 논리이지만 수학문제를 푸는 것 같아 굉장히 어렵다..

이번 문제는 1시간 이상 걸렸고, 데이터를 차곡차곡

저장하는 방법과, 저장된 데이터를 빼서 사용하는

부분에서 상당히 애를 먹었다. ( 그냥 다 어려웠다는 말 )

01. 다이나믹(동적 계획법)을 수행할 클래스 선언

02. 초기화

03. 다이나믹 (동적 계획법) 알고리즘 수행

나름 자세하게 설명해 보았다. 다이나믹을 처음 접했을 때

상당히 난해했던 기억이 난다. 혹시나 나와 같은 사람이 있을까

최대한 설명을 해보지만.. 더 헷갈릴 수도 있겠다는 생각이 든다.

04. 메인 함수

멤버 함수를 하나하나 부르기 보다 편의 함수를

정의해서 함수 호출을 했다. 알고리즘 공부를 하면서

C++도 공부할 수 있으면 괜찮겠다 생각해서

클래스로 만들고 편의 함수도 만들어 보았다.

DFS(백트래킹) 알고리즘 문제 : 영역구하기 (정올)

오랜만에 DFS(백트래킹) 알고리즘을 풀어보았다.

DFS는 흔히 재귀로 많이 풀기 때문에 소위 말하는

재귀적인 사고(?)가 필요하다. 코드를 설명하는 부분에도

이러한 부분을 설명하기가 상당히 까다롭기 때문에

설명이 조금 부실하다.

일단 DFS(백트래킹)은 깊이 우선 탐색을 한다.

쉽게 말해 한 방향으로 쭉 들어갔다가 빠져나오는 것

스택의 원리와 같기 때문에 스택을 이용하거나

함수가 스택에 쌓였다가 풀리는 과정을 이용(재귀)

하여 풀 수 있다. 이번 문제는 난이도가 높지는 않은 듯 하다.

01. 변수 선언, 초기화

DFS (백트래킹)문제를 잘 풀기 위해서는

문제를 제대로 이해하고 초기화 하는 것 부터 시작.

02. 재귀 함수

최대한 자세히 설명한다고 했지만

재귀적인 사고(?)가 필요함.

03. 메인 함수

위에 코드에서도 언급했지만

한번의 함수호출로 답을 찾아낼 수 있는 방법이

있는지 조금 더 생각해봐야 할 부분이다.

오늘은 오랜만에 DFS(백트래킹) 알고리즘을 풀어보았다.

사실 초반에 BFS로 풀까 말까 고민하다가 정신없었던 건 사실

DFS, BFS에 익숙해져서 어떠한 알고리즘을 써야하는지

한번에 캐치하는 것도 중요한 듯 하다.

1차원 배열을 사용하는 알고리즘 기초 문제 (백준)

숫자의 개수 , OX 퀴즈 , 음계 , 평균 점수 (백준)

알고리즘의 기초가 되는 1차원 배열

난이도가 낮은 편에 속하지만

기초를 튼튼히 다지지 않으면

사상누각에 불과한 것.

백준 사이트의 1차원 배열 사용하기 마스터~

01. 숫자의 개수

숫자를 어떻게 체크해야할지 엄청 고민했다.

문자열로 받아야 하나.. 이런 저런 고민하다가

그냥 나누어서 해결.

02. OX 퀴즈

그냥 O,X 구분해서 점수 누적

03. 음계

함수를 쓰기가 귀찮아서 안썻다가

결국은 함수를 써서 해결..

04. 평균 점수

백준의 알고리즘 문제는 가끔씩 터무니 없이

쉬운 문제도 나온다. 가뭄의 단비 같은 존재

역시나 알고리즘은 술술 풀려야 하는 맛이 나는데..

요즘 하고 있는 DFS , BFS , 다이나믹 알고리즘은

죽을 맛이다. 알고리즘 기초문제라 쉽게 풀리지만

어떤 분야든 기본은 튼튼하게!!

다이나믹 (동적 계획법) 알고리즘 문제. 배낭 채우기1 (정올)

동적 계획법의 가장 큰 특징은

전에 찾아놓았던 답을 가져다가 후의 답을 찾는 데 사용한다는 것

이 문제는 이러한 규칙을 잘 이용하면 풀 수 있다.

사실 DFS , BFS 같은 경우 복잡하긴 했지만

스택이나 큐의 성질을 이용하면서 풀기 때문에

나름 코딩을 하고 있다는 느낌이 들었지만,

다이나믹 (동적 계획법)알고리즘은 내가 수학공식을

만들어 내는 듯한 느낌을 준다.( 아직 많은 문제를 풀진 않았지만 )

이 문제 또한 답을 보지 않았다면 언제 풀었을지 모르겠다..

이 알고리즘에 익숙해지기 까지는 한참 답을 참고해야 할 듯 하다.

01. 클래스 선언

한 가지 위안이라면, 그리디 알고리즘을 풀 때 처럼

객체화를 해서 풀 수 있다는 점.. 나름 재미를 느끼고 있는 부분이기에

02. 초기화

03. 답 찾기

차근차근 개념을 적립해둘 겸 그리고

혹시나 나처럼 다이나믹 (동적 계획법) 때문에

헤메고 있을 중생들이 있을까봐 최대한 자세히 설명

(위에 설명한 적립식으로 푼다는 점을 짚고 들어 가겠다.)

04. 메인

다이나믹 (동적 계획법) 알고리즘은 진짜 수학적 사고력이

 뛰어나야 한다는 느낌을 받는다. DFS나 BFS처럼

다이나믹도 곧 익숙해지리라 믿는다.

알고리즘 기초문제 문자열

문자열 반복, 단어의 개수 (백준)

정올에 이어 백준 문자열 문제까지 마스터~

백준에 꽤 까다로운 문제가 많이 나와서

시간이 좀 오래 걸린 듯 하다.

1. 문자열 반복

말 그대로 입력된 숫자만큼 문자를 반복해서

출력하면 되는 문제다. 이중 for문으로 간단하게

해결 가능하기 때문에 주석은 달지 않았다.

2. 단어의 개수

알고리즘 기초 문자열 문제를 풀면서

함정이 많이 있다고 느꼈는데 그 중 가장 대표적인 문제다.

항상 느끼지만 알고리즘 기초 문제 중에서도

문자열은 특히 더 중요하기 때문에 더욱 신경 써서 해둬야겠다.

DFS, BFS, 다이나믹 등등 주요 알고리즘도

풀어야 하는데.. 너무 어려워서 풀기 싫네..

다이나믹 알고리즘 (동적 계획법) 두 줄로 타일 깔기 (정올)

점화식을 세우는 것이 가장 중요한 부분이란다.

이 문제에 대한 점화식을 미리 알고 들어갔기 때문에

수월하게 풀었다. 즉, 점화식만 잘 세운다면 쉽게 풀 수 있다는 거

다이나믹 알고리즘이라는 게 대충 어떤 것인지는 알 수 있었다.

기존의 데이터를 차곡차곡 저장해 놓고

그 데이터를 바탕으로 값을 계산해 나간다는 것.

다음 문제부터는 다이나믹(동적 계획법)의 핵심인

점화식을 직접 구해보면서 공부해 나가도록 하겠다.

사실 문제를 제대로 읽지않아 20100529 이 부분이 왜 들어가는지 한참 찾았다.

이 것만 아니었어도 3분 내에 해결 됬을 듯..( 당연 점화식을 알고 있었기 때문에)

다이나믹(동적 계획법) 에 대해 맛만 보는 시간을 가졌다.

자 다음문제 점화식을 세우러 go go

문자열 알고리즘 기초 문제

상수 , 다이얼 , 크로아티아 알파벳 (백준)

01. 상수

왜 냈는지 의도를 모르겠다..

기존 문자열 문제보다 상당히 쉽다.

02. 다이얼

알고리즘 기초 문자열 문제 02. 다이얼

처음에 이런 식으로 풀었는데 가독성이 상당히 안좋다.

3중 for문을 썻기 때문에 입력의 크기가 컸다면

상당한 시간복잡도를 보일 것이다.

그래서 다른 사람들은 어떻게 풀었나 보니까

모두 if문 아니면 switch로 풀었더이다.

난 스위치를 좋아하기 때문에 스위치로 한번 더

근데 하드코딩을 하는 듯한 느낌

03. 크로아티아 알파벳

상당히 고민을 많이 했다.

새벽이라 집에 빨리 가고 싶기도 하고

집중도 안되고, 이리저리 해보다가 풀렸다.

함수를 적절히 이용해야겠다는 생각..?

알고리즘 기초 문자열 문제를 풀어보았다.

문자열 문제는 다른게 아니고 항상 형변환에 대해

고민을 안할 수가 없는데, 한번 날잡아서

형변환에 대해 정리하는 시간을 가지겠다.

BFS 알고리즘 경로 찾기 (정올)

살짝 난해한 문제 같았으나

비교적 빠른 시간에 풀었고 한방에 통과~

구조체에 어떠한 변수를 넣을 것인가를 잘 생각해야 하고,

중복된 곳을 다시 큐에 넣지 않게 잘 체크하는 것이

BFS 알고리즘을 푸는 데 있어 가장 중요한 부분인 것 같다.

노드를 잘 만들고 경로 체크를 하고 큐에 넣고 빼고

유효성 체크만 잘 해주면 아주 간단한 문제.

(모든 BFS의 공통된 핵심인 듯 하다.)

01. 변수 선언

BFS 알고리즘을 위한 인큐 , 디큐

02. 초기화

큐가 비었는지 체크하는 함수

그리고 헤밍 경로가 맞는지 체크하는 함수

03. 답을 찾는 함수

1. 큐에 넣고

2. 경로 체크 하고

3. 큐에서 빼고

4. 유효성 검사

04. 메인 함수

BFS 알고리즘은 앞서 말했듯이 구조체를

어떻게 구성할지 빨리 캐치만 한다면

그 후로는 쭉쭉 풀어나갈 수 있을 듯하다.

알고리즘 기초 문제 - 단어 공부 , 그룹 단어 체커 (백준)

단어 공부 문제는 비교적 쉽게 풀었지만

그룹 단어 체커에서 멘붕

01. 단어 공부

알고리즘 기초 문자열 문제를 풀면서 느끼는 거지만

코드의 순서만 다르게 해줘도 복잡한 부분이 해결된다.

02. 그룹 단어 체커

상당히 짜증나게 했던 그룹 단어 체커

이런 문제가 어떻게 정답률이 60%가 넘는지..

메인 함수 

즐거워야 할 알고리즘 기초문제인데

심기가 불편하다.. 특히나 백준 사이트는

정올 처럼 어떠한 부분이 틀렸는지

볼 수 없기 때문에 걍 빡(?)침