본문 바로가기

백준문제풀이

 (53)
[백준 문제풀이] 11488번 : 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 💡 순열을 이용해서 모든 경우의 수를 사용해 계산하고, 해당 계산 값을 리스트에 넣어 거기서 최대/최소 값을 찾아 출력하도록 만들었다. 시간초과날까봐 걱정했던.. pypy로 제출하니까 되긴하는데 뭔가 다른 풀이법 있을듯 중간고사 끝나고 찾아봐야겠다. from itertools import permutations N=int(input()) A=..
[백준 문제풀이] 11725번 : 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 💡 리스트로 트리를 만들고 각각의 부모노드를 DFS 탐색으로 찾아 출력한다. 재귀오류나와서 재귀횟수 증가시켜줌. ✔소스코드 import sys sys.setrecursionlimit(10**9) N=int(sys.stdin.readline()) Tree=[[0] for i in range(N+1)] Parents=[0 for i in range(N+1)] for i in range(N-1): a,b=map(int,sys.stdin.readline().split..
[백준 문제풀이] 2250번 : 트리의 높이와 너비 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 💡중위순회를 통해 앞에서부터 차례대로 탐색 ✔소스코드 N=int(input()) matrix=[[0]*2 for i in range(N+1)] node = [0 for i in range(N + 1)] row = [[] for i in range(N + 1)] #입력받은 수를 matrix에 채우기 for i in range(N): ro,le,ri=map(int,input().sp..
[백준 문제풀이] 1991번 : 트리 순회 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 💡트리를 파이썬으로 처음 생각해봤던 것 같다. C언어 처럼 class해야할까 했는데 그렇게 안해도 트리처럼 보이도록 할 수 있어서 그냥 배열 사용해서 했다. ✔소스코드 N=int(input()) node=[[0]*3 for i in range(26)] for i in range(N): ro,le,ri=map(str,input().split()) root=ord(ro)-65 node[ro..
[백준 문제풀이] 14226번 : 이모티콘 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 💡dfs를 사용해서 클립보드를 탐색하는 문제였다. 화면의 이모티콘 개수와 클립보드에 복사된 이모티콘 개수가 함께 필요하기 때문에 2차원 배열을 사용해주었다. 각 조건에 맞게 if문을 작성하고, for문을 돌면서 결과값을 계산한다. 쉬울 줄 알았는데 생각보다 어려웠던 문제.. ✔소스코드 import sys from collections import deque N=int(sys.stdin.readlin..
[백준 문제풀이] 13913번 : 숨바꼭질4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 💡 숨바꼭질과 구하는 것은 같지만 해당 경로를 찾는 문제이기 때문에 결과를 먼저 얻고 어떤 경로로 왔는지 되돌아가는 문제였다. 하나의 배열을 더 만들어 주고 거기에 몇 번을 지나왔는지를 넣고, path에서 최종 위치를 통해 반대로 탐색하여 출력한다. 생각보다 어려웠던 문제! 반대로 도는게 생각보다 어려웠음 ✔소스코드 import sys from collection..
[백준 문제풀이] 1697번 : 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 💡 아직도 dfs bfs 바로 구현 못해서 개념 다시 확인하고 문제 푸는 중. 특히 bfs보다는 dfs를 더 많이써서 bfs는 어색하다. bfs는 너비우선탐색으로 하나의 노드를 확인하면 해당노드에 연결된 다른 노드를 큐에 넣고 순서대로 꺼내면서 전체를 확인하는 방식이다. 보통 deque를 사용하여 leftpop()을 하고, visited를 활용해 원하는 값을 저장한다. ..
[백준 문제풀이] 2178번 : 미로탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 💡 앞에서 푼 문제들이 전부 DFS라 이번에도 DFS일거라 생각한 내 잘못.. 미로탐색은 대부분 BFS를 사용한다. BFS는 큐를 사용하기 때문에 파이썬 라이브러리에 있는 deque를 사용했다. 위치를 확인하기 위해 dx,dy리스트를 활용하고 각각의 위치에 기본값이 1과 0이기 때문에, 마지막 (N,M)에 바로 얼마나 이동했는지 보여주도록 만들어야 했다. ✔ 소스코드 from collections import deque impo..

티스토리툴바