Today's Algorithm(2018-10-19) programmers 네트워크 깊이/너비 우선 탐색으로 풀 수 있는 문제 중 가장 간단한 형태의 문제 중 하나가 아닐까 생각합니다. 한마디로 연결되어 있는 네트워크의 개수를 구하라는 것이죠. 모두가 이어져 있으면 1개, 만약 모두 연결되어 있지 않으면 n이 반환되는 것입니다. 이 경우 '깊이 우선 탐색', '너비 우선 탐색' 모두 사용 가능한데요. 저는 Queue를 이용한 '너비 우선 탐색'을 이용하였습니다. 대략적인 풀이 방법은 다음과 같습니다. n개의 반복문을 돌면서 방문하지 않은 컴퓨터를 하나 고릅니다. 방문하지 않은 컴퓨터를 큐에 넣고 방문 표시 및 네트워크 개수를 +1 증감합니다. 이 큐가 비워질 때까지 반복합니다. 그 반복문 안에서 우선 큐..
programmers 타겟 넘버 뭔가 어려울줄 알았는데 막상 풀어보니 단순한 문제였네요. 결국은 모두 탐색해봐야하는 문제인데요. 이 경우 고려해볼 수 있는 것은 DFS를 고려해볼 수 있습니다. DFS를 구현하기 위해 재귀를 썼습니다. 하지만 구현을 하는데 있어 전역변수를 최대한 써보지 않는 방향으로 노력해봤는데 생각보다 잘 안되더라구요. 그래서 다 풀고나서 다른 사람들의 풀이를 참고하여 전역변수없이 구현하는 부분까지 해봤습니다. class Solution { int answer, target; public int solution(int[] numbers, int target) { answer = 0; this.target = target; int[] sign = {-1, 1}; visit(numbers,..
boj 14940. 쉬운 최단거리 리팩토링 어제 이 문제를 풀면서 제대로 풀지 못했다는 생각에 조금 아쉬웠는데요. 오늘 저보다 잘하시는 분들의 코드를 보면서 어떻게 좀 더 간단하면서도 명확하게 풀 수 있는지 배우게 되었습니다. 그분의 코드를 보고 느낀점을 정리해볼께요. 변수 이름 짓기 DFS 풀다보면 배열이 필요한데요. 저의 경우 익숙하지 않다보니 배열명을 막 지었고 그렇다보니 뒤에서 쓰면서 많이 헷갈렸던 것 같아요. 그래서 아래에 몇 개 유용하다고 생각하는 이름을 적겠습니다. visited(방문 체크), map(지도 값들) 입력값 배열에 넣을 때 StringTokenizer의 사용 이건 개인 스타일의 차이일 수도 있는데 StringTokenizer를 사용하면 띄워쓰기에 따라 알아서 구분해주기 때문에 좀..
Today's Algorithm(2018-11-12) boj 14940. 쉬운 최단거리 이번 문제의 경우 풀다가 제가 선언한 변수들을 제가 헷갈려버리기 시작하면서 미궁으로 빠졌고 시간이 꽤 오래 걸렸습니다. 이후 미궁으로 빠졌던 부분에서 겨우 빠져나오고 나서야 제출할 수 있었는데요. 답은 맞았지만 참 찝찝한 느낌이 듭니다. 다음과 같은 이유들 때문입니다. 코드에서 비효율성, 반복이 너무 많이 보입니다. 반복되는 부분, 다른 조건에서 다 처리할 수 있는 부분이 곳곳에 보였지만 지역변수들이 너무 많아 헷갈려서 많이 줄이지 못하였습니다. 앞에서 말한대로 지역변수들이 너무 많이 선언되어 제가 선언한 것임에도 불구하고 무엇을 의미하는건지 많이 헷갈렸습니다. 시간과 메모리에서 둘 다 다른 사람들에 비해 좋지 않습니..
Today's Algorithm(2018-11-10) boj 12865. 평범한 배낭 배낭 문제 참 유명하죠. 다이나믹 프로그래밍으로 풀 수 있는 대표적인 문제 중 하나인데요. 이 문제를 토대로 해결법을 정리해볼게요! 다이나믹 프로그래밍은 모든 수에 대해 탐색을 하는데 그 이전의 봤던 수에 나온 데이터들을 이용하는 것입니다. 중요한 것은 데이터, 즉 무엇을 기록할지입니다. 이 문제의 경우 전dp[해당_아이템][해당_무게] = 전 해당 무게에서 해당 아이템이 추가되었을 때 최고 가치로 잡아 모든 아이템을 보면서 기록해나가는 것이죠. 이 문제의 경우 다음 그림과 같이 기록 가능합니다. 그럼 의문이 들죠. '어떻게 최고 가치를 찾을 것인가?' 이전에 이렇게 구성할 때 물건을 하나씩 살펴보고 기록하기 때문에 다..
Today's Algorithm(2018-11-09) leetcode 8. String to Integer (atoi) atoi메서드를 실제 구현해보는 문제인데요. 이 문제 푸는데 얘 먹었습니다. 이게 특정 방식으로 풀지 않으면 갈수록 미궁 속이 되더라구요. 결국은 다른 사람의 코드를 참고하여 해결하였습니다. 문제 풀면서 힘들었던 점과 참고한 풀이에서는 어떻게 해결했는지 살펴볼게요. 막혔던 부분 Integer 범위 넘어가는 수 처리 전 처음에 문자열을 가지고 이를 처리하려 했습니다. Integer.parseInt()를 너무 좋아했던거죠. 그렇다보니 넘어가는 수에 대해 자리수 계산하고 그랬습니다. 정확하지도 않고 그게 맞는지도 모르는채 말이죠. 하지만 각각의 자리 수에 대해서 바로바로 Integer형으로 ..
