안녕하세요. 알고리즘 공부하기 정말 ... 좋네요 ...ㅎㅎㅎ 오늘은 백준의 '삼성 SW 역량 테스트 기출 문제' 문제집에 있는 문제 중 하나인 '퇴사'를 가져와보았습니다. 이 문제의 해결법을 먼저 말해보자면, Brute Force 알고리즘으로 짜보았어요. Brute Force는 무식한(brute) + 힘 (force) 라는 의미로, 무식하게 밀어붙인다? 쯤 ...? 인 것 같아요. 완전 탐색 알고리즘으로 모든 경우의 수를 탐색하게 됩니다. 이 알고리즘은 정답만을 출력하기 때문에, 믿을만한 알고리즘이죠. 문제는 아래와 같습니다. 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 ..

안녕하세요. 최근에 알고리즘 공부를 다시 시작했는데, 다시 시작한 김에 C++ 로 언어를 바꿔보았습니다. 확실히 코딩하는 시간이나 습득하는 시간 등 장점이 많다고 느꼈어요. 지인 분들이 왜 python으로 안하냐고들 하는데 그러게요 ... 마지막 욕심일지두 희희 오늘은 프로그래머스의 Greedy 문제인 구명보드를 풀어보고자 합니다. 참고로 Greedy는 지난 포스팅에서 개념을 확인할 수 있습니다. 일단 문제는 아래와 같습니다. 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번..

오늘은 너비우선 탐색을 알아보겠습니다. DFS는 BFS와 같이 배우는 경우가 많은데요. BFS는 지난 포스팅에서 다루었기 때문에 필요하다면 참고해보셔도 좋을 것 같아요 〰️ DFS❓ DFS는 Depth First Search의 약자입니다. 너비 우선 탐색으로, 연결되어 있는 모든 노드를 전부 확인하고 그 다음 노드의 모든 노드를 살펴보는 방식으로 모든 노드를 탐색하는 방식이죠. DFS와 BFS의 비교는 지난 포스팅에서 이미 다뤘기 때문에 생략하겠습니다. DFS 구현 노드들이 연결되어 있다고 가정하겠습니다. 아래의 그림에서 왼쪽은 보기 편하게 도식화한 모습이고, 오른 쪽의 위는 linked List로 구현되어 있는 모습을 표시했습니다, Visited는 Boolean 타입의 Array입니다. 위의 그림에서 ..

프로그래머스 문제인 '단어 변환'을 해결해 봅시다. 문제를 먼저 살펴보도록 할게요. 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과..

오늘은 프로그래머스에서 제공하는 문제인 Network 를 다뤄보겠습니다. 문제는 아래와 같습니다. 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-..

어렵지만 재밌게 푼 문제! 문제를 이해하는 데 어려움이 컸고, 완전히 이해한 후 문제를 푸니 재밌게 풀 수 있게 되었다 〰️ 일단, 문제를 보고 솔루션을 찾아가 보도록 합시다 ❗️ 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸..