Definition of Seon

1. 문제 이 문제는 접두사X집합의 최대 크기를 구하는 문제이다.주어진 배열에서 어떤 단어가 다른 단어의 접두어가 되지 않는 부분집합을 만들어야 한다.단어의 개수는 최대 50이어서 숫자가 크지 않다. 2. 풀이접두어가 되려면 자신보다 길거나 같은 길이의 문자여야 하므로길이를 기준으로 짧은 길이부터 긴 길이 순으로 정렬을 했다.이후 이중 반복문을 사용하여 가장 짧은 단어부터 시작해 자기 자신 다음 단어부터 가장 긴 단어까지 확인한다.만약 단어 j를 i 단어의 길이 만큼 잘라서 i와 자른 j가 같다면 단어 i는 부분집합에 들어갈 수 없다. 직접 배열 자체에서 그 단어를 삭제하는 것도 방법이지만,결국 출력해야 하는 것은 크기 값 뿐이므로 ans 변수를 새로 만들어 겹치는 단어를 빼주었다.처음에는 n 자체를 변..

1. 문제 이 문제는 스티커를 뗄 때 얻을 수 있는 최대 점수를 구하는 문제이다.그러나 스티커를 떼면 맞닿는 스티커들은 사용할 수 없어진다. 2. 풀이이 문제는 코테 스터디에서 시간을 정해두고 풀었다.20분 정도 소요되어서 풀었다.이전에 풀어봤던 dp 문제들 덕에 금방 풀이 방법을 생각해냈다. 스티커 배열을 입력받고 그것과 같은 형태로 dp 테이블을 초기화한다.자기 자신을 뜯을 경우에는 바로 왼쪽 칸은 뜯을 수 없고, 대각선에 있는 걸 뜯을 수 있다.그래서 자신 + 왼쪽 대각선을 뜯은 값과 왼쪽 칸을 뜯은 값 중 최댓값으로 dp 테이블을 갱신한다.마지막에는 모든 값 중 최댓값을 출력한다.3. 코드import sysinput = sys.stdin.readlinet = int(input()) #테스트케이스f..

1. 문제 이 문제는 호텔의 홍보 비용에 따른 고객 수 증가 정보를 가지고호텔의 고객을 c명 이상 늘이기 위해 투자해야 하는 돈의 최솟값을 구하는 문제이다. 2. 풀이[접근 1 - dfs] 시간초과처음에는 dfs를 활용하여 재귀 형태로 모든 경우의 수를 확인하도록 했다.모든 방법을 확인하다가 고객 수가 c 이상이 될 경우 최솟값을 갱신하고 return하는 형태이다.답을 찾는 데는 무리가 없었으나 시간초과가 떠버렸다.이에 시간을 줄일 수 있는 다른 방법을 고민했다. [접근 2- dp]목표 고객 증가 수인 c에다가 한 번의 투자로 늘어날 수 있는 최댓값인 100을 더해서 dp테이블을 만들었다.혹시 c보다 c+1이 더 비용이 적게 들 수도 있기 때문이다.dp 테이블은 모두 큰 수로 초기화해두고 반복문을 돌렸다..

1. 문제 이 문제는 선수의 능력치를 고려하여 포지션을 정해 가장 최대의 능력치를 구하는 문제이다.11명의 선수들에 대해 11개 포지션에 대한 능력치를 수치화하여 제시한다.그 숫자들 중 모든 경우의 수를 고려하여 가장 최대의 합을 구하는 문제이다.즉, 전형적인 백트래킹 문제.2. 풀이솔직히 이 문제를 어떻게 풀어야 할지 감이 안 왔다.아직 알고리즘 실력이 부족하기 때문인 것 같다.어떤 상황에서 어떤 알고리즘을 써야 하는지 아직 잘모르는 것 같아서백트래킹 알고리즘을 다시 정리해야겠다고 생각했다.https://jemarque.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-Backtrackin..

최근 코딩테스트 문제를 풀면서 알고리즘 정리가 필요함을 느꼈다.자주 출제되는데 아직 나에게 어려운 백트래킹을 먼저 정리해보려고 한다. 백트래킹 모든 경우의 수를 고려하는 알고리즘 백트래킹은 재귀를 활용해 모든 경우의 수를 확인하는 알고리즘이다.대표적으로 DFS, BFS를 사용하며 코딩테스트에서 잘 다루어지는 알고리즘이기도 하다.시간복잡도는 중복이 가능한 경우, N**2이고 중복이 불가한 경우는 N!이다. 목표한 조건에 도달하는 경우를 탐색하는 것인데,절대 목표에 도달할 수 없다고 판단이 되면 앞으로 돌아가서 다시 그 조건에 맞는 경우를 탐색한다. 1. DFS깊이 우선 탐색트리에서 바닥에 도달할 때까지 한쪽 방향으로만 내려가는 방식으로재귀함수를 사용하여 목표한 바가 나올 때까지 반복한다.일반적으로 모든 경..

1. 문제 이 문제는 어떤 단어가 주어지고 사전식 정렬을 하였을 때그 바로 다음에 오는 단어를 찾는 문제이다.2. 풀이[접근 1]처음에는 모든 사전식 배열을 다 늘어놓고그 중에서 입력값을 찾은 뒤, 그 다음 값을 출력하는 방식을 생각했다. 1. 순열 라이브러리를 이용해 단어 조합을 모두 리스트에 넣는다.2. 처음 입력한 단어의 인덱스를 찾는다.3. 마지막 단어가 아닐 경우 다음 단어를 출력한다. 역시 코드 자체에 문제는 없었으나 결과가 시간 초과가 떠버렸다.필요 없는 데이터까지 다 구해서일까...바로 다음 순열을 어떻게 찾을지 긴 시간 고민했다. [접근 2]고민의 과정을 거쳐 뒤에서부터 숫자 크기를 비교하는 방식을 발견했다.그 뒤 숫자 위치를 바꾸고 거꾸로 정렬하는 방식으로 문제를 해결할 수 있었다.뒤의..

백준 20436번 ZOAC 3 1. 문제 이 문제는 쿼티 자판에서 타자를 칠 때 걸리는 시간의 최솟값을 구하는 문제이다.키를 누르는 데 1의 시간이 걸리고 이동하는 데 두 좌표의 거리 (직선 거리 말고 택시 거리) 만큼의 시간이 걸린다.독수리 타법, 즉, 양손의 손가락을 하나씩만 사용하는 타법이고 왼손과 오른손은 한글 자음 모음의 위치로 구분한다.2. 풀이조금 귀찮은 구현 문제였다.쿼티식 키보드에 있는 모든 문자, 즉 알파벳 26개를 모두 배열에 넣어야했다.거리 계산의 간편함을 위해 가장 아래 왼쪽에 있는 'Z'를 (0,0)이라고 생각해서큰 배열 안에 3개의 줄이 있는 이중배열 구조로 키보드를 표현했다. 입력값은 모두 좌표가 아닌 문자로 주어지기 때문에 이걸 좌표로 바꾸는 함수를 만들었다.coordina..

백준 21918번 전구https://www.acmicpc.net/problem/21918 1. 문제 전구의 상태를 숫자 0과 1로 표현한다.전구가 꺼진 경우는 0, 켜진 경우는 1이다.전구를 제어하는 명령어 1~4번을 입력된 순서대로 처리한 뒤의 전구 상태를 확인하는 문제이다. 2. 풀이이 문제는 간단한 구현 문제로, 난이도가 쉬운 편이었다.각각의 명령어를 수행하는 코드를 짜서 명령어가 입력된 순서에 맞게 실행만 시키면 된다. 함수형 프로그래밍 구현을 위해 조건문을 사용해 각 경우를 함수 안에 넣었다.반복문을 사용해 명령어들을 입력받은 순서대로 실행했다. 3. 코드처음 시도에서는 평소 자주 사용하던 방식대로 입력 받은 명령어 정보를 배열에 저장했다.그 뒤에 배열에 저장한 각각의 명령어 정보에 대해 순서대..

그간 포스팅이 뜸했다. 마음의 정화를 위해 8월 중순부터 여행을 잔뜩 다녀왔다. 제주도 여행과 부산 여행을 통해 마음이 조금이나마 가벼워졌다. 이제 9월, 다시 달릴 시간. 이산수학 강의를 듣다가 이상한 부분들을 발견했다. 강의 앞뒤가 잘려 있어 숙제를 못 듣거나 ppt에 빠진 내용이 있었던 것. 그래서 조금 더 최신 자료를 이용하고자 coursera를 검색했다. 내가 선택한 과정은 Introduction to Discrete Mathematics for Computer Science이다. 이 강의에는 5개의 강좌가 포함되어 있다. 1. Mathematical Thinking in Computer Science (6주) 2. Combinatorics and Probability (6주) 3. Introd..