파이썬
[BaekJoon] 백준 1389번 케빈 베이컨의 6단계 법칙
[BaekJoon] 백준 1389번 케빈 베이컨의 6단계 법칙 문제: https://www.acmicpc.net/problem/1389 문제를 보고 친구 관계가 연결되어 있고, 관계를 하나하나 따라 들어가 몇단계인지 찾는다는 부분에서 이거 뭔가 탐색 문제일 것 같은데..! 라는 생각이 들었다. 이어서 최단 경로의 단계를 찾는다는 부분에서 이건 bfs다 라는 생각으로 이어졌다. 어떤 유형의 문제인지 알았으니 이제 입력 받은 데이터를 어떻게 넣어서 bfs를 통해 풀면 될것 같은데, 어떤 자료구조로 넣지? 생각하다가 그래프의 두가지 표현 방식인 1) 인접 리스트(1: 2, 4, 5 / 2: 1, 5 / ...) 2) 인접 행렬(arr[i][j]로 표현)이 떠올랐다. 그중에서 나는 특정 점에 연결된 점들을 찾는..
[BaekJoon] 백준 13458번 시험 감독
[BaekJoon] 백준 13458번 시험 감독 문제: www.acmicpc.net/problem/13458 내코드 - 그냥.. 계산문제 - 시험장에 응시자가 없는 경우를 간과해서 처음에 틀렸었다. import math N = int(input()) member = list(map(int, input().split())) B, C = map(int, input().split()) def main(): global N, member, B, C result = 0 for i in range(N): if member[i] > 0: member[i] -= B result += 1 if member[i] > 0: result += math.ceil(member[i] / C) print(result) main() 참고
[BaekJoon] 백준 3190번 뱀
[BaekJoon] 백준 3190번 뱀 문제: www.acmicpc.net/problem/3190 내코드 - 그대로 구현하기만 하면 되는 간단한 문제였다. - 처음에는 내용 이해를 하고 어떻게 구현해야 할지 막막했는데 하나씩 짜다보면 풀리는 문제였다. - 뱀의 몸이 있는 위치를 deque에 넣어주고 빼줘서 뱀이 이동하는 것을 나타냈다. - 포인트는 문제에 적혀있는 이 세문장이라고 생각한다. 이 순서대로 코드를 작성하였다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. - 또 까다로웠던 부분은 왼쪽, ..
[BaekJoon] 백준 12100번 2048 (Easy)
[BaekJoon] 백준 12100번 2048 (Easy) 문제: www.acmicpc.net/problem/12100 내코드 - dfs와 시뮬레이션을 섞어놓은 문제 - dfs로 상하좌우 각각의 경우에 대해서 이동시키는 것을 각각 5번씩 반복했다. - 이동 시킬때 상하우는 모두 좌로 모양을 맞춰주기 위해 list의 모양을 바꿔주었다. - 모양을 바꿔준 후 0을 제외한 값들만 남기고 붙어있는 두 숫자가 같은 경우에 더해주었다. (ex) 2 2 4 1 1 -> 4 0 4 2 0 (이렇게 해주면 이미 한번 더해진 블럭의 경우 다시 더해지지 않는다!) - 이후에 다시 0을 제외해준 뒤, 배열의 크기 n 에 맞게 뒤에 0을 다 붙여주었다. - 여기까지 하고 다시 처음부터 상하좌우에 대한 이동을 반복한다. - 5번..
[BaekJoon] 백준 13460번 구슬 탈출 2
[BaekJoon] 백준 13460번 구슬 탈출 2 문제: www.acmicpc.net/problem/13460 내코드 - bfs 문제 - 지금까지 풀었던 bfs 문제들과 비슷하지만 구슬 두개를 움직여야 한다는 점에서 생각이 필요했다. - 마지막에 계속 막히던 부분(백준 68%.. 정도에서 틀림)이 있었는데 횟수의 문제였다. if point[2] > 10을 if point[2] > 9 로 바꿔주니까 통과함 from collections import deque arr = [] dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] n, m = map(int, input().split()) # 지도 정보 저장 def init(): for i in range(n): tmp = list(str(in..
[BaekJoon] 백준 1759번 암호 만들기
[BaekJoon] 백준 1759번 암호 만들기 문제: www.acmicpc.net/problem/1759 내코드 이전 백트래킹 문제들과 푸는 방식은 비슷하지만 포인트는 크게 두가지 였다. 자음과 모음의 최소 포함 개수가 정해져 있었다는 것 사전 순으로 출력해야 한다는 것 consonant_n, vowel_n 변수를 따로 선언해줘서 자음 모음 개수를 저장해주고 마지막에 개수를 확인해 준뒤 출력해줬다. 또한 out변수에 append하기 전에 out 리스트의 마지막 문자보다 현재 입력하려고 하는 문자가 사전순으로 뒤에 있는지 확인해 준뒤 입력해줬다. 문제를 풀면서 맞게 풀었다고 생각했는데 틀렸다고 나왔다. 처음 입력받은 문자열 리스트를 sorted()로 정렬해주니 해결되었다. # BaekJoon1759.py..
[BaekJoon] 백준 15650번 N과 M (2)
[BaekJoon] 백준 15650번 N과 M (2) 문제: www.acmicpc.net/problem/15650 내코드 15649번 N과 M (1)과 거의 동일하지만 오름차순으로 출력해야 한다는 것이 달랐다. 즉, (1)번 문제는 (1 2), (2 1)이 다른 배열로 처리되었지만 (2)번 문제에서는 둘중 오름차순인 (1 2)만출력해야 된다는 것 [1, 3]과 같은 리스트가 있을 때, 다음 숫자를 정하는 과정에서 새로운 수가 3보다 작으면 pass하는 방식으로 처리해줬다. # BaekJoon 15649.py N과 M(2) # 백트래킹 문제: 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 n, m = map(int, input().split()) vis..