![]()
https://www.acmicpc.net/problem/1520 문제 분석 난이도 골드 3 분류 그래프 탐색, 다이나믹 프로그래밍 + (DFS or 우선순위 큐) 문제 문제 풀이 풀이 맨 마지막 위치에서 인접한 부분의 자신보다 큰 수를 우선순위 큐에 넣어준다. 그러면 항상 앞에는 작은 수가 들어가고 그 순서대로 탐색하게 된다. 주변의 인접한 숫자들 중 자신보다 큰 수가 있다면 현재의 방문횟수를 더해주고, 방문한 적이 없는 곳이라면 우선순위 큐에 넣어준다. M*N은 최대 250000(500*500) 이고, push pop의 시간복잡도는 logN이므로 시간은 넉넉하다. 소스코드 from sys import stdin from heapq import heappop,heappush input=stdin.rea..
![]()
bfs와 dfs를 모두 함수로 구현해서 각각 한번씩 실행을 해줘야 한다. 각각 한 번씩만 하면 되므로 이를 기록할 리스트를 1개씩 만들어두고 입력받은 점에 대해서는 2차원 배열에 저장해두자 bfs와 dfs를 실행하면서 각각의 경우에 2차원 배열에 저장된 경로들을 참고하여 출력할 수 있는 경우들을 출력하고 출력 형식은 한 줄로 붙어있어야 하므로 그때그때 출력하고 end=" "를 통해서 한 줄로 출력하자. import sys from collections import deque def main(): N, M, V = map(int, sys.stdin.readline().split()) graph = [[False] * (N+1) for _ in range(N+1)] for _ in range(M): a, b..
![]()
4963번: 섬의 개수 (acmicpc.net) 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 소스코드 설명 sys.setrecursionlimit()를 이용해 재귀호출의 최대 깊이 증가 하나의 섬을 둘러싸고 있는 최대 8개의 섬이 존재하며 각 섬으로 이동 가능하므로 현재 섬의 좌표가 (0,0)일 때, 각 섬의 x좌표와 y좌표를 dx, dy 리스트로 생성 w, h을 입력받고 둘다 0이라면 while문 종료 현재 섬과 바다의 위치를 보여주는 2차 배열 a 생성 a와 똑같은 위치의 칸에 방문 여부를 알려주..
https://www.acmicpc.net/problem/1012 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추..
![]()
BFS와 최단 경로 BFS는 최단거리와 관련있다. 왤까? BFS 알고리즘과 구현에 대해 이해하면, 이에 대한 해답을 얻을 수 있다. BFS 알고리즘을 이해하기 위해서는 먼저 bfs 알고리즘이 node를 방문하는 순서를 살펴봐야 한다. bfs는 위 그림과 같이 인접한 노드를 먼저 방문한다. 그리고 방문한 순서대로 노드들을 Q에 넣고 시작점에서 인접한 Node를 모두 방문하면, Q 맨앞의 노드를 popleft한다. 이후 popleft된 노드들의 인접한 노드를 탐색하여 이 노드들도 똑같이 Q에 저장한다. 결론적으로 queue는 선입선출 방식으로 동작되기 때문에 방문 노드들이 순서대로 queue에 저장된다. 예시를 보자. 시작점 A에서 F까지의 최단경로를 알아본다고 했을 때 bfs를 진행하면서 F를 처음 방문하..
![]()
https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 알고리즘 좋은 단어의 조건은 1. 같은 단어끼리 짝을 지을 때 2. 선끼리 교차가 불가능하다는 것이다. 그림을 통해 이해하면 쉽다. 만약 문자 A가 나오면 스택 맨위값(top : stack[-1])이 A일 경우, 같은 문자이니까 스택에서 문자 A를 pop한다. B인 경우도 마찬가지로 작업을 진행한다. 이렇게 넣고 빼는 과정을 반복하다보면, 교차 없이 짝이 다 맞는 단어는 스택에 있는 모든 값을 비워주게된다...
문제링크 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 코드 from collections import deque n = int(input()) q = deque(enumerate(map(int,input().split()))) while q: idx,num = q.popleft() print(idx+1,end=' ') if num>0: q.rotate(-(num-1)) else: q.rotate(-num) 문제풀이 dequ..
1. 문제 https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 2. 설명 그리디 알고리즘을 사용하면 다솜이를 제외한 모든 국회의원들 중 표가 가장 많은 사람의 표를 뺏어 오는 것이 가장 유리하다 !! 3. 코드 n = int(input()) dasom = int(input()) vote = [] count = 0 for _ in range(n-1) : vote.append(int(input())) vote.sort(reverse=True..
문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net Algorithm "R"의 개수에 따라 "D"를 입력받았을 떄 배열에서 pop할 위치가 달라진다. "R"을 홀수 번 입력받으면 배열의 마지막 위치에서, 짝수 번(0번 포함) 입력받으면 배열의 첫번째 위치에서 pop시킨다. 그리고 최종적으로 "R"을 홀수 번 입력받았을 경우에는 배열을 reverse 명령어로 순서를 반대로 해서 출력하고 짝수 번(0번 포함) 입력받았을 경우에는 그대로 출력한다. 만약 "D" 입력을 너무 많이 받아 배열의 길이가 0일 ..
![]()
총 후보가 몇 명인지와 각 후보의 득표수를 알고 있을때 이를 이용해서 구해야 하니 하나의 리스트를 이용해 정보를 보관하자. -> 몇 명이든지 정보를 기록하기에는 이 방법밖에 생각이 안난다. 이 리스트에서 나 -> 0번 원소가 최댓값이여야 한다. 따라서 다른 원소가 최댓값이라면 하나를 빼서 나에게 하나를 더 해주고 매수한 표를 하나씩 카운팅하는 법을 사용하자 이 방법을 사용하면 처음부터 내가 최대이거나 내가 최대가 되면 그만 해야하니까 if문과 while문을 야무지게 써주자. 하나 조심해야 할 부분은 내가 최댓값이여도 같은 표를 가진 사람이 있으면 한 표가 더 필요한거니 이 부분을 고려해야 한다. 이 부분들을 고려한 내 코드가 밑에 있다. import sys def main(): N = int(sys.st..
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net package Koala_study.week_5; import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; import java.util.StringTokenizer; public class g_5430 { public static void main(String[] args) { Scanner in = new Scanner(System.in); StringTokenize..
![]()
https://www.acmicpc.net/problem/15903 문제 분석 난이도 실버 1 분류 자료구조, 우선순위 큐 문제 문제 풀이 풀이 우선순위 큐를 이용해 풀 수 있는 문제이다. 앞에서 2개를 pop한 뒤 그 합을 2번 push해주고를 반복하면 된다. 소스코드 from sys import stdin from heapq import heappop,heappush input=stdin.readline n,m=map(int,input().split()) cards=[] for i in map(int,input().split()): heappush(cards,i) for i in range(m): x,y=heappop(cards),heappop(cards) x=y=x+y heappush(cards,x..
