programmer life guidance 101

https://www.acmicpc.net/problem/1167 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 16697 6017 4382 35.067% 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다. 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째..

https://www.acmicpc.net/problem/1158 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 42044 20375 14627 48.405% 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K..

https://www.acmicpc.net/problem/1107 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 43887 10219 6970 22.347% 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램..

https://www.acmicpc.net/problem/1076 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 16623 6600 5656 40.034% 문제 전자 제품에는 저항이 들어간다. 저항은 색 3개를 이용해서 그 저항이 몇 옴인지 나타낸다. 처음 색 2개는 저항의 값이고, 마지막 색은 곱해야 하는 값이다. 저항의 값은 다음 표를 이용해서 구한다. 색 값 곱 black 0 1 brown 1 10 red 2 100 orange 3 1000 yellow 4 10000 green 5 100000 blue 6 1000000 violet 7 10000000 grey 8 100000000 white 9 1000000000 예를 들어, 저항에 색이 yellow, violet, r..

https://www.acmicpc.net/problem/1062 문제 남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다. 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N과 K가 주어진다..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 MN 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 88 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다..

> 비트마스킹 bitmask : 정수의 이진수 표현을 자료구조로 쓰는 기법 데이터들은 0과 1의 집합이라고 합니다. 비트는 네트워크 외에도 운영체제 등에서도 자주 접할 수 있는데요 때문에 최적의 성능을 위해 여러 곳에서 쓰이고 있습니다. 이진 숫자로 0, 1 값을 가질 수 있고 이에 따라 true/false, on/off 와 같은 상태를 나타내는 것이 가능합니다. 비트마스크 장점 먼저 비트마스킹의 장점을 알아 보겠습니다. 빠른 수행시간 시간복잡도 O(1)에 구현되는 것이 많습니다. 비트마스크를 사용할 수 있다는 말은 원소의 수가 많지 않다는 뜻이기 때문에, 큰 속도 향상을 기대할 수는 없지만 여러번 수행해야 하는 경우에는 작은 최적화도 큰 속도 향상을 가져올 수 있습니다. 간결한 코드 양한 집합 연사자들..

> Prefix Sum 누적 합, 구간 합 누적합 또는 구간 합을 빠르게 구하는 알고리즘입니다. 여기서 주의해야할 것은 부분 합 은 0 ~ k까지의 합을 의미하는 것이고 구간 합은 a ~ b까지의 합을 의미 합니다. 이러한 알고리즘은 어디에 쓰일까요? 아래와 같은 문제를 예시로 봅시다. int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 배열이 존재한다. 이 때 a에서 b의 구간 합을 요구하는 쿼리 "2천만개"가 들어온다. 이러한 문제에 대해 어떻게 해결 할 것인가? 가장 쉬운 방식은 브루트 포스를 이용해 일일이 더하는 것입니다.하지만 쿼리 2천만개를 1초만에 해결해달라고 요구 했을 때, 이 코드의 시간복잡도를 보면 쿼리 2천만개 * (a에서 b의 합 구하는 for 문의 최악..

Longest Increasing Subsequence) 최장 증가 부분 수열 임의의 수열이 주어졌을 때, 이 수열에서 몇 개의 수 들을 선택해 부분수열을 만들 수 있는데, 이 때 만들어진 부분수열 중 오름차순으로 정렬 된 가장 긴 수열을 최장 증가 수열이라고 한다. 여기서의 부분 수열은 반드시 연속적이거나 유일하지 않아도 된다. 예를 들어 arr[ ] = {10, 20, 10, 30, 20, 50}의 수열이 있다고 할 때 여기서의 LIS는 {10, 20, 30, 50}이고 길이는 4일 것이다. 이제 이를 O(N2)과 O(nlogn)의 시간복잡도를 가지는 두 가지 방법을 알아보자. 1. DP 풀이 과정은 아래와 같다. i번째 인덱스에서 끝나는 최장 증가 부분 수열의 마지막에 arr[k]를 추가했을 때의 ..

> Levenshtein 알고리즘 편집 거리 알고리즘 (edit distance) Levenshtein distance 는 string 간 형태적 유사도를 정의하는 척도입니다. 만약 우리가 단어 사전을 가지고 있고, 사전에 등록되지 않은 단어가 발생한다면 Levenshtein distance 가 가장 가까운 단어로 치환함으로써 오탈자를 교정할 수 있습니다. 그러나 Levenshtein distance 는 계산 비용이 비쌉니다. 이 때 간단한 inverted index 를 이용하여 비슷할 가능성이 있는 단어 후보만을 추린 뒤 몇 번의 Levenshtein distance 를 계산함으로써 효율적으로 오탈자를 교정할 수 있습니다. String 간의 형태적 유사도를 정의하는 척도를 string distance ..

Longest Common Subsequence 최장 공통 부분 수열 여기서 substring은 연속된 부분 문자열이고, subsequence는 연속적이지 않은 부분 수열이다. 예로, "iamstudent" 라는 문자열에서 연속된 부분 문자열 mstu은 substring이 되고 연속적으로 이어지지는 않지만 순서는 맞는 mtue는 subsequence가 된다. 그렇다면 공통 부분 수열이란, 두 문자열이 공통으로 가지고 있는 부분 수열이다. 에를 들어 "CDABE" 와 "CDEGT"가 있다면 공통부분 수열은 {}, {C}, {D}, {E}, {C, D}, {D, E}, {C, E}, {C, D, E} 일 것이다. 최장 공통 부분 수열이란 공통 부분 수열 중에서 길이가 가장 긴 부분 수열을 뜻한다. 대표적으로..

programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이 programmers.co.kr 문제설명 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다. 예를 들어..

www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 문제 트리는 사이클을 갖지 않는 연결된 그래프이다. 중앙 정점은 모든 정점으로 이르는 비용의 합이 가장 작은 정점이다. 트리의 정점 개수가 작은 경우에는 모든 경우의 수를 다 계산해보는 프로그램을 이용해 쉽게 구할 수 있다. 위의 그림은 가중치가 있는 트리로, 정점의 개수는 5개이다. 이 트리의 중앙 정점은 B이다. B-A = 2, B-D = 7, B-C = 1, B-E = 7+5=12, ..

leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ Binary Tree Zigzag Level Order Traversal - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to le..

> 트라이(Trie) 여튼 또 문자열인데, 이번엔 매칭 문제가 아니라 여러 문자열을 저장하는 자료구조를 소개해드릴 겁니다. 바로 트라이(Trie)인데, 트리와 굉장히 스펠링이 비슷하면서 트리와도 유사합니다. 아니, 아예 트리의 한 종류라고 해도 될 겁니다. 래딕스 트리(radix tree)나 접두사 트리(prefix tree)라고도 합니다. 예를 들어 {"he", "she", "her", "him", "show"}라는 문자열 집합이 있다면, 그들을 담고 있는 트라이는 그림과 같습니다. 빨간색 겹선 노드가 여기서 끝나는 문자열이 있다는 뜻으로, output이 있다고 하거나 final state, accepting node라고도 하는 등... 그런 의미가 있습니다. 왜 트라이의 별칭 중 접두사 트리라는 것이..