본문 바로가기

전체보기

 (180)
백준[1941] 소문난 칠공주 (Python3) 최적화가 필요한 완전 탐색 문제 BFS로 풀기에는 복잡한거 같아서 DFS로 풀었다. 단순히 상하좌우 탐색으로 한붓그리기가 아니라 어찌됐든 가로세로 연결만 하면 되는 형태이기 때문에 일반적인 상하좌우 탐색 문제풀이에 익숙한 사람이라면 생각이 필요했을 것이다. DFS로 풀기 위해선, 각 함수마다 3개의 정보가 필요하다고 생각했다. 전체 탐색 횟수 Y를 만난 횟수 지나온 경로 1번은 기저 조건을 만들기 위해 필요했고, 2번은 Y는 최대 3개까지 허용되니, 여기에 대한 기록이 필요했다. 3번같은 경우, 모든 탐색마다 기존에 지나온 경로에서 다시 상하좌우로 탐색이 필요했다. 당연한 거지만, 첫 탐색 지점이 Y인 것은 의미가 없다 생각해, S일 때 탐색을 시작했다. 최적화 나는 지나온 경로를 튜플 형태로 관리했기 ..
백준[6987] 월드컵 (Python3) 정직하게 풀어야 했는데 편법쓰다 3번 틀린 문제 증명하는 방법이 복잡했기 때문에 완전 탐색으로 가야 했다. 동일한 조의 국가들은 다른 국가들과 1번씩 경기를 해서, 각 국가는 총 5번의 경기를 해야 한다. 따라서, 국가들이 경기를 하는 모든 경우의 수를 구한 다음 해당 국가끼리 경기를 했을 때, 이긴 경우, 비긴 경우, 진 경우 3가지에 대해 탐색을 한다. 총 15번의 경기를 하고, 매 경기마다 생기는 경우의 수가 3개이니 시간 복잡도는 O(3^15)이다 코드 더보기 import itertools records = [[0 for _ in range(3)] for _ in range(6)] match = list(itertools.combinations(range(6), 2)) ans = 0 def mai..
백준[16496] 큰 수 만들기 (Python3) 생각보다 쉬운 문제 파이썬이 아닌 언어로 풀었으면 조금 돌아가야 했을 것이다. 시도한 방법 1 입력된 수들을 가장 긴 자릿수만큼 자신의 일의자리 수를 더해준다. 예를 들어 입력이 432, 9999 가 들어온다면, 4322, 9999로 맞춰준다. 그다음 내림차순 정렬을 해, 원본 수를 이어붙인다. 반례로 98, 9888889가 들어오면 98이 먼저 와야 하는데 뒤로 가야 하는 문제가 발생했다. 다른 사람 코드 보는 과정에서 알았는데, 끝자리 수만 추가해주는게 아니라 해당 수를 적당히 이어붙이고, 앞에 10개만 가져와서 비교하면 됐었다. (10개만 가져오는 이유는, 수의 범위가 10억 이하이기 떄문) 시도한 방법 2 두 수 A, B가 있을 때, AB와 BA의 값을 비교한 다음 위치를 바꾼다. N의 범위가 매..
백준[16934] 게임 닉네임 (Python3) 제한 시간 2초 치고는 데이터 범위가 작다 싶었는데, 키가 문자열이라 그런지 생각보다 실행 시간이 길었다. 트라이를 사용해 풀었다. 생각이 필요했던 부분이 입력된 입력된 닉네임이 고유한 닉네임이면 접두사를 별칭으로 해주고, 다음에 같은 닉네임을 입력받으면, 닉네임 + 중복 수를 별칭으로 해줘야 하는 거였다. 따라서, 삽입 전에 탐색을 통해 중복되는 닉네임이 있는지 확인할 필요가 있었다. 탐색에선 먼저 접두사를 구한 다음, 구해진 접두사의 길이가 닉네임의 길이와 같다면 중복된 닉네임으로 간주해 해당 닉네임의 카운트를 붙인 별칭을 반환해 출력했다. 코드 from collections import defaultdict class Trie: def __init__(self): self.root = {} self..
백준[13505] 두 수 XOR (Python3) XOR 연산으로도 풀 수 있지만, 트라이로 풀었다. XOR 연산이 1과 0으로 이루어지기 때문에, 각 수들을 이진수로 변환한 값들을 트라이로 만들어주면 된다. 편의상 최대 자릿수를 구한 다음, 이 길이에 맞춰 다른 이진수들에 padding 값으로 0을 붙였다. 이걸 안 해주니 탐색 코드에서 이진수 자릿수까지 검증해야 해서 불편했다. 탐색 과정은 다음과 같다. 현재 자릿수와 반전되는 수가 노드에 있는지 본다. (1이면 0, 0이면 1) 있다면 임시 배열에 1 추가. 아니면 0 추가 임시 배열에 있는 값으로 십진수 변환 코드 class Trie: def __init__(self): self.root = {} def insert(self, S): current_node = self.root for s in S..
한국항공대 소프트웨어학과 학술제 월드소프트콘 참여 후기 차세대 보안리더 BoB에 활동한 경험이 있어, 여기에 대해 소개를 해달라는 부탁을 받아 참여하게 됐다. 타 학교를 보면 보안 동아리를 잘 운영해 이쪽으로 방향을 잡은 분들도 있었는데, 우리 학교에는 이런 게 없었다는 게 좀 아쉽기도 했었다. 그래서 이번 학술제 참여가 개발에 집중된 우리 학교에 보안이란 새로운 방향을 제시할 수 있다 생각했다. 발표 시간은 20분으로, 같은 학회원 친구와 같이 배정됐다. 발표 준비를 하면서 사실 BoB에 활동한지는 꽤 됐다. 1학년 새내기 때 시작한 대외 활동이었고, 현재는 4학년이어서 그동안 BoB에서도 많은 것이 바뀌었다. (센터가 강남이 아니게 된 게 너무 아쉽다.) 그래도 알고 지내온 수료생분들 사이에서 이것저것 들은 게 있고 현재 4기 친구 한 명이 PL로 활동하..
백준[17612] 쇼핑몰 (Java, Python3) 자료 구조를 만들어 정렬하거나 관찰을 통해서 풀 수 있는 문제 추가시간이 없기 때문에, 10^7 내에 끝내야 한다. 완전 탐색 매초 각 계산대의 물건 카운팅을 1씩 감소시키면서 0이 된 계산대엔 새로운 대기자를 넣는다. 시간 복잡도 계산을 하면서 헷갈렸던 게 고객은 큐로 관리하고, 계산대만 루프를 통해 확인하는 식이기 때문에 O(KW)로 완전 탐색이 가능하다 생각했지만 골 2란 점이 계속 신경 쓰였다. 그래서 조금 최적화하는 방향으로 갔다. 완전 탐색 최적화 계산대를 탐색하는 빈도를 줄이는 방향으로 갔다. 현재 계산대에 물건이 가장 적은 값을 찾는다. 모든 계산대에 그 값만큼 빼준다. 모든 계산대의 물건값이 0이면서 대기 큐가 빌 때까지 반복한다. 우선순위 큐 태그를 확인하니 우선순위 큐 문제길래, 여기..
백준[16928] 뱀과 사다리 게임 (Python3) 테스트케이스 짜보는 연습해 보기 좋은 문제 완전 탐색 현재 지점부터 +1 ~ +6까지의 지점을 갔을 때에 대한 결과를 큐에 넣고, 100이 될 때까지 탐색한다. 하지만, 뱀을 만나게 되면 다시 돌아가게 돼서 그 지점부터 탐색이 계속 진행되기 때문에 무한 루프가 된다. 완전 탐색 최적화 1에서 7을 가는 최단 경로는 주사위 6이 나와서 이동하는 경우다. 그 외의 방법으로 가는 경우는 비효율적이므로 배제한다. 따라서, 방문 처리 배열을 하나 만들어 이동할 지점에 도달하기 위해 굴린 주사위 수가 현재 굴린 주사위 수 + 1보다 크면 큐에 현재 정보를 추가한다. 주의해야 할 점 사다리를 탈 때 무작정 이 사다리가 더 높이 간단 이유로, 그 사다리만 골라서 가면 안 된다. 뱀을 통해 내려간 곳 근처에 있는 사다리..

티스토리툴바