www.acmicpc.net/problem/5829 5829번: Luxury River Cruise Farmer John is taking Bessie and the cows on a cruise! They are sailing on a network of rivers with N ports (1
분류 전체보기
www.acmicpc.net/problem/19538 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net 아이디어: 큐를 두개를 사용하여서 루머를 믿는 사람을 저장하는 큐 A와 A의 인접한 노드들을 저장하는 큐 B로 나눈다. A의 요소들을 pop하면서 시간을 저장하고 해당 요소의 인접리스트를 B에 저장한다. A의 요소가 모두 비게 되면 시간이 +1되는 것이다. 그리고 B의 요소들을 pop하면서 루머에 감염되었는지 여부를 판단하고 감염된 노드만 A에 다시 추가한다. 처음에는 최..
www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 아이디어: 앞선 A->B 문제와 비슷한 방식으로 그래프를 구현하여 풀 수 있을 것 같다. 대신 이번 문제는 무조건 BFS로 풀어야 한다. 생각해야 할 조건이 많아서 예상외로 까다로웠다. 처음에 그냥 제출하니 메모리 초과가 났고.. 그래서 한 번 만든 수를 다시 만들지 않도록 visit 배열을 추가했다. 예를 들면 *2를 하여 이미 한번의 경로만을 사용하여 만든 수를 +1 두번을 사용하..
www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A *2 끝에 1을 추가 -> *10+1 A부터 시작해서 갈 수 있는 경우가 2가지밖에 없으니까 그 방향으로 BFS로 탐색하면서 B가 나오면 도달하기까지 간선의 개수+1를 출력한다. 큐에 [변해가는 A의 값, cnt]를 추가하면서 탐색을 진행하고, n[0]이 B보다 큰 경우에는 연결된..
www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 아주 기본적인 DFS, BFS 구현 문제이다. 백준 기록 보면 인접리스트로 푼 것과 인접배열로 푼 것 두 가지 방식을 확인할 수 있다. dfs를 구현하는 방식에는 재귀함수로 구현하는 방법과 스택을 이용하는 방법 두 가지가 있는데, 이 문제에서는 정점번호가 작은 순서대로 출력해야해서 재귀함수로 구현하는 방법이 더 나을 것 같아 그렇게 풀었지만, 코드는 일단 올려놓는다. (df..
www.acmicpc.net/problem/20002
www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 아이디어: 부분합을 이용하면 되지 않을까. 2k+1만큼의 길이를 더하면서 최댓값을 갱신한다.. 일단 ice배열을 1,000,000개씩 만들고, g와 x를 받으면서 ice[x]=g를 넣는다. 그리고 큐를 하나 만들어서 ice를 하나씩 추가하고 길이가 2k+1이 되면 하나씩 pop하고 다음 걸 더한다. 이때 최댓값을 갱신해준다. 간단한 문제인데.. 이렇게 막막하면 우짤꼬....ㅠㅠ #게으른 백곰 import sys from collect..
www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 아이디어: 주어진 수열을 돌면서 F(Ai) 배열을 채운다. 무식하게 풀어보자면.. 그냥 배열을 돌면서 다 비교할 수 있겠지만 그러면 O(n^2)이므로 시간초과가 날것이다.. 구글링을 해보니, 스택으로 조금만 생각하면 쉽게 풀 수 있었다. 일단 뒤에서부터 배열을 읽어나가는 게 핵심이다! 그리고 F[i]의 값을 스택에 push하되, 만약 현재 읽는 배열의 F[i]값이 스택의 top보다 작다면 NGF(i)는 스택의 top이 된다..
www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 아이디어: 스택을 이용하면 될 것 같은데. 앞서 풀었던 괄호 문제랑 비슷하게. 스택을 만들고 왼쪽 괄호인 경우에는 push, 오른쪽 괄호인 경우에는 스택의 하나를 pop한다. 이때 pop한 값이 왼쪽 괄호이고 짝이 맞으면 조건에 맞게 숫자를 push해야 되는데, 이때 스택에 남아 있는 값이 뭔지 peek해보고(값이 남아있지 않을 경우 예외처리 해줘야 함), 숫자가 있으면 그것도 pop해서 더한 후 숫자를 pu..
www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 아이디어: #덱 뽑고자 하는 원소가 맨 첫번째 원소가 될때까지 왼쪽이나, 오른쪽으로 이동시키는 최소 횟수를 구하면 된다. 근데 그 최소횟수는 어떻게 구하지? 덱에서의 해당 원소의 위치를 알아야 할 것 같은데.. -> index(x) index(x) popleft() 반대면 pop() 을 한다. 이 값이 뽑고자 하는 원소와 일치하지 않으면 각각 반대편에 다시 추가하고, ans+=1한다. 같은 경우 poplef..
