Loading [MathJax]/jax/output/CommonHTML/jax.js

AngelPlayer`s Diary

[BOJ / 백준] 14267 회사 문화 1 (G4^ / 트리) - Python

링크https://www.acmicpc.net/problem/14267    문제 해석상사가 직속 부하를 칭찬하면 부하가 부하의 직속 부하를 연쇄적으로 칭찬 칭찬한 정도만큼 부하들이 똑같이 칭찬 받음   입력첫 번째 줄 : n m   n : 직원 수   m : 칭찬의 횟수 두 번째 줄 : n명의 직속 상사 번호 m개의 줄 : i w   칭찬을 받은 직원 번호   칭찬의 수치  출력모든 직원이 칭찬 받은 정도를 출력    풀이 & 코드 해석직장의 상하관계를 생각해보면 그래프에 사이클이 없다는 것을 쉽게 생각할 수 있습니다.(A가 B의 상사이고, B가 C의 상사이고, C가 A의 상사인 경우는 있을 수 없다.) 따라서 이 문제는 트리 문제라고 생각해볼 수 있습니다.  문제를 보면 A가 칭찬을 받으면 직속 부하..
개인 공부/1Day_1Algo 2024. 7. 16. 10:10

[BOJ / 백준] 3584 가장 가까운 공통 조상 (G4 / 트리) - Python

링크https://www.acmicpc.net/problem/3584    문제 해석테스트 케이스 별로 공통 조상 노드를 구하라 공통 조상 노드란 a, b가 서로 만나는 조상이면서 가장 가까운 조상을 의미한다.   입력첫 번째 줄 : t   t : 테스트 케이스 개수 첫 번째 줄 : n   n : 트리의 노드 수 n - 1개의 줄 : a, b   a : 부모   b : 자식 마지막 줄 : n1, n2   n1, n2 : 공통 조상을 찾을 두 노드  출력각 테스트 케이스의 공통 조상 노드 출력    풀이 & 코드 해석그래프 문제는 누가 누구의 부모이고 자식인지 등 그래프의 형태를 파악하기 위해 연결을 할 필요가 있습니다. 다만 해당 문제는 입력 시 a 노드가 b 노드의 부모이다 라는 조건을 제시해주고 있으..
개인 공부/1Day_1Algo 2024. 7. 15. 11:06

[BOJ / 백준] 17298 오큰수 (G4 / 스택) - Python

링크https://www.acmicpc.net/problem/17298    문제 해석n개의 수가 주어졌을 때 i번째 수의 오큰수는 i보다 오른쪽에 있으면서 가장 왼쪽에 있는 i보다 큰 수오른쪽에 i보다 큰 수가 없다면 -1각 자리수의 오큰수를 구하라  입력첫 번째 줄 : n  n : 숫자 개수두 번째 줄 : n개의 숫자  출력각 자리의 오큰수 출력    풀이 & 코드 해석나보다 큰 숫자가 무엇인지 판단하는 가장 원초적인 방법은 완전탐색일 것입니다. 그렇다면 시간 복잡도는 O(N^2)이 될 것인데 N의 범위가 1,000,000이므로 시간 초과가 날 수밖에 없습니다.   문제를 풀기 위해서 스택을 사용하는 방법을 생각해 보았는데요. 풀이 방식은 아래와 같습니다.1. 입력된 배열을 역순으로 탐색한다.2. 스..
개인 공부/1Day_1Algo 2024. 7. 12. 09:47

[BOJ / 백준] 17404 RGB거리 2 (G4 / DP) - Python

링크https://www.acmicpc.net/problem/17404    문제 해석집이 총 n개가 있음 집을 빨강, 초록, 파랑 중 하나로 칠해야 함 매번 칠할 떄 가격이 서로 다름 색상은 이전 집과 항상 달라야함첫 번째 집과, n번째 집의 색상은 서로 달라야 함  입력첫 번째 줄 : n  n : 집의 개수 n개의 줄 : n번째 집을 칠할 때 드는 색상별 비용    출력모든 집을 칠하는 최소 값 구하기    풀이 & 코드 해석어제 풀었던 RGB거리와 입력과 출력 양식이 정확히 동일한 문제입니다.https://angelplayer.tistory.com/581   다만 위 문제와 차이점은 조건으로 첫 번째 집과, 마지막 집의 색상이 서로 달라야 한다는 점입니다. 이 문제를 해결하기 위해서 dp의 저장 조..
개인 공부/1Day_1Algo 2024. 7. 8. 11:39

[BOJ / 백준] 1149 RGB거리 (S1^ / DP) - Python

링크https://www.acmicpc.net/problem/1149    문제 해석집이 총 n개가 있음집을 빨강, 초록, 파랑 중 하나로 칠해야 함 매번 칠할 떄 가격이 서로 다름색상은 이전 집과 항상 달라야함  입력첫 번째 줄 : n  n : 집의 개수n개의 줄 : n번째 집을 칠할 때 드는 색상별 비용   출력모든 집을 칠하는 최소 값 구하기    풀이 & 코드 해석이 문제를 완탐으로 푼다면 매 집에 대해 3가지 경우의 수를 가지고, n이 최대 1000까지 있으므로, O(3^n)이 될 것입니다. 따라서 제한 시간 내에 풀기 위해서는 DP를 사용해야 합니다.    코드import syssys.setrecursionlimit(10**8)def recursive(idx, bef): global n ..
개인 공부/1Day_1Algo 2024. 7. 8. 11:34

[BOJ / 백준] 1726 로봇 (G3 / BFS) - Python

링크https://www.acmicpc.net/problem/1726    문제 해석로봇은 방향과 위치를 가지고 있고, 매 턴 [ 좌로 회전, 우로 회전, 한 칸 앞으로 이동, 두 칸 앞으로 이동, 세 칸 앞으로 이동 ]이 가능하다. 이 때 원하는 도착지점에 원하는 회전상태로 이동하는 최단 시간을 구하라.  입력첫 번째 줄 : m, n   m : 직사각형의 세로 길이   n : 직사각형의 가로 길이 m개의 줄 : 지도 정보   0 : 갈 수 있는 길   1 : 갈 수 없는 길 다음 줄 : sx, sy, sd    로봇의 출발 지점 위치, 바라보는 방향   동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4 마지막 줄 : ex, ey, ed   도착점의 위치, 바라봐야할 방향 출력 원하는 방향으로 이동시키는데..
개인 공부/1Day_1Algo 2024. 7. 6. 12:31

[BOJ / 백준] 11899 괄호 끼워넣기 (S3^ / Stack) - Python

링크https://www.acmicpc.net/problem/11899    문제 해석괄호열이 주어졌을 때, 왼쪽과 오른쪽에 몇 개의 괄호를 추가함으로써 완벽한 괄호열이 되는지 구하시오.   입력 첫 번째 줄 : s   s : 괄호열 출력 올바른 괄호열로 만들기 위해 앞과 뒤에 붙여야할 괄호의 최소 개수 구하기     풀이 & 코드 해석코드 구현은 생각보다 단순합니다. 여는 괄호( '(' )를 만나면 stack에 push,닫는 괄호( ')' )를 만나면 stack에 값 하나를 pop 하면 됩니다.   괄호열이 "(" 인 경우위 괄호열의 0번 인덱스 괄호는 '('입니다. '('는 추후 ')'의 여부에 따라서 완벽환 괄호가 될 수 있습니다. 따라서 stack에 해당 값을 저장해 놓습니다. 괄호열의 괄호가 한..
개인 공부/1Day_1Algo 2024. 7. 5. 10:10

[BOJ / 백준] 1389 케빈 베이컨의 6단계 법칙 (S1 / BFS) - Python

링크https://www.acmicpc.net/problem/1389    문제 해석A와 B가 소개를 통해서 알 수 있는 거리를 베이컨 거리라고 한다. A와 B가 직접 아는 사이라면 거리가 1이고,A와 C가 직접 아는 사이이고, B와 C가 직접 아는 사이라면 A와 C는 거리가 2이다. n명의 사람이 주어졌을 때 모든 사람과 가장 베이컨 거리의 합이 짧은 사람을 구하라.   입력첫 번째 줄 : n, m   n : 유저수   m : 친구 관계 수  출력베이컨 거리가 가장 짧은 사람의 번호 단 베이컨 거리가 동일한 사람이 있는 경우 번호가 가장 작은 사람이 정답    풀이 & 코드 해석주어지는 사람들간의 관계(간선)은 가중치 없이 모두 균등합니다. 균등한 가중치를 가지는 그래프에서 최단 거리를 찾을 때는 BF..
개인 공부/1Day_1Algo 2024. 7. 4. 10:20

[BOJ / 백준] 1697 숨바꼭질 (S1 / BFS) - Python

링크https://www.acmicpc.net/problem/1697    문제 해석수빈이는 1초에 -1칸, 1칸, 현재의 위치의 두배 위치로 이동이 가능함 수빈이가 동생을 찾는데 걸리는 최소 시간은? 입력 첫 번째 줄 : n k   n : 수빈의 위치   k : 동생의 위치 출력 수빈이가 동생을 찾는 가장 빠른 시간    풀이 & 코드 해석수빈이가 n에서 조건대로 이동하여 k로 갈 수 있는 최단 거리를 구하는 문제입니다. 문제에서 수빈이가 이동할 수 있는 경우는 [ 앞으로 한 칸, 뒤로 한 칸, 현재 위치 2배 ]로 총 3가지 입니다.  BFS는 알고리즘 특성 상 그래프에서 특정 위치에 가장 먼저 도착하는 시간을 알 수 있습니다. 따라서 현재 이동 가능한 모든 경우의 수를 Queue에 삽입하고 연산하는..
개인 공부/1Day_1Algo 2024. 7. 3. 11:09

[BOJ / 백준] 2668 숫자고르기 (G5^ / DFS) - Python

링크https://www.acmicpc.net/problem/2668    문제 해석세로로 2칸, 가로로 n개의 칸으로 이루어진 표가 주어짐첫 번째 행에서 뽑은 숫자의 집합과, 첫 번째 행과 같은 열에서 뽑은 두 번째 행의 숫자의 집합이 동일해야 함위를 만족하며 최대로 구할 수 있는 숫자 개수는?   입력첫 번째 줄 : n   n : 숫자의 개수 n개의 줄 : 2번째 줄에 들어갈 숫자  출력  뽑힌 정수의 개수를 출력 뽑힌 정수들을 오름차순으로 출력     풀이 & 코드 해석문제의 예제를 그려보면 위와 같습니다. 정답은 1, 3, 5인데 결국 사이클을 가지는 경우, 즉 나 자신으로 돌아올 방법이 있는 경우 정답이 된다는 것을 알 수 있습니다. 사이클의 종류는 크게 1과 3이 이루는 1대1 사이클, 5와 ..
개인 공부/1Day_1Algo 2024. 7. 2. 10:41

[BOJ / 백준] 16562 친구비 (G4 / DFS) - Python

링크https://www.acmicpc.net/problem/16562    문제 해석돈을 주면 친구가 되어 준다. 친구의 친구는 친구다. 가진 돈의 한도 내에서 가장 적은 비용으로 모두와 친구가 될 수 있는 방법을 구하라. 입력 첫 번째 줄 : n m k   n : 학생 인원 수   m : 친구 관계 수   k : 가지고 있는 돈두 번째 줄 : n명의 학생이 각각 친구비로 원하는 돈m개의 줄 : f1 f2   f1 : 친구 1   f2 : 친구 2   -> 1, 2는 서로 친구사이 출력 모든 학생을 친구로 만들 수 있으면 최소 비용 출력 친구를 다 사귈 수 없으면 "Oh no" 출력  특이사항 친구 숫자는 1부터 시작함    풀이 & 코드 해석연결요소로 이어진 사람들은 한 명만 매수해도 모두 친구가 됩..
개인 공부/1Day_1Algo 2024. 6. 30. 10:38

[BOJ / 백준] 2644 촌수계산 (S2 / DFS) - Python

링크https://www.acmicpc.net/problem/2644    문제 해석촌수계산 부모-자식 관계는 1촌 더 멀어지는 경우 촌수가 늘어남 입력 첫 번째 줄 : n   n : 사람 수 두 번째 줄 : a, b   촌수를 구해야 하는 사람 세 번째 줄 : m   m : 부모 자식 관계 수 나머지 줄 : m개의 부모 자식 관계  출력 두 사람의 촌수를 출력촌수를 나타낼 수 없으면 -1    풀이 & 코드 해석어제 풀었던 바이러스와 다르게 촌수계산은 a라는 노드와 b라는 노드가 얼마나 떨어져 있는지를 계산해야 합니다. 따라서 그래프를 순회하면서 시작 정점으로부터 얼만큼 떨어져 있는지를 매개변수로 추가하여 문제를 해결하였습니다.    코드def dfs(num, dis): global b, ans ..
개인 공부/1Day_1Algo 2024. 6. 27. 09:39

[BOJ / 백준] 2606 바이러스 (S3 / DFS) - Python

링크https://www.acmicpc.net/problem/2606    문제 해석컴퓨터 바이러스는 동일한 네트워크에 연결된 다른 PC로 감염된다. 1번 컴퓨터가 바이러스에 감염되었을 때 1번 컴퓨터로 인해서 감염된 컴퓨터의 개수를 구하라. 입력 첫 번째 줄 : n   n : 컴퓨터의 수 두 번째 줄 : m   m : 네트워크 상에 연결된 컴퓨터 쌍의 수 나머지 줄 : m개의 쌍 정보 출력 1번 컴퓨터로 인해 감염된 PC 수    풀이 & 코드 해석그래프에서 연결된 노드의 개수를 찾는 문제입니다. 인접 리스트를 통해서 구현을 시도하였으며, 새롭게 노드를 방문할 때마다 개수를 count하면서 정답을 구하였습니다.   코드def dfs(num): global ans v[num] = True ..
개인 공부/1Day_1Algo 2024. 6. 26. 12:35

[BOJ / 백준] 1407 2로 몇 번 나누어질까 (G4^ / 수학) - Python

링크https://www.acmicpc.net/problem/1407    문제 해석a, b 사이의 숫자 중 2의 거듭제곱으로 나누어 떨어지는 수는 2의 거듭제곱을, 그렇지 않으면 1을 더한 결과를 출력하기  입력첫 번째 줄 : a, b  a : 숫자의 시작 범위  b : 숫자의 마지막 범위    풀이 & 코드 해석다른 문제를 푼 사람들의 코드들은 굉장히 효율적이고 간결한데, 저는 수학을 잘 못해서 무식하게 풀었습니다. 저는 단순하게 1~b 사이에 2의 제곱 값을 구하고 1~(a-1)사이에 2의 제곱 값을 구해서 뺀 결과와,a~b 사이의 1의 개수를 더한 값을 결과로 출력하는 방식을 생각했습니다.   https://angelplayer.tistory.com/563 [BOJ / 백준] 15996 팩토리얼 ..
개인 공부/1Day_1Algo 2024. 6. 24. 11:20

[BOJ / 백준] 2725 보이는 점의 개수 (S2^ / 수학) - Python

링크https://www.acmicpc.net/problem/2725    문제 해석(0, 0)에서 볼 수 있는 점의 개수를 출력하기   입력첫 번째 줄 : 테스트 케이스나머지 줄 : n  n : x, y의 범위 제한  출력n까지 범위 내 보이는 점의 개수    풀이 & 코드 해석(4, 2)는 (2, 1)에 의해서 가려지기 때문에 볼 수 없습니다. 이를 다르게 생각하면 (a, b)에서 a, b를 나누어 떨어뜨리는 약수가 존재하는 경우,즉 a, b의 최대 공약수가 1이 아닌 경우에는 해당 위치가 볼 수 없는 자리라고 볼 수 있습니다. (※ 두 수의 최대공약수로 1만 가질 수 있는 경우를 서로소라고 합니다.)   한편 n이 한 칸씩 늘어날 때 마다 볼 수 있는 점의 개수는 짝수 개로 늘어납니다. (1을 제외..
개인 공부/1Day_1Algo 2024. 6. 23. 11:01

[BOJ / 백준] 2247 실질적 약수 (G5 / 수학) - Python

링크https://www.acmicpc.net/problem/2247    문제 해석SOD(n) : 1과 n을 제외한 모든 약수CSOD(n) : 1부터 n까지 모든 SOD(i)의 합   입력 n : 찾고자 하는 숫자  출력CSOD(n)    풀이 & 코드 해석문제 내용은 약수를 모두 찾아서 더해주는 심플하고 간단합니다. 단 n의 범위가 200,000,000 이기 때문에 매 숫자에 대한 약수를 구하는 것은 시간초과가 발생할 것입니다.   따라서 한 번에 하나의 값만 보는 것이 아니라 팩토리얼 나누기에서 했던 방식처럼 for문을 통해 반복을 진행하면서,  현재 반복 중인 i라는 숫자로 나누어 떨어지는(약수로 가지는) 숫자가 몇 개인지를 세는 방식으로 구현하였습니다.  ※ 팩토리얼 나누기 해석https://a..
개인 공부/1Day_1Algo 2024. 6. 22. 09:25

[BOJ / 백준] 6219 소수의 자격 (S3 / 수학) - Python

링크https://www.acmicpc.net/problem/6219    문제 해석a에서 b사이의 소수 중 d를 포함하는 수가 몇 개인지 구하라  입력첫 번째 줄 : a b d  a : 시작 값  b : 마지막 값  d : 포함할 숫자  출력d를 포함하는 숫자의 개수   풀이 & 코드 해석소수를 구하는 가장 빠른 방법은 에라토스테네스의 체입니다. 에라토스테네스의 체를 구현하는 방법은 아래 링크에 설명되어 있습니다.https://angelplayer.tistory.com/391 [알고리즘] 소수 (Prime)소수 구하기 - 숫자 N의 소수 판정 방법 1 ~ √N까지 N을 나누어 떨어지게 하는 수가 있는지를 확인 - 에라토스테네스의 체 사용하기 각 수는 임의의 값 n * n 제곱하여 나오는 ..
개인 공부/1Day_1Algo 2024. 6. 21. 10:11

[BOJ / 백준] 10815 숫자 카드 (S5^ / 이분탐색) - Python

링크https://www.acmicpc.net/problem/10815    문제 해석입력첫 번째 줄 : n   n : 숫자 카드 개수  두 번째 줄   가지고 있는 숫자카드 리스트 세 번째 줄 : m   확인할 숫자 개수 : m 네 번째 줄   해당 숫자 카들 가지고 있는지 확인할 리스트  출력해당하는 숫자 카드를 가지고 있으면 1 아니면 0으로 출력    풀이 & 코드 해석숫자 카드가 존재하는지 완탐을 진행하면 n * m 을 진행해야하고 결국 시간초과가 발생합니다. 이분 탐색을 활용하면 시간초과를 해결할 수 있습니다. 이분 탐색은 먼저 탐색할 배열이 정렬이 되어 있어야 하고, 이를 up-down을 통해서 탐색하는 방식으로 찾고자 하는 방법을 찾을 수 있습니다.    코드n = int(input())a..
개인 공부/1Day_1Algo 2024. 6. 19. 10:07

[BOJ / 백준] 2805 나무 자르기 (S2^ / 이분탐색) - Python

링크https://www.acmicpc.net/problem/2805    문제 해석입력첫 번째 줄 : n m   n : 나무의 수   m : 가져갈 나무의 길이 두 번째 줄 : 나무 리스트  출력최소한의 나무를 자를 수 있는 절단기의 높이   풀이 & 코드 해석완전 탐색으로 풀기 위해서는 모든 높이에서 탐색을 해야 하므로 시간초과가 발생합니다. 따라서 이분 탐색을 통해 적절한 높이를 찾는 것이 중요합니다.  20 | -> 1m19 | -> 2m18 | -> 3m17 | | -> 5m 16 | | -> 7m15 | | | -> 10m14 | | | ->..
개인 공부/1Day_1Algo 2024. 6. 18. 12:57

[BOJ / 백준] 20055 컨베이어 벨트 위의 로봇 (G5 / 시뮬레이션) - Python

링크https://www.acmicpc.net/problem/20055    문제 해석입력 첫 번째 줄 : n k   n : 컨베이어 벨트 길이   k : 내구도가 0인 위치의 한계값 두 번째 줄 : 벨트 내구도 출력 : 종료 시 단계, 1단계부터 시작함  문제에서 참고할 설명1번칸 : 컨베이어 벨트에 올리는 위치 N번칸 : 컨베이어 벨트에서 내리는 위치 내구도 깎이는 기준   1) 로봇을 올리는 위치에 올림   2) 로봇이 칸 이동을 진행함  시뮬레이션 순서1) 벨트 한 칸 회전 (로봇이 같이 움직임) 2) 올라탄 로봇 순서대로 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동    이동하려면 해당 칸에 로봇이 없으며, 내구도가 1이상이어야 함 3) 올리는 위치의 칸의 내구도가 0이 아니면 올리는..
개인 공부/1Day_1Algo 2024. 6. 16. 14:07

[BOJ / 백준] 11559 Puyo Pyuo (G4 / 시뮬레이션, BFS) - Python

링크https://www.acmicpc.net/problem/11559    문제 해석입력 뿌요뿌요 판의 정보 (12 * 6)   R G B P Y : 색상   . : 빈 공간 출력 연쇄 수 / 없으면 0  초기 값에서는 아래 빈칸 없음 연쇄 == 턴 한 턴에 여러 색이 터지더라도 1연쇄 1. 뿌요가 존재하는 위치 찾기 2. bfs 3. 끌어내리기  풀이 & 코드 해석BFS를 곁들인 시뮬레이션 문제입니다. 한 턴에 여러 개의 뿌요가 터지더라도 이는 1연쇄로 한다는 점을 잘 숙지하시면 크게 어려운 점이 없습니다.    코드from collections import dequedx = [-1, 0, 1, 0]dy = [0, 1, 0, -1]def print_arr(arrs): for i in range(..
개인 공부/1Day_1Algo 2024. 6. 14. 09:37

[BOJ / 백준] 1913 달팽이 (S3^ / 구현) - Python

링크https://www.acmicpc.net/problem/1913    문제 해석입력첫 번째 줄 : n   n : 행, 열의 길이       n^2 == 첫 번째 수 두 번째 줄 : m   m : 좌표를 찾을 값 출력 1) 달팽이 결과 출력 2) m의 좌표 출력 / (1, 1)부터 시작함    풀이 & 코드 해석삼성 코딩테스트 등에서 종종 사용되는 나선형으로 숫자 출력하는 문제입니다. 다음 숫자를 작성할 경로를 나타내는 dx dy를 따라서 쭉 숫자를 작성하다가, 범위를 벗어나거나 이미 작성된 위치가 있는 경우 방향을 바꿔서 다시 숫자를 채워가는 방식을 적용하면 쉽게 풀 수 있습니다. 하 우 상 좌 순으로 달팽이가 돌기 때문에 dx dy를 맞춰서 만들었습니다.    코드# 하 우 상 좌dx = [1, ..
카테고리 없음 2024. 6. 13. 07:24

[BOJ / 백준] 20056 마법사 상어와 파이어볼 (G4^ / 시뮬레이션) - Python

링크https://www.acmicpc.net/problem/20056    문제 해석격자 n * n 파이어볼 개수 m개 파이오볼은 위치 질량 방향 속력을 가짐 행열은 1,1부터 시작함 1번열과 n번열은 연결되어 있음 입력 - 첫 번째 줄 : nn, ll, kk   nn : 격자 크기   ll : 초기 파이어볼 개수   kk : 이동 명령 횟수 - 나머지 줄 : rr cc mm ss dd   rr : 행   cc : 열   mm : 질량   ss : 속력   dd : 방향  출력 남아있는 파이어볼 질량의 합    풀이 & 코드 해석시뮬레이션이므로 문제에 주어진 조건을 그대로 구현하면 됩니다.    코드dx = [-1, -1, 0, 1, 1, 1, 0, -1]dy = [0, 1, 1, 1, 0, -1, -..
개인 공부/1Day_1Algo 2024. 6. 12. 11:29

[Baekjoon] 백준 17945 통학의 신 (B3 / 완전탐색) - Python

링크 https://www.acmicpc.net/problem/17945 17945번: 통학의 신 x2 + 2Ax + B = 0 의 두 계수 A, B가 주어진다. A, B는 정수이며, 이 방정식의 근은 항상 정수이다. (-1000 ≤ A, B ≤ 1000) www.acmicpc.net 문제 해석 입력 첫 번째 줄 : a, b a, b : x^2 + 2ax + b = 0의 계수 출력 : 방정식의 근 찾기 (중근인 경우 1개) 풀이 & 코드 해석 완전탐색 풀이 방법 1) 모든 경우의 수 확인하기 근의 범위가 -1000 ~ 1000 이므로 최대 2001개이다. 따라서 -1000부터 1000까지 하나씩 식에 대입하여 근인지 판별하는 완전탐색 방법으로 풀어도 시간 내에 풀 수 있다. 코드 a, b = list(m..
개인 공부/코딩 테스트 2024. 4. 24. 08:35

[Baekjoon] 백준 1261 알고스팟 (G5^ / 다익스트라) - Python

링크 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제 해석 미로의 크기는 N * M 미로는 빈 방(0) 또는 벽(1)으로 이루어져 있음 벽은 부술 수 있으며, 부수지 않으면 해당 칸으로 이동할 수 없음 이동은 상하좌우로 이동 가능 (1,1)에서 (N, M)으로 이동하기 위해서 최소 몇 개의 벽을 부셔야 하는가? 풀이 & 코드 해석 문제를 해결하기 위해서 먼저 DFS 방식으로 풀어보았습니다. def dfs(x, y): ..
개인 공부/코딩 테스트^ 2024. 3. 22. 18:14

[Baekjoon] 백준 1753 최단경로 (G4^ / 다익스트라) - Python

링크 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 해석 정점의 개수와 간선이 개수가 주어짐 각 간선은 가중치를 가짐 시작 정점이 주어졌을 때, 시작 정점으로부터 다른 정점으로 가는 최단거리를 각각 출력하기 풀이 & 코드 해석 다익스트라의 기본이 되는 문제입니다. 다익스트라 알고리즘에 맞춰서 풀면 쉽게 해결됩니다. 코드 import heapq v, e = map(int, input().split())..
개인 공부/코딩 테스트^ 2024. 3. 20. 08:47

[Baekjoon] 백준 5582 공통 부분 문자열 (G5^ / DP) - Java

링크 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제 해석 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾으시오. 입력 첫 번째 줄 : 문자열 N 두 번째 줄 : 문자열 M 출력 부분 문자열의 최대 길이 풀이 & 코드 해석 공통 부분 문자열은 2차원 배열로 구성된 dp를 통해서 쉽게 풀 수 있는 문제입니다. 자세한 풀이 방법은 별도로 알고리즘을 정리한 포스트를 참고해주세요. https://an..
개인 공부/코딩 테스트^ 2023. 10. 31. 09:54

[Baekjoon] 백준 N과 M 시리즈 1~4 (S3 / 순조부) - JS

링크 https://www.acmicpc.net/workbook/view/2052 문제집: N과 M (시리즈) www.acmicpc.net 공통 설명 N과 M 자연수 N과 M이 주어졌을 때 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 구하시오. 입력 첫 번째 줄 : N M 출력 조건을 만족하는 수열을 출력 중복되는 수열을 여러 번 출력하면 안됨 수열은 공백으로 구분하여 출력 (1) 설명 1부터 N까지 자연수 중 중복없이 M개를 고른 수열 해석 (1, 3) (3, 1)이 가능하므로, 순열 코드 const fs = require('fs'); const inputData = fs.readFileSync('/dev/stdin').toString().split(' '); // const inp..
개인 공부/1Day_1Algo 2023. 10. 23. 08:23

[Baekjoon] 백준 2573 빙산 (G4^ / BFS) - Java

링크 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 해석 빙산을 2차원 배열에 표시 빙산의 부분별 높이 정보는 배열 각 칸에 저장 바다에 해당하는 칸은 0이 저장 바닷물에 많이 접해있으면 빨리 줄어듬 4방향 중 바다에 접한 면만큼 줄어듦 입력 첫 번째 줄 : N M 행 : N 열 : M 나머지 줄 : 행만큼 반복적으로 입력 출력 한 덩어리의 빙산이 주어질 때 빙산이 두 덩어리 이상으로 분리되는 최초 시간 다 녹을 때까지 두 덩어리 ..
개인 공부/코딩 테스트^ 2023. 10. 22. 08:36

[Baekjoon] 백준 2304 창고 다각형 (S2 / 구현) - Java

링크 https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 문제 해석 막대기둥 N개 막대기둥을 잇는 지붕을 만들어야 함 지붕은 물이 고이지 않게 오목한 부분이 없어야 함 가장자리는 땅에 닿아야 함 이때 만들어지는 창고의 최소 크기를 구하라 - 입력 첫 번째 줄 : N N : 기둥의 개수 나머지 줄 : L H L : 기둥 위치 H : 높이 - 출력 창고의 최소 크기 풀이 & 코드 해석 스택으로 푸는 문제라고도 하는데 굳이 스택을 사용하..
개인 공부/코딩 테스트 2023. 9. 11. 21:21
◀ 1 2 3 ▶

티스토리툴바