'Python' 태그의 글 목록

[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

[Softeer/소프티어] 나무 섭지 (Lv3 / BFS) - Python

링크https://softeer.ai/practice/7726/history?questionType=ALGORITHM Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 문제 해석지도 상에 나타나는 정보 : 남우, 출구, 유령, 빈공간, 벽 . : 빈칸D : 탈출구G : 귀신# : 벽N : 남우 1초에 한 칸씩 상하좌우로 이동 유령은 벽을 통과할 수 있음 유령은 자기 자리에서 움직이지 않을 수 있음 남우가 유령과 마주치면 잡힘 (출구 자리라도) 입력 첫 번째 줄 : n, m n : 행 m : 열 나머지 줄 : 행렬 정보 출력 탈출 가능하면 Yes 탈출 불가능하면 No 풀이 & 코드 해석BFS로 풀 수 있는 턴제형 미로 문제입니다. 문제에서 명시가 되어 있는 ..

개인 공부/1Day_1Algo 2024. 6. 29. 10:29

[BOJ / 백준] 15971 두 로봇 (G4^ / DFS) - Python

링크https://www.acmicpc.net/problem/15971 문제 해석N개의 방이 존재하고, 통로는 N-1개 존재한다.두 로봇 간에 통신이 필요하고, 통신을 위해서는 로봇 사이에 1개의 통로만 존재해야 한다.통신을 하기 위해 두 로봇이 이동해야 하는 최단 거리는? 입력 첫 번째 줄 : n, a, b n : 방 개수 a : 1번 로봇 위치 b : 2번 로봇 위치 나머지 줄 : s, e, d s : 시작점 e : 끝점 d : 길이 출력 로봇이 서로 통신하기 위해 현재 위치에서 이동해야하는 거리합의 최솟값 풀이 & 코드 해석bfs나 dfs와 같은 그래프 탐색 기법을 사용하면 풀 수 있는 문제입니다. 저는 dfs를 통해 a부터 끝까지 탐사하면서 지나간 통로의 길이를..

개인 공부/1Day_1Algo 2024. 6. 28. 09:52

[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 ~ $\sqrt{N}$까지 N을 나누어 떨어지게 하는 수가 있는지를 확인 - 에라토스테네스의 체 사용하기 각 수는 임의의 값 n * n 제곱하여 나오는 ..

개인 공부/1Day_1Algo 2024. 6. 21. 10:11

[BOJ / 백준] 15996 팩토리얼 나누기 (S3^ / 수학) - Python

링크https://www.acmicpc.net/problem/15996 문제 해석입력첫 번째 줄 : n a n : 팩토리얼 수 a : 나눌 소수 출력n!을 a^k으로 표현할 때 k의 값을 출력 풀이 & 코드 해석완전 탐색 방법으로는 팩토리얼을 계산하여 a로 몇 번 나누어 떨어지는지 계산하면 될 것입니다. 다만 숫자의 최대 범위가 2^31! 이므로 일반적인 방법으로는 절대 시간내로 구할 수 없습니다. # case 16 5 4 3 2 11 1 1 1# case 21010 9 8 7 6 5 4 3 2 1 1 1 1 1 1 1 1 1# case 36 36 5 4 3 2 11 1# case 416 416 15 14 13 12 11 10..

개인 공부/1Day_1Algo 2024. 6. 20. 10:04

[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

[코드트리] 고대 문명 유적 탐사 (G4^ / 시뮬레이션) - Python

링크https://www.codetree.ai/training-field/frequent-problems/problems/ancient-ruin-exploration/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 문제 해석격자 크기 5*5유믈 조각 종류 : 7개 (1~7) 입력 첫 번째 줄 : kk mm kk : 진행할 턴 횟수 mm : 벽면 유물 조각 개수 나머지 줄 : 유물 테이블 마지막 줄 : 벽면 유물 조각 번호 출력 한 줄에 각 턴에서 획득한 유물 총합 출력 이번 턴에 획..

개인 공부/1Day_1Algo 2024. 6. 15. 11:12

[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

AngelPlayer`s Diary