https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 최근에 함수형 인터페이스를 공부했었는데 활용하기 좋은 문제 인거 같아 정리해보고자 한다. 문제 분석 3칸씩 n개의 줄로 주어지는 숫자들에서 숫자를 하나씩 골라 더했을 때 최대값, 최소값을 구하면 된다. 이때 숫자를 고르는 조건은 현재 숫자를 고른 행,열을 기준으로 다음 행에서는 현재열과 인접한 열의 숫자만 고르는게 가능하다. 즉 현재 고른숫자가 제일 왼쪽이라면 다음에 고를수 있는 숫자는 왼쪽과 가운데, 제일 오..
https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 이번 포스팅에서는 스택을 활용하기 좋은 문제를 다뤄보도록 하겠다. 먼저 문제 분석을 하자면, 입력받은 문자열중 , - , 그 이외의 문자인경우로 나눠 다른 동작을 수행하게 한 후 최종 결과를 출력해주면 된다. 화살표의 경우엔 커서를 의미하고 - 의 경우 문자 지우기, 그 이외의 문자의 경우 입력을 의미하는데 각 문자에 따라 스택을 활용해 표현하면 다음과 같이 표현이 가능하다. 우..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 이번 포스팅에서는 삼성 A형 기출문제인 파이프 옮기기 1 문제를 다뤄보도록하겠다. 먼저 문제 분석을 하자면 N*N 크기의 행렬 시작점 (0,1) 에서 종점 (n,n) 까지 도달가능한 모든 경우의 수를 찾는 문제로 이동가능한 방향은 가로, 세로, 대각 세가지 방향으로만 진행이 가능하며 벽이 존재하기 때문에 벽에 막혀 진행하지 못하는 경우는 제외해주어야 한다. 이때 대각 방향..
https://www.acmicpc.net/problem/7432 7432번: 디스크 트리 갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파 www.acmicpc.net 이번 포스팅에서는 트라이를 순회하는 문제에 대해 다뤄보도록 하겠다. 이전 포스팅에서도 언급한적이 있듯 키 집합으로 하위노드가 정렬된 트라이로 생성한다면 전위순회를 통해 사전순으로 저장된 데이터를 출력할수 있다. 그럼 바로 문제 분석으로 들어가도록 하겠다. 여러줄로 디렉토리경로가 주어지고 경로의 구분자는 \ (역슬래시)로 한다. 이를 하위 디렉토리라면 한칸씩 띄운뒤 사전순으로 출력해주면 된다. 핵심 ..
https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 이번 포스팅에서는 ICPC에서 출제된 트라이를 사용하는 문제가 있어 한번 다뤄보도록 하겠다. 먼저 트라이에 대해 알고싶다면 하단의 링크를 참조하도록 하자. https://0bliviat3.tistory.com/53 [자료구조] 트라이(Trie)의 구현 (JAVA) 이번 포스팅에서는 문자열 데이터를 다루기에 최적화된 자료구조중 하나인 트라이에 대해 다뤄보고자 한다. 먼저 위키..