![]()
https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답코드 # 2023-06-30 # 2023-07-12 # 복습 횟수:1, 00:30:00, 복습필요:*(세 달 뒤 쯤 복습하면 될듯 - 그때도 맞으면 끝) def solution(targets: list): answer = 0 targets.sort(key=lambda x: x[1]) end = 0 for target in targets: if target[0] >= end: answer +=..
문제 https://www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net Algorithm 재귀호출을 이용해서 풀었다. 이동횟수는 항상 2**n-1 1 1번 기둥에 N개 원판 있고,이를 3번 기둥으로 옮길때 2 1번 기둥에 위치한 N개의 원판 중 N-1 개를 2번으로 옮김 3 나머지 1개를 3번으로 옮김 4 2번 기둥에 있는 N-1개 원판을 3번 기둥으로 옮김 f(n,a,b,c): n개 원판 1번기둥 a, 2번기둥 b, 3번기둥 c n=1이면 하나 옮기면 끝 n>1..
![]()
문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net Algorithm n*n개의 타일에 퀸 n개를 서로 공격할 수 없게 되는 경우의 수를 출력하는 문제이다. 체스에서 퀸은 상하좌우, 대각선을 전부 이동할 수 있으므로 같은 열에는 둘 수 없다. n개의 열에 n개의 퀸을 두므로, 한 열에는 퀸이 1개만 존재해야한다. 순열을 재귀함수로 구현할때, 배열을 만들어서 선택이 가능한 경우에만 재귀함수를 돌리는 거에서 착안하여 재귀를 돌릴때마다 그 자리에 퀸을 두어도 되는..
![]()
문제 https://www.acmicpc.net/submit/1504/61065431 로그인 www.acmicpc.net Algorithm 다익스트라 알고리즘을 이용한다. 시작점이 정점 1인 경우에서 다익스트라 알고리즘을 수행했을 때와 시작점이 각각 정점 v_1, v_2인 경우에서 다익스트라 알고리즘을 수행했을 때의 결괏값 3개를 구한다. 이 결괏값을 각각 d_0, d_1, d_2이라 하면 이 결괏값들은 모두 리스트이다. 경로가 "정점 1->정점 v_1->정점 v_2->정점 N"일 때와 "정점 1->정점 v_2->정점 v_1->정점 N"일 때 중에서 길이가 더 짧은 경로의 길이를 출력한다. 다시 말해 d_{k-1}의 i번째 원소는(1
![]()
풀이 A -> B로 가는데 드는 최소비용을 구하는 문제이다 각 버스의 출발 도시와 도착 도시, 버스 비용을 그래프에 추가한다. 같은 출발 도시에서 여러 개의 버스가 있을 수 있으므로, 출발 도시를 인덱스로 하는 벡터에 도착 도시와 비용을 추가한다. 우선순위 큐를 사용하여 탐색할 도시와 그 도시까지의 비용을 저장하고, 시작 도시의 거리는 0으로 설정하고 큐에 추가한다. 큐에서 도시를 하나씩 꺼내면서 인접한 도시들을 탐색한다. 구간 출발점에서 도착점까지의 최소 비용인 distance[B]를 출력한다. 코드 #include #include #include #include using namespace std; const int INF = numeric_limits::max(); struct Edge { int ..
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 해결 1. n번의 마을에 사는 학생 1명이 x번 마을로 가는 최단 경로 값을 구해야한다. 즉, 1-2-3-4-...-n번 마을에 해당하는 학생이 x 마을에 가는 최단경로의 모든 값을 구해야한다. 2. n번 마을에서 x번 마을로 갔다가 돌아오는 왕복값을 계산해주어야 한다. 이때 도로가 단방향이므로 갈 때의 최단 경로와 돌아올 때의 최단 경로는 다르기 때문에 각각에..
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net Algorithm 양쪽으로 빼기 위해서 덱을 사용하였다.R의 개수가 홀수일 경우에만 뒤집기를 수행, flag 값을 통해 R의 개수를 카운트하고 짝/홀 여부를 판정한다."[]"라고 입력을 받아도 deque의 길이는 1이 되기 때문에 길이가 0인 부분에 대해서는 예외사항으로 빈 큐로 초기화를 해줘야 한다. 'R'이면,flag 변수가 1씩 증가 'D'이면, 덱 q의 길이가 0인지 확인한다. 만약 q가 비어있으면 'error'를 출력하고 반복문을 중단한다. 그..
![]()
23033번: 집에 빨리 가고 싶어! (acmicpc.net) 23033번: 집에 빨리 가고 싶어! 첫째 줄에 역의 수 N(2 ≤ N ≤ 20,000)과 노선 M개(1 ≤ M ≤ 300,000)가 주어진다. 둘째 줄 부터 M개의 줄에 걸쳐서 4개의 정수 A, B, T, W가 주어지고 A역에서 B역으로 가는 단방향 노선이 존재하며, 소요 www.acmicpc.net 코드 해석 역의 수 N, 노선 M을 입력 받음 a,b,t,w를 입력 받고 graph의 a행에 (b, t, w) 저장 시작 역부터 해당 역까지의 최소 시간을 저장하는 dist 리스트 생성 생성 직후 출발역에서는 0, 이외의 역에서는 INF(무한) 최소 시간이 작은 역부터 처리하기 위해 우선순위 큐인 q 사용 생성 직후 출발역인 0에서는 [0,1]..
![]()
https://www.acmicpc.net/problem/14497 문제 분석 난이도 골드 4 분류 그래프, 0-1 BFS 또는 다익스트라 문제 문제 풀이 풀이 주난이가 점프를 뛸 때마다 주난이와 이어진 0 주변의 1들이 사라진다고 생각하면 된다. 이것만 보고는 백준의 다른 너비우선탐색 문제들과 했갈릴 수 있지만 더 효율적으로 푸는 방법은 다익스트라이다. 그 이유는 0으로 된 부분을 이동하는데 가중치가 0이고, 1을 0으로 바꾸는데 가중치가 1이 들어가는 그래프로 생각하고 풀어줄 수 있기 때문이다. 위의 설명처럼 가중치가 0또는 1만 존재하기 때문에 0-1 BFS로도 해결이 가능한 문제이다. 다익스트라는 O(ElogV)의 시간복잡도, 0-1 BFS는 O(E+V)의 시간복잡도를 갖는다. 소스코드 다익스트라..
문제링크 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 코드 import sys import heapq input = sys.stdin.readline def dijkstra(x,y): q = [] distance[x][y] = 0 heapq.heappush(q,(0,x,y)) while q: dist,x,y = heapq.heappop(q) for i in range(4): nx = x + dx[i] ny = y + d..
![]()
문제 1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net Algorithm 1~n까지 숫자를 붙여서 썼는데, 일부분이 지워졌을때 최소의 n을 구하는 문제이다. 예시로 234092를 봐보자. 2는 2에서, 3은 3에서, 4는 4에서, 0은 10에서 나온다. 그다음 9는 최소의 n이 되려면 19에서 나와야하고, 2는 20에서 나와야한다. 그래서 n이 20이 된다. 숫자열의 인덱스를 나타내 줄 포인터를 설정하고, 현재숫자 i 를 정한다. while문으로 숫자를 증가시켜가면서 숫자의 자릿수가 배열에 있으면 포인터를 증..
https://www.acmicpc.net/problem/2644 문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람..
