프로그래머스
[프로그래머스] 단어변환
[프로그래머스] 단어변환
2020.06.17문제 : 단어 변환 [ 문제 출처 ] https://programmers.co.kr/learn/courses/30/lessons/43163 [문제 풀이] 이 문제의 경우 주어진 문제를 그래프로 표현할 수 있어야 한다 즉 "그래프 모델링"을 해주어야 한다 어떤 것을 그래프의 정점으로 사용할 것이고 정점과 정점을 잇는 간선의 연결은 어떻게 정할 것인지 등이 있다 이 문제의 그래프 모델링 과정을 살펴보자! 정점은 어떤 것으로 사용해야 할 까? words에 있는 단어로 하면 좋지 않을까? 정점과 정점을 잇는 간선은 어떻게 연결시켜야 할까? 알파벳을 단 한 개만 바꾸어 해당 단어로 표현할 수 있다면 이는 연결 되었다고 볼 수 있다 즉 "hot" --> "hit" , "hot" --> "dot" 알파벳 차이가 단 ..
[프로그래머스] 기능개발
[프로그래머스] 기능개발
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를 연결하는 다리는 건설할 필요 가 없다. 이 문제를 풀기 위해서는 유니온 파인드 알고리즘이 필요하다 유니온 파인드를 적용하면 이 문제는 매우 쉽게 해결 할 수 있다 유니온 파인드에 대해서 잘 모른다면 이에 대해 학습하고 문제 풀기를 추천한다!! 모든 노드들을 연결하면서 노드들을 연결하기..
[프로그래머스] 타일 장식물
[프로그래머스] 타일 장식물
2020.05.25문제 : Level3 타일 장식물 [ 문제출처 ] https://programmers.co.kr/learn/courses/30/lessons/43104 [ 문제풀이 ] 문제는 다음과 같은 타일이 있을 때 안쪽 타일 부터 시작해서 [1, 1, 2, 3, 5, 8, .... , ] 처럼 점점 타일이 확장된다 정답은 N개의 타일로 구성된 직사각형의 둘레를 구하는 것이다 규칙이 보이지 않는가? n번째 타일의 한 변의 길이는 밑에 식과 같이 정의가 가능 하다. 한 변의 길이를 정의하였으니 N번째 타일을 하나씩 붙여 가면서 직사각형 둘레의 길이는 어떻게 변하는지 살펴보자 기존에 있던 빨간색의 타일에서 파란색 타일이 추가된 상황이다 타일의 겹치는 부분의 길이를 파란색 타일의 윗변으로 생각해주고 즉 왼쪽 오른쪽 양변의..