본문 바로가기

Archived(CSE Programming)

 (169)
프로그래머스 - 섬 연결하기(Java, LV3) / MST https://programmers.co.kr/learn/courses/30/lessons/42861?language=java 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 해당 문제는 graph의 MST(Minimum Spanning Tree) 최소연결간선 트리 찾기 문제로 크루스칼 알고리즘으로 해결 가능하다. 먼저, 주어진 전체 costs를 비용 순으로 정렬 후 사이클체크를 하면서 사이클이 형성되지 않는다면 해당 간선을 연결한다. 연결하면서 두 노드를 union 해준다. 그렇게 전체 costs를 탐색하면서 MST가 구성되었다면 중단하여 지금까지 계산한 비용을 반환한다. import java.uti..
프로그래머스 거스름돈(Java, LV3) /DP https://programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5�� programmers.co.kr 풀이 DP 문제 중 가장 대표중인 문제, 화폐 거스름돈과 유사한 문제이다. 단, 차이점은 지불할 수 있는 방법의 수를 계산하는 것이다. 점화식을 세우고 진행하는데, 2차원 배열을 통해 처음 접근했다. d[i][j] = i개의 화폐(moeny[0..i])로 j 금액을 낼 수 있는 방법 수 d[i][j] = d[i-1][j] + d[i][j-mone..
프로그래머스 - 멀쩡한 사각형(Java, LV2) https://programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 �� programmers.co.kr 풀이 해당 문제는 사각형 패턴의 규칙을 찾는 것이 관건이었다. (나는 3개의 예제를 그려보며 패턴이 있음을 파악했다... 수학적 사고가 뛰어난 사람들은 저게 1차함수를 활용하는 문제임을 알고 푼 듯하다) 먼저 대각선이 그어지는 패턴을 보면 어느 꼭짓점(좌표)에서 딱 맞게 떨어진다. 그림 출처 : ajufresh.log 그렇기에, ..
프로그래머스 - 주식가격(Java, LV2) https://programmers.co.kr/learn/courses/30/lessons/42584?language=java 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr prices의 해당 값이 떨어졌을 때 그 시점의 인덱스 차이를 넣어주면 된다. 단, 값이 떨어질 경우없이 끝까지 갔을 경우에는 -1을 해줘야함(끝까지 간 경우는 index를 1 초과했으므로) 그리고 마지막 값은 무조건 0 이므로 계산해주지 않아도 된다. 아무리 생각해도 O(n^2)을 극복하는 방안..
커리큘럼(파이썬) / 위상 정렬(topology sort) 문제 온라인 컴퓨공학강의를 듣고 있다. 이 때, 각 온라인 강의는 선수강의가 있을 수 있다. 1번부터 N번 까지 강의가 주어지고 그에 따른 선수강의가 있을 경우, 각 강의를 듣는데 걸리는 시간을 모두 출력하라. 입력 첫째 줄에 동빈이가 듣고자 하는 강의 수 N이 주어진다(1 0 -> 3 일 경우 다시 0을 파싱하지 않아서 무한루프를 돈다. import sys from collections import deque sys.stdin = open("input/input_10-4.txt" ,"r") sys.stdout = open("ouput_10-2.txt", "w") # input n = int(input()) answer = [0] * (n) prev_list = [] visit = [] # main fo..
[백준 1647번] 도시 분할 계획(파이썬) / 크루스칼(MST) 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개의..
팀 결성(파이썬) / 사이클 체크 문제 학교에서 학생들에게 0번부터 N번까지 팀 번호를 부여ㅑ했다. 모든 학생이 다른 팀으로 시작하는데 이 때, 연산을 통해서 팀이 결성된다. 1. '팀 합치기' 연산은 두 팀을 합치는 연산이다. 2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력해라. 입력 첫째 줄에 N, M(연산횟수) 이 주어진다(1
전보 (파이썬) / 최단경로(다익스트라) 문제 어떤 나라에 N개의 도시가 있다. X에서 Y로 향하는 통로가 있으면 X->Y는 보낼 수 있지만 Y->X로는 따로 통로가 있어야 한다. 특정 도시에서 다른 도시로 전부 전보를 보내기 위해서 필요한 시간은 얼마인지 계산하라. 입력 첫째 줄에 도시의 개수 N, 통로의 개수 M, 메세지를 보내고자 하는 도시 C가 주어진다. (1

티스토리툴바