![]()
https://www.acmicpc.net/problem/1504알고리즘출발점이 1 종료지점이 n이고 v1, v2를 지나는 최단경로의 길이를 출력하는 문제이다. 가능한 경로는1 -> v1 -> v2 -> n / 1 -> v2 -> v1 -> n 두가지 경로가 존재하므로 각각의 경우를 전부 계산해서 더해준 뒤에 더 작은 값을 출력해주면 된다.출발점을 1, v1, v2 로 하여 다익스트라를 진행한 뒤에 각각의 경우를 더해서 최단경로를 계산해주었다.모든 경우마다 다익스트라를 실행하면 시간이 많이 소요되기 때문에, 각각의 경우에 대해 1번씩만 수행한 뒤에 distance배열을 리턴값으로 받아서 마지막에 더해주었다.코드import sysimport heapqinput = sys.stdin.readlineINF ..
문제https://www.acmicpc.net/problem/2852문제동혁이는 NBA 농구 경기를 즐겨 본다. 동혁이는 골이 들어갈 때 마다 골이 들어간 시간과 팀을 적는 이상한 취미를 가지고 있다.농구 경기는 정확히 48분동안 진행된다. 각 팀이 몇 분동안 이기고 있었는지 출력하는 프로그램을 작성하시오.입력첫째 줄에 골이 들어간 횟수 N(1출력첫째 줄에 1번 팀이 이기고 있던 시간, 둘째 줄에 2번 팀이 이기고 있던 시간을 출력한다. 시간은 입력과 같은 형식(MM:SS)으로 출력한다. Algorithm'지금 이기고 있는 팀' 과 '승패가 바뀌었을 때의 시간'을 저장하는 변수 winteam, wintime을 선언한다.또한 팀별로 점수와, 시간을 저장해 비교해야 하므로 teamgoal, timedict ..
https://www.acmicpc.net/problem/13424입력입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방의 개수 N (2 ≤ N ≤ 100), 비밀통로의 개수 M(N-1 ≤ M ≤ N(N - 1)/2)이 공백으로 구분되어 주어진다. 그 다음 줄부터 M개의 줄에 걸쳐 비밀통로의 정보(a, b, c)가 주어진다. a와 b는 비밀통로로 연결된 두 방의 번호이며 c는 a와 b를 연결하는 비밀통로의 길이이다. a와 b는 항상 다르며 c는 1 이상 1,000 이하의 자연수이다. 두 방을 연결하는 비밀통로는 반드시 하나씩만 존재한다. 또한 어떤 방에서 다른 방으로..
문제 https://www.acmicpc.net/problem/4485 Algorithm- 다익스트라 알고리즘 사용했당 Codeimport java.util.*;import java.io.*;public class Main { static class Node implements Comparable{ int x; int y; int cost; public Node(int x, int y, int cost) { this.x = x; this.y = y; this.cost = cost; } @Override public int compareTo(Node o) { return this.cost - o.cost; } } static int n; static int[][]..
문제우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.입력사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사..
문제 https://www.acmicpc.net/problem/1759문제바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.새 보안 시스템에서 조교들이 암호로 사용했을 법한 문..
![]()
문제 https://www.acmicpc.net/problem/4963 Algorithm Codeimport sysfrom collections import dequeinput = sys.stdin.readlinedx = [0,0,1,-1,1,-1,1,-1]dy = [1,-1,0,0,1,1,-1,-1]def BFS(x,y): queue = deque() queue.append([x,y]) graph[y][x] = 0 while queue: x,y = queue.popleft() for i in range(8): next_x = x + dx[i] next_y = y + dy[i] ..
https://www.acmicpc.net/problem/2583입력첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. 출력첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다. 문제 코드from collections import dequ..
![]()
https://www.acmicpc.net/problem/31575알고리즘좌측상단에서 우측하단까지의 길을 찾는 문제이다. 2차원인 배열을 1차원으로 바꾸어 그래프에 적용하였다. 현재 위치가 1인 상태에서 오른쪽이 1이면 이동가능이므로 그래프에 추가, 아래가 1이면 이동가능이므로 그래프에 추가한 뒤에 dfs를 실행한다.마지막 위치의 visited배열을 검사하여 True면 이동이 가능하므로 Yes를 출력해준다.dfs로 해결했지만, dp로도 풀 수 있는 문제인 것 같다.코드import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)def dfs(graph, v, visited): visited[v] = True for i in graph[v]:..
![]()
https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr알고리즘 유형깊이/너비 우선 탐색(DFS/BFS)문제 설명다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다. 지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다. 만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다. 단, 서로 다른 두 직사각형의 x축 좌표 또는 y..
문제 https://www.acmicpc.net/problem/16713 Algorithm누적합누적합이 아니라 매번 모든 쿼리를 계산하면 시간 초과가 난다.또한 베타적 논리합(XOR, ⊻)이 결합법칙이 성립함을 알고 있어야 한다.예를 들어 (a1 ⊻ a2 ⊻... a10) = (a1 ⊻ a2) ⊻ (a3 ⊻ a4 ⊻ ... a10) 이다.그리고 A ⊻ B = C 일 때, C ⊻ A = B, C ⊻ B = A 이다.추가적으로 0 ⊻ N = N 임을 알고 있어도 도움이 된다. Codeinput = __import__('sys').stdin.readlineN, Q = map(int, input().rstrip().split())a_list = list(map(int, input().rstrip().spl..
![]()
문제 https://www.acmicpc.net/problem/7795문제심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모..
