프로그래머스9 [프로그래머스] 단어변환 문제 : 단어 변환 [ 문제 출처 ] https://programmers.co.kr/learn/courses/30/lessons/43163 [문제 풀이] 이 문제의 경우 주어진 문제를 그래프로 표현할 수 있어야 한다 즉 "그래프 모델링"을 해주어야 한다 어떤 것을 그래프의 정점으로 사용할 것이고 정점과 정점을 잇는 간선의 연결은 어떻게 정할 것인지 등이 있다 이 문제의 그래프 모델링 과정을 살펴보자! 정점은 어떤 것으로 사용해야 할 까? words에 있는 단어로 하면 좋지 않을까? 정점과 정점을 잇는 간선은 어떻게 연결시켜야 할까? 알파벳을 단 한 개만 바꾸어 해당 단어로 표현할 수 있다면 이는 연결 되었다고 볼 수 있다 즉 "hot" --> "hit" , "hot" --> "dot" 알파벳 차이가 단 .. 2020. 6. 17. [프로그래머스] 기능개발 문제 : 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. 6. 10. [프로그래머스] 카드 게임 문제 : Level4 카드 게임 [ 문제출처 ] https://programmers.co.kr/learn/courses/30/lessons/42896 [ 문제풀이 ] 처음에 문제를 이해 하기를 문제에서 제시된 조건 1 부분에서 1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다 이 부분에서 이해가 가질 않았다 역시 국어를 못하니 문제를 빠르게 파악하지를 못하는 것 같다 ㅠㅠ 제시된 조건도 1과 2로 나누어 주었으면 좋지 않았나 싶기도 하다 얻는 점수가 없는 경우를 묶어서 조건으로 내민 것 같다 게임에서 가능한 경우를 보자 조건 : 어느쪽 더미든 카드가 없어질 때까지 1. 왼쪽 카드를 버리자 2. 왼쪽과 오른쪽 카드를 동시에 버리.. 2020. 6. 3. [프로그래머스] 네트워크 문제 : Level3 네트워크 [ 문제출처 ] https://programmers.co.kr/learn/courses/30/lessons/43162 [ 문제풀이 ] 이 문제는 컴퓨터의 연결 정보가 주어 질 때 이 연결 정보를 통해서 몇 개의 네트워크가 존재하는지를 구하는 문제이다 BFS 탐색을 통해서 연결되어 있는 모든 컴퓨터 즉, 모든 노드 탐색하면서 방문한 노드를 check 배열에 표시해 주었다 정답은 BFS의 호출 횟수이다 여기서 주의할 점은 컴퓨터의 연결 정보가 인접 리스트가 아닌 인접 행렬로 주어진다는 점이다 그 점만 주의해서 BFS 탐색 코드만 잘 짜주면 된다. [소스 코드] 123456789101112131415161718192021222324252627282930313233#include .. 2020. 5. 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. 5. 25. [프로그래머스] 타일 장식물 문제 : Level3 타일 장식물 [ 문제출처 ] https://programmers.co.kr/learn/courses/30/lessons/43104 [ 문제풀이 ] 문제는 다음과 같은 타일이 있을 때 안쪽 타일 부터 시작해서 [1, 1, 2, 3, 5, 8, .... , ] 처럼 점점 타일이 확장된다 정답은 N개의 타일로 구성된 직사각형의 둘레를 구하는 것이다 규칙이 보이지 않는가? n번째 타일의 한 변의 길이는 밑에 식과 같이 정의가 가능 하다. 한 변의 길이를 정의하였으니 N번째 타일을 하나씩 붙여 가면서 직사각형 둘레의 길이는 어떻게 변하는지 살펴보자 기존에 있던 빨간색의 타일에서 파란색 타일이 추가된 상황이다 타일의 겹치는 부분의 길이를 파란색 타일의 윗변으로 생각해주고 즉 왼쪽 오른쪽 양변의.. 2020. 5. 25. [프로그래머스] 주식가격 문제 : Level2 주식가격 [ 문제 출처 ] https://programmers.co.kr/learn/courses/30/lessons/42584 [ 문제 풀이 ] 내가 이 문제를 처음 봤을 땐 어디서 풀어 본 문제 같은데?라는 생각을 했다 비슷한 문제를 풀어 봤기에 어렵지 않게 풀 수 있었다 찾아보니 BOJ에서 오큰수 문제이고 풀이 방식도 조금만 다를 뿐 매우 유사하다. [문제 출처 ] : https://www.acmicpc.net/problem/17298 프로그래머스에는 문제의 분류로 스택을 사용함을 지시하였지만 BOJ 문제에서는 이를 모르고 스택을 사용하지 않을 경우 "시간 초과"가 나지 않을까 싶다.. (물론 스택사용 외에도 다른 풀이가 존재 할 수 있다!) 만약 이 문제를 처음 접하고 스택의.. 2020. 5. 18. [프로그래머스] 카카오 프렌즈 컬러링북 문제 : Level2 카카오 프렌즈 컬러링북 [ 문제출처 ] https://programmers.co.kr/learn/courses/30/lessons/1829 [ 문제풀이 ] 이 문제는 주어진 배열에서 영역의 개수를 구하고 가장 큰 영역의 칸의 개수를 구하는 문제이다 이 문제는 BFS 를 이용하여 쉽게 해결 하였다. 배열의 원소를 순회 하면서 0이 아닌 칸과 방문하지 않은 칸을 만나게 되면 BFS 함수를 호출 한다. - (BFS 의 반환값으로 해당 영역의 칸의 개수가 반환된다) 이 때 가장 큰 영역의 칸의 개수를 갱신 해준다. [ 소스코드 ] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 .. 2020. 5. 14. [프로그래머스] 크레인 인형뽑기 게임 문제 : Level1 크레인 인형 뽑기 게임 [ 문제출처 ] https://programmers.co.kr/learn/courses/30/lessons/64061 [ 문제풀이 ] 이 문제는 친절하게도 Stack 을 사용하게끔 해당 문제의 그림에서도 유도해주었다. 크레인을 작동시킬 위치가 담긴 배열 moves 에서 차례로 하나씩 값을 꺼내어 해당 위치의 열에서 가장 위에 있는 값을 스택에 넣어 주면 된다. 이 부분을 따로 함수로 구현해 주었다 하지만 2가지 상황이 존재한다. 1. 해당 위치의 열에 뽑을 인형이 없는 경우 --> -1 을 Return 2. 뽑을 인형이 존재 --> 해당 자리에 0을 넣고 인형의 모양을 의미하는 숫자를 Return 바구니에 담는 과정에서 터지는 상황을 생각해보자 아니, 일단 바.. 2020. 5. 14. 이전 1 다음
