🌱1 Day, 1 Commit Wonseok's Record

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 해설 : 알파벳 소문자로 이루어진 단어 N개가 주어질 때 이를 조건에 맞게 정렬하는 문제이다. 조건 1. 길이가 짧은 것이 앞으로 조건 2., 길이가 같다면 사전순으로 가까운 것이 앞으로 풀이 : 쉬운 정렬 문제이다. 주어진 알파벳들을 list에 넣고 sort 함수를 사용하면 된다. 풀이를 보면 정렬을 2회 진행하였는데 이 때는 Python의 이해도가 조금 낮았던 것 같다. 지금 푼다면..

해시(Hash) 해시란 ? 해시를 정리해둔 글을 살펴보면 "해시는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말합니다. 쉽게 말해, 아무리 큰 숫자를 넣더라도 정해진 크기의 숫자가 나오는 함수입니다. " 라고 말합니다. 해시를 많이 사용해본 저도 한 번에 이해하기 어려운 문장입니다. 제가 이해하고 있는 개념으로 해시의 사용을 설명해보자면 다음과 같습니다. (개인적인 견해이므로 맹신하지는 말아주세요) 1. 어떠한 값(데이터)을 해시화하여 만들어진 결괏값 그 자체. 대표적으로 정보의 암호화를 예시로 들겠습니다.회원가입시에 사용자의 민감정보인 비밀번호화 같은 데이터들은 날 것 그대로 데이터베이스에 저장할 수 없습니다. 당연히 보안에 취약하기 때문이죠. 이를 해결하기 위해 해시 ..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 해설 : 트리의 노드와 간선정보가 주어질 때, 임의의 두 노드사이의 최대거리를 구하는 문제이다. 풀이 : BFS의 구현은 쉬웠지만 답을 도출하는 아이디어를 떠올리기 힘든 문제였다. 1. 루트노드에서 BFS로 탐색하여 가장 멀리 떨어진 노드를 찾는다. 2. 루트로부터 가장 멀리 떨어진 노드로부터 가장 멀리 떨어진 노드를 찾는다. BFS를 총 2회 실행해야 찾을 수 있는 문제였다. 소..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 해설 : N명의 사람이 원을 이루면서 앉아있다고 할 때, 순서대로 K번째 사람을 제거한다. 모든 사람이 제거될 때까지 K번째 사람을 계속 제거한다. 이 때, 제거되는 사람들의 순서를 요세푸스 순열이라고 한다. N과 K가 주어질 때 요세푸스 순열을 찾는 문제이다. 풀이 : 사람이 원형으로 앉아있는 모습을 구현하기 위해 원형 큐를 사용하였다. 실제로 구현한 것은 아니지만 비슷한 기능을 하게끔 구현하였는데 방법은 다음과 같다. 1. K번 만큼 queue의 popleft()값을 append()해..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 해설 : N개의 집이 있고 집을 색칠하는데 드는 비용이 R, G, B 색깔별로 주어진다. 이 집을 R, G, B의 색들 중 하나로 색칠하려 할 때, 인접하는 집 끼리는 색이 같지 않게 색칠하는 방법 중 비용이 가장 적게 드는 경우의 비용을 찾는 문제이다. 풀이 : DP문제이다. 0번째 집부터 각 집마다 색칠하는데 드는 총 비용중 최솟값만을 갱신하며 계산한다. 핵심은 인접한 집..

https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 해설 : N명의 사람을 키순으로 줄 세우려 한다. 각 사람의 키는 1, 2, 3, 4 ··· 순으로 증가하게 주어진다. 또한, 사람들은 줄을 설 때 자기보다 키가 큰 사람이 자신의 왼쪽에 몇 명 있었는지만 기억하고 있다. 이 때, 주어진 조건으로 사람들을 줄 세우는 방법을 출력하는 문제이다. 풀이 : 주어지는 배열은 사람들이 자신의 왼쪽에 자기보다 큰 사람이 몇 명 있었는지 기억하는 대이터..

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 해설 : 문자열 A와 B가 주어졌을 때 A의 앞이나 뒤에 아무 글자나 붙일 수 있다고 가정하고 B랑 차이가 최소인 문자열을 만드려고 한다. 만들 수 있는 A와 B의 차잇값중 최소를 출력하는 문제이다. 풀이 : 쉬운 문제이다. A의 길이가 B보다 같거나 작으므로 B에서 0번부터 len(B)-len(A)+1만큼 문자열을 잘라주면서 A와의 차이를 구하면 된다. 이..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 해설 : 수빈이는 리모컨을 조작하여 원하는 채널로 이동하고 싶다. 그러나 리모컨의 버튼이 몇 개 고장나서 직접적으로 이동할 수 없는 상황이다. 고장나지 않은 버튼과 +, -버튼만을 이용하여 원하는 채널로 바꿀 때 버튼을 누르는 최소 횟수를 찾는 문제이다. 수빈이의 현재 채널은 100번이다. 풀이 : 우선 고장난 버튼을 제외하고 가능한 버튼에 대한 정보를 담아두고 이 정보를 이용해서..

https://www.acmicpc.net/problem/1105 1105번: 팔 첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 해설 : 자연수 L과 R이 주어질 때 L보다 크거나 같고 R보다 작은 자연수들 중 8이 가장 적게 들어있는 경우의 8의 개수를 찾는 문제이다. 풀이 : L의 자릿수만큼 for문을 반복하여 L과 R의 자릿수를 각각 비교한다. 이 때, 자릿수가 다르다면 그 때까지 8의 개수를 센 값을 출력하고 아니라면 L 과 R의 자릿수가 모두 8인지 확인한다. 이는 L이나 R의 자릿수가 둘 다 8이 아니면 다른 수를 넣어 8이 아니게 만들 수 ..