출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # n명의 권투 선수들은 1부터 n까지 번호를 가짐 # results는 경기 결과 배열 # 경기 결과 A B는 A가 B를 이겼음을 표시 # 순위를 매기려 하는데 몇몇 경기 결과 분실 # 알고있는 경기 결과를 통해 순위를 확실히 알 수 있는 선수의 수를 return 더보기 풀이 def solution(n, results): answer = 0 INF = float('inf')..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # n개의 노드가 있는 그래프에서각 노드는 1~n으로 주어짐 # 가장 멀리 떨어진 노드란 최단경로로 이동 했을 때 간선의 개수가 가장 많은 노드 # 1번 노드로부터 가장 멀리 떨어진 노드의 개수 더보기 먼저, 생각해야 할 부분 1. 1번 노드로부터의 최단 경로를 찾고 있다 -> 다익스트라 알고리즘 2. BFS를 이용한 풀이 역시 가능하다. 다익스트라를 이용한 풀이 from ..
출처 : 이것이 취업을 위한 코딩테스트다 with Python, 숨바꼭질 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. hanbit.co.kr 더보기 다익스트라 풀이 import sys from collections import Counter from heapq import heappop, heappush INF = float('inf') def solution(n, pass_list): #1번으로부터 최단 거리가 가장 먼 노드를 찾음. ad_matrix = [[INF for _ in range(n)] for _ in range(n)] # 인..
다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 그래프의 한 노드에서 모든 노드까지의 최단 거리를 구하는데 사용됩니다. 플로이드 워셜 vs 다익스트라 플로이드 워셜은 모든 노드에서 다른 모든 노드까지의 최단 거리를 구하는 용도인 반면, 다익스트라는 시작점을 1개의 노드로 정하고 이 노드로부터 다른 모든 노드까지의 최단 거리를 구합니다. BFS vs 다익스트라 BFS와 다익스트라 모두 최단 거리를 구하기 위한 알고리즘으로 사용될 수 있습니다. 단, BFS는 가중치가 없는 그래프인 경우에 최단 거리 문제를 푸는 방법이고, 다익스트라는 가중치가 다양한 경우에 최단 거리 문제를 푸는 방법입니다. 가중치가 없는 경우 모든 칸에 대해서 1번 이동하는 것이 동일한 가중치를 가진다 볼 수 있기 때문에, 가장..
출처 : 이것이 취업을 위한 코딩테스트다 with Python, 화성 탐사 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. hanbit.co.kr 더보기 먼저, 생각해야 할 부분 1. 한 곳에서 다른 곳까지 이동할 때 최소 비용을 구하는 문제이다. (최단 거리 문제) 단, 이동 시 가중치가 다 다르다 -> 다익스트라로 풀어야한다. 2. 가중치 그래프 설정 방법 - 하나의 칸에 있는 값을 칸을 나가기 위한 값으로 설정한다 - 칸에 도착할 경우에도 에너지가 소모되므로, 이 경우 최단 거리 return 시 마지막 칸의 값을 별도로 더해주어야한다. 풀..
출처 : 이것이 취업을 위한 코딩테스트다 with Python, 정확한 순위 이것이 취업을 위한 코딩 테스트다 with 파이썬 IT 취준생이라면 누구나 가고 싶어 하는 카카오, 라인, 삼성전자의 2016년부터 2020년까지의 코딩 테스트와 알고리즘 대회의 기출문제를 엄선하여 수록하였다. hanbit.co.kr 더보기 먼저, 생각해야 할 부분 1. n명 중 정확한 순위를 알 수 있다는 것은 내 아래로 A명과 내 위로 B명을 더했을 때 n-1 명이라는 것과 같다. 2. 내 점수보다 아래 혹은 위임을 알 수 있는 방법은 해당 노드를 방문할 수 있는지 여부를 통해 알 수 있다. 3. r = 점수가 낮은 학생, c = 점수가 높은 학생으로 정했을 때, 1번 행은 1보다 1번 학생보다 점수가 높은 학생들의 방문 가..
플로이드-워셜(Floyd-Warshall) 알고리즘 플로이드 워셜 알고리즘은 그래프의 모든 노드에서 다른 모든 노드로 가는 최소 비용을 구하는 알고리즘입니다. 원리 1에서 3으로 가는 최단 거리를 구한다고 생각해봅시다. 1에서 3으로 바로 가는 거리는 13입니다. 하지만, 1에서 2로 갔다가, 2에서 3으로 가는 거리는 2 + 3으로 5입니다. 즉, 2를 거쳐가는 1 -> 2 -> 3이 최단 거리가 됩니다. 위와 같이 플로이드 워셜 알고리즘은 현재 내가 알고 있는 최단 거리와 다른 노드를 거쳐갈 때의 최단 거리를 비교하여 갱신합니다. 이를 점화식으로 나타내면 다음과 같습니다 # A에서 B로 가는 최단 거리 D[A][B] # 경유 노드 K D[A][B] = min(D[A][B], D[A][K] + D[K]..
출처 : 백준, https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net # n개의 도시 사이를 운행하는 m개의 버스가 있음 # A B C -> A 도시에서 B 도시로 가는 비용 C # 가격이 다른 동일 노선이 존재할 수 있음. # 각 도시에서 다른 도시로 가는 최소 비용을 출력 # 갈 수 없을 경우 0 출력 더보기 먼저, 생각해야 할 부분 1. 가격이 다른 동일 노선이 존재할 수 있다. 2. 모든 도시에서 모든 도시로 가는 최소 비용을 구해야한다. -..
출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr # 비내림차순 정렬(점점 증가하는 수열)이 주어질 때 # 시작idx와 길이가 가장 작으면서 내부 요소 총합이 k인 부분 수열의 [시작 idx, 끝 idx]를 return 더보기 먼저, 생각해야 할 부분 1. 조합으로 풀기에는 sequence가 1,000,000개까지 존재할 수도 있다. 수열의 부분합을 빠르게 구할 수 있는 다른 방법은 무엇이 있을까? Two Pointer를..
본 글은 FEConf Korea에서 최수형님의 프론트엔드에서 TDD가 가능하다는 것을 보여드립니다 발표를 보고 정리한 글입니다. TDD의 궁극적인 목적 Clean Code that works : 작동하는 깔끔한 코드 왜 어려운가? 코드 자체가 Testable 하지 않아서 그렇다. 어떻게? 관심사 분리 → 개개의 요소가 자신이 관심 갖고 있는 요소에만 집중해야 TDD를 쉽게 할 수 있다. 이를 지키지 않으면 거대한 진흙 덩어리가 된다. 일단 테스트를 통과하기 위한 코드를 짜라! → 그 후에 수정하자. 라이브코딩 React의 컴포넌트 테스팅 React에서 testing하기 위해서 testing-library/react를 사용 jest의 watchAll 모드를 통해 저장될 떄마다 자동으로 실행해서 확인 // ..
출처 : 백준, https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net # NxN의 지도가 주어진다 # 모든 칸의 높이가 같으면 길 # 길이가 다른 경우에는 경사로를 놓아서 길을 만들 수 있다. # 경사로의 높이는 항상 1이고 높이는 L # 경사로는 낮은 칸에 놓고, L개의 연속된 칸에 모두 접해야함. # 경사로의 낮은 칸과 높은 칸의 차이는 1이어야한다. # 경사로를 놓을 낮은 칸의 높이는 모두 같아야하고, L개의 연속된 칸이 있어야함. # 지나갈 수 있는 길의 갯수 더보..
출처 : 백준, https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net # n x n의 격자, m개의 파이어볼 # 1:n은 연결되어있다 # 파이어볼은 r, c, m, d, s의 정보로 주어진다 # 1 ≤ ri, ci ≤ N -> 1부터 시작함. # d는 0~7까지 12시 기준 시계 방향 8방향, s는 한번 움직이는 칸 수 # 이동이 모두 끝나고, 2개 이상의 파이어볼이 같은 칸에 있다면 # 모두 합친 후 4개로 ..
