이 험난한 세상에서어어~

문제 설명 trie 문제집으로 분류되어 있기는 하지만, 구현 문제다. 그리고 굳이 trie를 안 써도 풀린다... 아무튼 해당 문제에서 특이한 점은 주어진 행렬이 이어져 있다고 생각해야 한다는 점이다. 예를 들어서 (0,0)에서 한 칸 위로 올라가면 (-1,0)이 된다. 그렇다면 해당 좌표는 탐색하지 않는 것이 옳지만, 행렬이 이어져 있다고 생각해야 하니 (2,0)을 탐색해줘야 한다. 즉, 좌표가 0보다 작으면 n-1 혹은 m-1의 위치로 들어가고 n 혹은 m의 위치가 되면 0으로 들어가야 한다는 것이다. 그리고 대각선도 탐색해야 한다는 것을 잊어서는 안 된다. 그리고 출력 부분도 조심해야 한다. 문제에서는 신이 좋아하는 문자열은 중복될 수 있다고 했다. 그러므로 중복된 문자열 또한 해당 문자열의 결과 ..

문제 설명 나무들이 주어졌을 때, 해당 나무가 전체 나무에서 몇 %를 차지하는지 구하는 문제이다. 이때 출력은 알파벳 순으로 한다. 여기서 주의할 점은 전체 종의 몇 %가 아니라 입력받은 나무의 몇 %인지를 의미하는 것이다. https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제 풀이 첫 번째 접근 문자열 집합과 마찬가지로 trie에 분류되어 있는 문제이다. 근데 굳이 trie로 풀 필요는 없을 거 같은... 아무튼 나는 trie로 문..

문제 설명 N개의 문자열로 이루어진 집합 S가 주어질 때, M개의 문자열 중 집합 S에 있는 문자는 총 몇 개인지 구하는 문제이다. https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 난 trie 알고리즘을 연습하고 싶어서 풀었던 문제인데, 사실 굳이 trie 안 써도 되는 문제이긴한다. 문제 풀이 첫 번째 접근 trie알고리즘을 이용해서 풀었다. trie 알고리즘이란 간단하게 말해서 문자열을 검색해주는 것인데, 나..

문제 설명 방향성 없는 그래프가 주어질 때 1부터 n까지 v1과 v2를 지나서 가는 최단 경로를 구하는 문제이다. https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 풀이 첫 번째 접근 다익스트라로 풀어주면 되지만 v1과 v2를 지나가야 한다는 것이 문제이다. 여기서 갈 수 있는 경로는 1에서 v1, v2, n이거나 1에서 v2, v1, n이다. 간단하게 생각해주면 되는데, 일단 1부터 시작하는 다..

문제 설명 해커 yum3이 어느 네트워크 시설의 한 컴퓨터를 해킹했다. 특이하게도 한 컴퓨터가 감염되면 연결되어 있는 다른 컴퓨터도 전염되는 방식인데 웜인가? a가 b라는 컴퓨터에 의존했다면 b 컴퓨터가 감염이 되면 a 컴퓨터 또한 일정 시간 뒤에 전염이 되어 있는 방식이다. yum3이 해킹한 컴퓨터와 각 컴퓨터의 의존성이 주어질 때, 총 몇 대가 감염되고 얼마나 시간이 걸리는지 구하는 문제다. https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 문제..

문제 설명 현재 달리고 있는 선수들의 목록이 주어진다. 이때 해설진들은 순서가 앞으로 한 칸 가는 선수의 이름만 부른다. 게임이 끝났을 때 현재의 등수를 구하는 문제다. https://school.programmers.co.kr/learn/courses/30/lessons/178871 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 첫 번째 풀이 처음에는 단순히 배열에다가 넣어주고 선수 한 명이 나오면 해당 배열에서 선수의 위치를 찾아준 다음에 앞에 있는 선수와 바꿔주는 방식을 이용했다. 그러나 이런 방식은 n^2이 되어서 시간 초과가 난다. 당..