PS
[프로그래머스] 네트워크
[프로그래머스] 네트워크
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번째 타일을 하나씩 붙여 가면서 직사각형 둘레의 길이는 어떻게 변하는지 살펴보자 기존에 있던 빨간색의 타일에서 파란색 타일이 추가된 상황이다 타일의 겹치는 부분의 길이를 파란색 타일의 윗변으로 생각해주고 즉 왼쪽 오른쪽 양변의..
[SWEA 1204] (D2) 최빈수 구하기
[SWEA 1204] (D2) 최빈수 구하기
2020.05.20문제 : (D2) 1204 - 최빈수 구하기 [ 문제 출처 ] : SW Expert Academy [ 문제 풀이 ] 다음과 같은 수 분포가 있으면, 10, 8, 7, 2, 2, 4, 8, 8, 8, 9, 5, 5, 3 10 : 1번 8 : 4번 7 : 1번 2 : 2번 .... .... 위와 같이 가장 8이라는 숫자가 4번으로 가장 많이 등장한다 이를 최빈수 라고 한다 점수의 분포는 0점 ~ 100점 까지 존재 한다. 문제에서 학생의 수는 1000명 이라고 정의 하였으므로 1000명의 점수를 입력 받을 때 마다 해당 점수를 카운트 해준다 이는 배열을 이용하여 쉽게 구현 할 수 있다 다음으로 해당 답을 찾기 위해서 그 배열을 순회 하면서 최빈수 이면서 가장 큰 점수를 구하면 된다 [ 소스 코드 ] 1 2 ..
[SWEA 1210] (D4) Ladder1
[SWEA 1210] (D4) Ladder1
2020.05.19문제 : (D4) 1210 - Ladder1 [ 문제 출처 ] : SW Expert Academy [ 문제 풀이 ] 이 문제는 시뮬레이션 문제이다 문제에서 구하고자 하는 값은 도착점 2에 대응 되는 출발점의 인덱스 번호를 구하는 것이다 바로 무작정 문제를 풀려고 한다면 위에서 부터 출발 가능 한 점에서 시작 하여시뮬레이션을 하면서 2를 찾으려 할 것이다 즉, 모든 방법을 모두 시도 해보려 할 것이다 하지만 이는 매우 비효율적이다 사다리 타기 게임은 많이들 해봐서 알수 있듯이 출발점과 도착점은 1대1 대응 이다 따라서 반대로 2에서 출발하면 구하고자 하는 값을 단 한번의 시도로 찾을 수 있을 것이다 이 문제는 방향을 코드에 적절하게 구현 해야 하며 조금신경 써야할 부분이라고 하면은 배열의 범위에 값에 벗어..
[프로그래머스] 주식가격
[프로그래머스] 주식가격
2020.05.18문제 : Level2 주식가격 [ 문제 출처 ] https://programmers.co.kr/learn/courses/30/lessons/42584 [ 문제 풀이 ] 내가 이 문제를 처음 봤을 땐 어디서 풀어 본 문제 같은데?라는 생각을 했다 비슷한 문제를 풀어 봤기에 어렵지 않게 풀 수 있었다 찾아보니 BOJ에서 오큰수 문제이고 풀이 방식도 조금만 다를 뿐 매우 유사하다. [문제 출처 ] : https://www.acmicpc.net/problem/17298 프로그래머스에는 문제의 분류로 스택을 사용함을 지시하였지만 BOJ 문제에서는 이를 모르고 스택을 사용하지 않을 경우 "시간 초과"가 나지 않을까 싶다.. (물론 스택사용 외에도 다른 풀이가 존재 할 수 있다!) 만약 이 문제를 처음 접하고 스택의..