글 (385) 썸네일형 리스트형 [Python] 1389번 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 22/12/05 플로이드-워셜이나 BFS응용으로 풀 수 있는 문제로, BFS응용풀이에 대한 아이디어는 14217번과 같은 아이디어를 공유하고 있다. 2022.11.29 - [백준 문제 풀이] - [Python] 14217번 그래프 탐색 [Python] 14217번 그래프 탐색 https://www.acmicpc.net/problem/14217 142.. [Python] 1107번 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 22/12/04 조금 생각해야되는 브루트 포스 문제로, 조금만 생각한다면 그리디 알고리즘으로도 풀 수 있을 것 같다. 문제 접근 방식: 이 문제는 두가지 방법으로 풀 수 있다. 어떻게 하면 최소버튼을 누르게 만드는 번호를 찾을 수 있을까?로 접근한다면 그리디적인 접근으로 푸는 것이고, 그냥 생각 없이 채널 번호를 $0$부터 $1,000,000$까지 확인하면서 돌리면 브루트 포스로 .. [Atcoder] ABC 280 - D. Factorial and Multiple https://atcoder.jp/contests/abc280/tasks/abc280_d D - Factorial and Multiple AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 22/12/03 업솔빙을 하며 개인적으로 백준의 8279번이 많이 떠올랐던 문제였다. https://www.acmicpc.net/problem/8279 8279번: Double Factorial For a positive integer n, its factorial is defined as the product of all integers.. [Python] 26006번 K-Queen https://www.acmicpc.net/problem/26006 26006번: K-Queen 재헌이는 생일 선물로 크기가 $N \times N$인 체스판과 백색 킹 하나, 흑색 퀸 $100\ 000$개를 받았다. 킹은 8방향(상하좌우 및 대각선)으로 한 칸씩 이동할 수 있고, 퀸은 같은 행, 열, 대각선에 있는 상 www.acmicpc.net 22/12/01 그룹 연습 문제로 나왔던 문제를 풀었다. 실버 3치고는 개인적으로 어려웠던 편에 속해서, 실버 2로 충분히 올라가도 될 것 같다. 문제 접근 방식: 전형적인 구현 문제이지만, 구현을 잘 못한다면 어렵게 돌아갈 가능성이 존재한다. 먼저, 나는 흰색 킹이 8방향으로 움직일 수 있다는 점에 착안하여, BFS를 구현할 때처럼 dr, dc배열을 선언해주었.. [Python] 15650번 N과 M (2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 22/06/25 옛날에 풀었던 문제를 오늘(22/12/01) 백트래킹으로 다시 풀어보았다. 이전에는 파이썬의 itertools묘듈의 combinations를 사용해서 문제를 해결했지만, 백트래킹을 연습하는 문제로, 백트래킹으로 풀어보기로 했다. 문제 접근 방식: 첫 번째 접근 방법은 N과 M (1)의 코드를 변형한 코드이다. 2022.12.01 - [백준 문제 풀이] - [Python] 1564.. [Python] 15649번 N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 22/11/30 백트래킹의 기초적인 문제로, 단계별로 풀어보기에서 풀어볼 수 있다. 문제 접근 방식: 백트래킹은 주로 재귀+가지치기로 접근이 되어진다. 말 그대로 Backtrack이기 때문에, 쭉 갔다가 다시 돌아오는 작업이 필요하다. 때문에 깊이 있게 들어가는 dfs탐색으로 대부분의 문제가 풀린다. dfs는 스택을 이용할 수도 있고, 재귀를 이용할 수도 있지만, 일반적으로 재귀를 이용한 구현이.. [Python] 11478번 서로 다른 부분 문자열의 개수 https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 22/11/30 단계별로 풀어보기에서 풀은 문제로, 부분 문자열을 찾아내는 방법과 집합 자료구조에 대한 사용법만 알고 있다면 쉽게 풀 수 있는 문제이다. 문제 접근 방식: 모든 부분 문자열을 찾아내고, 이를 부분 문자열 집합에 넣어서 그 집합의 크기를 구하면 끝나는 문제이다. 부분 문자열을 찾아내는 방법은, 문자열 슬라이싱을 이용하여 찾아낼 수 있다. 부분 문자열의 길이가 될 수 있는 $len \ sub \ string$을 $1$부터 $len(S)$까지 for문으로.. [Python] 16928번 뱀과 사다리 게임 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 22/11/30 클래스에 못 푼 문제가 있길래 푼 문제이다. 전형적인 BFS문제이지만, 약간의 변형이 필요한 문제로, 그 상황만 잘 처리를 해준다면 쉽게 AC를 받을 수 있는 문제이다. 문제 접근 방식: 처음에 이 문제를 보고 뱀과 사다리를 타는 것이 의무적으로 타는 것이 아닌, 선택적으로 탈 수 있는 것인 줄 알고 의문의 WA를 많이 받았었다. 예를.. 이전 1 ··· 27 28 29 30 31 32 33 ··· 49 다음