본문 바로가기

전체 글46

[프로그래머스] 네트워크 문제 : 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.
[SWEA 1204] (D2) 최빈수 구하기 문제 : (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 .. 2020. 5. 20.
[SWEA 1210] (D4) Ladder1 문제 : (D4) 1210 - Ladder1 [ 문제 출처 ] : SW Expert Academy [ 문제 풀이 ] 이 문제는 시뮬레이션 문제이다 문제에서 구하고자 하는 값은 도착점 2에 대응 되는 출발점의 인덱스 번호를 구하는 것이다 바로 무작정 문제를 풀려고 한다면 위에서 부터 출발 가능 한 점에서 시작 하여시뮬레이션을 하면서 2를 찾으려 할 것이다 즉, 모든 방법을 모두 시도 해보려 할 것이다 하지만 이는 매우 비효율적이다 사다리 타기 게임은 많이들 해봐서 알수 있듯이 출발점과 도착점은 1대1 대응 이다 따라서 반대로 2에서 출발하면 구하고자 하는 값을 단 한번의 시도로 찾을 수 있을 것이다 이 문제는 방향을 코드에 적절하게 구현 해야 하며 조금신경 써야할 부분이라고 하면은 배열의 범위에 값에 벗어.. 2020. 5. 19.
[프로그래머스] 주식가격 문제 : Level2 주식가격 [ 문제 출처 ] https://programmers.co.kr/learn/courses/30/lessons/42584 [ 문제 풀이 ] 내가 이 문제를 처음 봤을 땐 어디서 풀어 본 문제 같은데?라는 생각을 했다 비슷한 문제를 풀어 봤기에 어렵지 않게 풀 수 있었다 찾아보니 BOJ에서 오큰수 문제이고 풀이 방식도 조금만 다를 뿐 매우 유사하다. [문제 출처 ] : https://www.acmicpc.net/problem/17298 프로그래머스에는 문제의 분류로 스택을 사용함을 지시하였지만 BOJ 문제에서는 이를 모르고 스택을 사용하지 않을 경우 "시간 초과"가 나지 않을까 싶다.. (물론 스택사용 외에도 다른 풀이가 존재 할 수 있다!) 만약 이 문제를 처음 접하고 스택의.. 2020. 5. 18.
Codeforces Round #642 (Div. 3) [못푼 문제] 처음에 치렀던 코드포스 Div3 문제들을 시간 내에 못 푼 문제 들을 다시 한번 풀어 보았다. 물론 진짜 못 풀 겠는 문제들은 구글링을 통하여 해법을 어느정도 제시받았다. 처음이었던 만큼 (핑계이기도 하지만) 모든 면에서 미숙하게 문제를 접근하고 풀었던 것 같다. 문제들은 뒤로 갈수록 어려워진다는 것은 알고 있어서 최대한 1-3번 문제들을 위주로 풀어 보려고 했었던 것 같다. [C. Board Moves] 이 문제는 다시 풀어보니 조금 쉬운 Dp 문제였다 내가 대회 도중 이 문제에 대해서 접근했을 때는 예제 입력 조차 이해가 안 되었고 막상 생각 하기를 단순한 수학 문제나 분할 정복 문제일 것이라고 생각을 했지만 이는 아니었다. 예제 입력 조차 이해를 못 한 것에는 내가 영어 지문을 해석을 제대로 해석을.. 2020. 5. 18.
Codeforces Round #642 (Div. 3) 생전 태어나서 처음으로 코드포스 콘테스트에 참여해보았다. 친구들과 밥을 먹고나서 웹툰을 좀 보면서 쉬려고 하다가 전에 신청해놓은 코드포스가 언제였는지 보려고 사이트에 들어갔다가 대회가 시작 한지 15분 정도 지나있다는 것을 알게 되었다... 하.. 쉴지 말지를 한참 고민을 하던 중에 그래 한번 보자!! 해서 콘테스트를 치르게 되었다 물론 보던 웹툰은 다보고 나서 하지만 결과는 크음 ..... 처음인 만큼 결과는 아주 참담했다 .....ㅠㅠㅠㅠ 아니 ? 처음 이여도 잘하는 사람은 많겠지 ... 결과는 6문제 중 2문제를 풀었다... 밑에 사진은 내가 코드를 제출한 이력이다.. 이 두 문제는 각 10분씩 투자해서 풀 수 있었다.. 오?! 할 만 한데?라고 생각이 들었지만 이는 뒤로 갈수록 아니었다.. 나의 .. 2020. 5. 15.
[프로그래머스] 카카오 프렌즈 컬러링북 문제 : 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.

티스토리툴바