PS/프로그래머스
[프로그래머스] 단어변환
[프로그래머스] 단어변환
2020.06.17문제 : 단어 변환 [ 문제 출처 ] https://programmers.co.kr/learn/courses/30/lessons/43163 [문제 풀이] 이 문제의 경우 주어진 문제를 그래프로 표현할 수 있어야 한다 즉 "그래프 모델링"을 해주어야 한다 어떤 것을 그래프의 정점으로 사용할 것이고 정점과 정점을 잇는 간선의 연결은 어떻게 정할 것인지 등이 있다 이 문제의 그래프 모델링 과정을 살펴보자! 정점은 어떤 것으로 사용해야 할 까? words에 있는 단어로 하면 좋지 않을까? 정점과 정점을 잇는 간선은 어떻게 연결시켜야 할까? 알파벳을 단 한 개만 바꾸어 해당 단어로 표현할 수 있다면 이는 연결 되었다고 볼 수 있다 즉 "hot" --> "hit" , "hot" --> "dot" 알파벳 차이가 단 ..
[프로그래머스] [1차] 프렌즈4블록
[프로그래머스] [1차] 프렌즈4블록
2020.06.10문제 : Level2 [1차] 프렌즈4블록 [ 문제 출처 ] https://programmers.co.kr/learn/courses/30/lessons/17679 [문제 출처] 이 문제는 단순하게 보드를 순회하면서 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다 블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다 이 2가지를 구현하면 되는 문제이다 밑에 그림과 같이 단순한 4개의 블록은 그냥 지우고 4점을 획득 하면 된다. 하지만 다음 그림은 조금은 아주 조금은 복잡하다고 생각 할 수 있지만 전혀 아니다 1번을 바로 지워 버리게 되면 2번에서는 4개를 인식 하지 못하게 되므로 2번에서는 지울 수 가 없다 즉 4점밖에 획득 하지 못하게 된다 지울 경우 단..
[프로그래머스] 기능개발
[프로그래머스] 기능개발
2020.06.10문제 : Level2 기능개발 [ 문제 출처 ] https://programmers.co.kr/learn/courses/30/lessons/42586 [ 문제풀이 ] 이 문제의 카테고리가 스택/큐였기에 한참 스택을 이용한 풀이를 생각했었지만 스택 또는 큐를 사용해서 풀 필요 가 없다는 것을 알고 반복문 한 개를 가지고 문제를 풀었다 풀이의 시간 복잡도는O(n)으로 풀었다 주어진 예시 문제를 보자! 작업의 진도 현황을 나타내는 배열 : [93, 30, 55] 각 작업의 개발 속도를 나타내는 배열 : [1, 30, 5] 주어진 배열들을 이용해서 주어진 작업이 앞으로 얼마나 걸릴 것인지를 간단한 연산을 통해서 알 수 있다 [(100 - 93) / 1, (100 - 30) / 30, (100 - 55) / 5]..
[프로그래머스] 카드 게임
[프로그래머스] 카드 게임
2020.06.03문제 : Level4 카드 게임 [ 문제출처 ] https://programmers.co.kr/learn/courses/30/lessons/42896 [ 문제풀이 ] 처음에 문제를 이해 하기를 문제에서 제시된 조건 1 부분에서 1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다 이 부분에서 이해가 가질 않았다 역시 국어를 못하니 문제를 빠르게 파악하지를 못하는 것 같다 ㅠㅠ 제시된 조건도 1과 2로 나누어 주었으면 좋지 않았나 싶기도 하다 얻는 점수가 없는 경우를 묶어서 조건으로 내민 것 같다 게임에서 가능한 경우를 보자 조건 : 어느쪽 더미든 카드가 없어질 때까지 1. 왼쪽 카드를 버리자 2. 왼쪽과 오른쪽 카드를 동시에 버리..
[프로그래머스] 네트워크
[프로그래머스] 네트워크
2020.05.25문제 : Level3 네트워크 [ 문제출처 ] https://programmers.co.kr/learn/courses/30/lessons/43162 [ 문제풀이 ] 이 문제는 컴퓨터의 연결 정보가 주어 질 때 이 연결 정보를 통해서 몇 개의 네트워크가 존재하는지를 구하는 문제이다 BFS 탐색을 통해서 연결되어 있는 모든 컴퓨터 즉, 모든 노드 탐색하면서 방문한 노드를 check 배열에 표시해 주었다 정답은 BFS의 호출 횟수이다 여기서 주의할 점은 컴퓨터의 연결 정보가 인접 리스트가 아닌 인접 행렬로 주어진다는 점이다 그 점만 주의해서 BFS 탐색 코드만 잘 짜주면 된다. [소스 코드] 123456789101112131415161718192021222324252627282930313233#include ..
[프로그래머스] 섬 연결하기
[프로그래머스] 섬 연결하기
2020.05.25문제 : Level3 섬 연결하기 [ 문제출처 ] https://programmers.co.kr/learn/courses/30/lessons/42861 [ 문제풀이 ] 이 문제는 n개의 섬에 다리를 건설해야 하는데 최소의 비용으로 모든 섬을 연결하여야 한다. 다음의 예시를 살펴보면 A ----- B ----- C A----B 와 B----C 를 연결하였으므로 간접적으로 A와 C 는 연결되었다 즉 A ----- C A와 C를 연결하는 다리는 건설할 필요 가 없다. 이 문제를 풀기 위해서는 유니온 파인드 알고리즘이 필요하다 유니온 파인드를 적용하면 이 문제는 매우 쉽게 해결 할 수 있다 유니온 파인드에 대해서 잘 모른다면 이에 대해 학습하고 문제 풀기를 추천한다!! 모든 노드들을 연결하면서 노드들을 연결하기..