Outgoing Introvert

△ 큐 Silver4 백준 2164 카드2 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.N이 주어졌을 때, 제일 ..

× 큐 백준 18258 큐2 Swift 에 회의감이 들게 하는 문제다,, 계속 시간초과 뜨는데 아무리 다양한 방식으로 구현해봐도 내 코드는 어디가 문제인지 전혀 모르겠고,, 알고리즘 구현을 잘못해서 발생하는 문제는 아닌거같은데 Swift 입출력이 느려서 그렇다나뭐라나 아무튼 개빡침,, FileIO 사용해서 어케어케 하면 통과시켜주는듯,, 백준에서는 시간초과로 통과를 안시켜주지만 Swift에서 더블스택을 사용하여 큐를 구현했을 때 생기는 의문점이 있어 공유해본다. 보통 시간복잡도가 O(n)인 removeFirst()를 사용하지 않고 dequeue를 효율적으로 구현하는 방식으로 다음 두 가지를 흔히 사용한다. 1. 포인터를 사용한 큐 구현 2. 더블 스택 큐 를 제시한다. 1. 포인터 사용 removeFir..

△ 스택 Silver 2 백준 1874 스택 수열 문제 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 입력 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다. 출력 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, po..

○ 스택 Silver 4 백준 4949 균형잡힌 세상 종료 조건 "." 이 들어올 때까지 문장을 input 으로 받아서 알파벳은 무시하고 [] () 괄호 짝만 맞추면 되는 문제. ( 혹은 [ 이면 push ] 혹은 ) 이면 확인하고 pop 마지막에 스택 남는거 확인하고 리턴 while true { let input = readLine()! if input == "." { break } else { print(isBalanced(input)) } } func isBalanced(_ input: String) -> String { var stack: [Character] = [] for i in input { switch i { case "(", "[": stack.append(i) case ")": if ..

○ 스택 Silver 4 백준 10773 제로 K개의 줄에 정수가 하나씩 주어질 때마다, 해당 정수를 push 해주고 0일 경우 pop 해주면 되는 간단한 문제. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다. 라고 되어 있어 딱히 옵셔널 처리도 안해줘도 됨. let k = Int(readLine()!)! var stack: [Int] = [] for _ in 0..

○ 스택 Silver 4 백준 10828 스택 문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. - push X: 정수 X를 스택에 넣는 연산이다. - pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. - size: 스택에 들어있는 정수의 개수를 출력한다. - empty: 스택이 비어있으면 1, 아니면 0을 출력한다. - top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩..

○ DFS/BFS Silver 2 백준 2644 촌수계산 문제 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호 셋째 줄에는 부모 자식들 간의 관계의 개수 m 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대 한 명만 주어진다. 출력 입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 두 사람의 친척 관계..

× BFS Silver 1 백준 2178 미로 탐색 문제 N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. 출력 첫째 줄에 지..

○ BFS 백준 2606 바이러스 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 컴퓨터의 수. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. 출력..

× DFS/BFS 백준 1260 DFS와 BFS 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다..