블로그 이름 뭐로 하지

문제 https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 정말정말.. 생각보다 너무너무 오래걸린 문제..ㅠ 문제를 보자마자 내가 정말 애정.하는 bfs문제임을 알았고, 그냥 벽만 피해서 최소비용 구하면 되겠다! 하고 생각을 했다. 이 문제가 기본 bfs의 최소비용문제와 달랐던 점은 바로 '코너'비용을 계산하는 것이었는데, 나는 처음 시작때만 방향 값을 -1을 두어 따로 분기 처리를 해주었고, 그 뒤부터는 현재 좌표로 오기 이전에 (위-아래) ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 그래프 관련 문제라기보단 단순 구현 문제이다. 이 문제에서 필요한건... 각 노드의 진입차수와 진출차수 이다. 생성된 노드 - 진입차수 0, 진출 차수 2 이상인 노드 막대 그래프 - 진입차수가 0인 노드가 있는 그래프 8자 그래프 - 진입 차수 2, 진출 차수 2인 노드가 있는 그래프 도넛 그래프 - 생성된 노드의 진출 차수(전체 그래프의 개수) - (위에서 구한 막대 그래프 개수 ..

문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 유니온 파인드를 사용해서 풀었다. union - 두 노드 중 작은 노드를 큰 노드의 부모 노드로 지정하는 함수 find - 노드의 루트 노드를 찾는 함수 부모 노드가 똑같은 두 노드 연결되면 사이클이 생긴것으로 판단하고 해당 과정을 result에 담는다. 코드 import sys input = sys.stdin.readline n, m = map(int,input().split()..

문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 저번에 2252 - 줄 세우기 문제에서 위상정렬에 대해 공부했었는데 이 문제도 위상정렬 문제여서 반가웠다. ㅎ 이쯤되면 클래스 5가 전부 다 그래프 문제인가 싶은..^ _ ^ . . . 위상 정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 이다. 위상 정렬 문제의 특징 중 하나는 답안이 여러개일 수 있다는 점이다. 진입차..

문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 최소 스패닝 트리를 조금 활용한 문제...? 라고 보면 될 것 같다. 프림 알고리즘을 이용해서 풀었고, 일반적으로 그래프 문제들은 연결돼있는 간선과 노드의 정보를 주는 경우가 많은데 얘는 그 정보를 두 점 사이의 거리를 활용해서 직접 만들어야 하는 문제였다. math.sqrt를 통해 제곱근을 구했고, 소수점 둘째자리까지만 활용하기 위해 round 함수를 사용했다. 이 외에는 일반적인 프림..

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 트리 - 사이클이 존재하지 않는 그래프 스패닝(신장) 트리 - 그래프 내의 모든 노드를 포함하면서 사이클이 없는 부분 그래프 최소 신장 트리 - 그래프 내의 모든 노드를 포함하면서 사이클이 없는 부분 그래프 중 가중치의 합이 최소가 되는 신장 트리 최소 신장 트리를 구할 수 있는 알고리즘에는 프림, 크루스칼 알고리즘이 있다. 크루스칼과 프림..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 가장 적은 비용의 간선부터 차례대로 사이클이 발생하지 않도록 연결해주면 최소비용신장트리를 구할 수 있다. (크루스칼 알고리즘) 코드 def solution(n, costs): answer = 0 # 비용이 가장 적은 간선부터 정렬 costs.sort(key = lambda x: x[2]) # 처음 시작 노드 넣고 시작 link = set([costs[0][0]]) # Kruskal 알고..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 맨해튼 거리가 2인 경우를 크게 3가지로 나눠서 확인했다. 1. 맨해튼거리가 1인 경우 중 동서남북 1칸 차이인 경우 -> 이 때는 칸막이고 뭐고 체크할 필요 없이 P가 나오면 무조건 거리두기 F 2. 맨해튼거리가 1인 경우 중 대각선 1칸 차이인 경우 -> 이 때는 사이에 칸막이가 있는지 체크해야한다. 만약 (1,-1) 만큼 차이 나는 경우 (0,-1) , (1,0) 이 칸막이(X)인..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음 시도 그냥 while문 안에서 for문 돌면서 -1씩 해주고 연속된 0이 k만큼 되면 못 건너는걸로 판단하고 break. ㅋㅋ ㅠㅠ 당연히 시간 초과. 징검다리 최고 숫자가 무려 200,000,000이고 징검다리도 200,000개이므로... 만약 죄다 200,000,000이 써져 있는 200,000개의 징검다리가 있다고 치면 내 코드는 그냥 쓰레기 코드가 된다 :) def solu..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17679 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 2018 카카오 문제...! 확실히 이 때는 시뮬이나 그래프 문제들이 많이 나왔던 것 같다. 지금은... 더보기 삼성 기출 풀어본 사람 특: 이런 구현 문제 되게 좋아함 하라는대로 하면 된다. 2*2 같은 거 있으면 체크해주고 한 번에 0으로 바꿔준다. down 함수를 통해서 빈 공간을 채우기 위해 위에 떠있는 아이들을 내려준다. 코드 from collections import dequ..