Toolofv 님의 블로그

문제워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자.두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 텍스트라고 부른다.편의상 T의 길이를 n, P의 길이를 m이라고 하자. 일반적으로, n ≥ m이라고 가정해도 무리가 없다. n  1 2 3 4 5 6 7 8 9 …T : [ A B C D A B C D A B D E ] | | | | | | XP : [ A B C D A B D ] 1 2 3 4..

문제오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.N=4이고, S가 아래와 같은 경우를 살펴보자. 예를 들어, 1, 2..

흉노족, 세력으로서의 등장  사마천의 사기에 흉노는 하나라의 후손으로 서주를 밀어버린 훈육과 험윤이 조상이라고 한다. 기원전 4세기말 전국시대에 흉노는 진나라를 공격했다. 중국을 통일한 진시황은 BC215에 몽염을 보내 오르도스 지역의 흉노를 축출하고 만리장성을 쌓았다. 묵돌 선우가 아버지 두만 선우를 죽이고, 선우에 등극했다.(BC209) 묵돌은 명적(소리나는 화살)을 이용해 자신이 명적을 발사하는 대상에게 일제히 사격을 하라고 하였다. 자신의 아내든, 누구든 명적이 도달하는 대상에게 사격을 하라고 했다. 그 과정에서 자신의 지시대로 하지 않으면 무참히 부하를 죽였다고 한다. 그 방법으로 아버지를 제거하고, 흉노족을 통합한다. 당시 중국은 초한전쟁시대(BC206~BC202)였는데 유방이 한나라를 세워 ..

문제N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.1+2+3-4×5÷61÷2+3+4-5×61+2÷3×4-5+61÷2×3-4+5+6식의 계산은 연산자 우선 순위를 무시하..

넷플릭스 드라마 "더글로리"의 흥행 벌써 시간이 꽤 흘렀는데, '더 글로리'란 드라마가 넷플릭스에서 2022년부터 2023년까지 파트1, 파트2로 나뉘어 공개되었고, 흥행을 일으키며 화제가 되었다. 작가를 비판하고자 하는 것은 아니고, 옳고 그름을 떠나 작가는 어찌되었든 현재의 대다수의 한국인들이 공유하고 있는 어떤 감정의 뭉치, 그 흐름을 표현한거라 생각한다. “어서 와, 나의 지옥에 온 걸 환영해” 학교폭력부터 온갖 강자의 횡포, 부조리가 사회에 판치는 듯 보인다. 실제로도 맞는 말이다. 그런데 우리 조금 더 자신을 강한 사람이라 생각하고, 용기를 낼 필요가 있다. 그냥 한 사람의 복수만으로 그쳐서는 안되는 문제이고, 조금 더 면밀하게 현상을 짚어봐야 한다. 고려 경종 때의 복수법 고려 경종(재위 9..

필요한 도구 1. 가로, 세로, 3x3 각 방문리스트2. '0'이 있는 위치를 저장한 리스트 = zero3. dfs 백트래킹 알고리즘 문제해결방법 1. 방문리스트를 가로, 세로, 3x3 공간에 없는 숫자를 체크할 수 있도록 이미 있는 숫자를 반영해둔다.2. 위 3가지 리스트에 없는 숫자들을 빈자리에 채워넣으며, dfs가 호출된 횟수가 len(zero)와 같아지면 모두 채워졌다는 뜻이니, 출력한다. - 코드game = [list(map(int, input().split())) for _ in range(9)]v_sero = [[0 for _ in range(10)] for _ in range(9)]v_garo = [[0 for _ in range(10)] for _ in range(9)]v_3x3 = [[..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제해결방법 1. 문자열을 압축하는 문제다. 압축하는 데 단위를 증가시킬 수 있어야 하고, 최대 단위는 주어진 문자열의 절반일 것이다. 어차피 단위가 그 이상 넘어가면 압축이 되지 않기 때문. 2. 파이썬의 문자열 슬라이싱은 직관적으로 보기 편하고, 쉽다. 이를 이용해 단위에 따른 문자열이 중복되는지를 검사한다. 3. 남은 잔여 문자열도 저장하기 전 반영해줘야 한다. - 코드def solution(s): answer = len(s) for i in range(1, len(s)//2+1): ..

지식 체계는 모두 연결되어 있다. 수학, 과학, 인문학 등 여러 갈래의 학문들이 있지만, 사실 학문은 하나다. 나무는 하나다.그런데 너무 방대해진 모양인지 사람들은 현재 이 학문 전체의 연결을 끊고서 부분적인 전문성만을 갖추려 한다. 글자가 전부 연결되어 있음을 안다면, 자신의 전공을 벗어나 전체의 시야를 갖게 된다. '전문성'이라는 역설적인 한계에 갇혀서 집단이기주의를 쏟아내는 일은 없게 된다. 그런데 사실 한국뿐만 아니라 세계가 현재 누구도 승복하지 않는, 해결되지 않는 매우 논리적인 사람들의 합리적인(?) 갈등을 겪고 있다. 검사는 검사대로, 의사는 의사대로, 경제부처는 경제부처대로, 누구는 누구대로 등등등... 어떤 분야든 자신만의 매뉴얼의 정답을 찾아간다. 자신의 매뉴얼의 정답을 찾아가는데 왜 ..

문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (1 ≤ N 출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 필요한 도구 1. 퀸의 이동방법을 반영할 수 있는 방문리스트 (총 3개)2. dfs 백트래킹 함수 문제해결방법 1. dfs함수에서 다음 재귀함수로 넘어가면서 + 되는 변수는 행이다. 행 어딘가에 한번 놓으면 같은 행에는 놓을 수가 없다. 2. 열 또한 같은 열은 직선루트라 놓을 수가 없다.3. 왼쪽 대각선, 오른쪽 대각선루트도 놓을 수 없다. (대각선은 좌표를 잘보면 규칙성을 찾을 수 있다.) 1. 시간초과가 나온..