블로그 이름 뭐로 하지

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

문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 사이클이 없는 방향 그래프에서 방향성이 한 곳만을 향하도록 정렬하는... 위상정렬...이란다. 나는 위상정렬이라는 개념은 몰랐고 그래프를 통해서 풀면 되겠다 싶긴했는데 정답을 도출하기가 참 어려웠다 ㅡ ㅡ 그래서 검색해보니 위상정렬의 대표적이 문제라더라. https://youtu.be/xeSz3pROPS8 1. 진입 차수가 0인 모든 노드를 큐..

문제 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 RGB거리1 문제와는 다른 조건이 하나 더 걸려있다. 바로 1번 집과 마지막 집의 색이 동일하면 안 된다는 점. 따라서 1. 1번 집을 R로 색칠하고 N번집을 G 또는 B로 칠한 경우 2. 1번 집을 G로 색칠하고 N번 집을 R 또는 B로 칠한 경우 3. 1번 집을 B로 색칠하고 N번집을 R 또는 G로 칠한 경우 각 세계의 경우에 따라 dp를 수행하고 각 경..