킹의 개발일지

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제를 풀 때 벽을 어떤 규칙으로 세워야 최대 크기의 안전 영역을 구할 지 매우 고민했던 문제이다. 한참을 고민해도 마땅한 규칙이 생각나지 않아서 '이거 그냥 일일히 벽 세워보고 안전영역 세어봐야 하는거 아냐?' 라고 생각했었는데... 그게 정답이었다... 이 문제에서 주어지는 맵의 크기도 8x8이고, 벽을 세울 수 있는 모든 조합의 수는 64C3 이기에, 이는 100,000 보다도 작은수이다. 시간제한이 2..

순환 알고리즘의 설계 아직 내 뇌가 절차적인 방식에서 벗어나지 못한듯하다.. 뭔가 귀납적으로 설계해야함을 알면서도 재귀함수를 타고타고 내려가다 정신을 놓치기 빈번했다.. 그래서 공부가 필요함을 느꼈고 재귀를 설계할 때 좋은 요령을 포스팅 하려고한다. 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법이다. 재귀함수가 성립되려면 기본적으로 아래와 같은 요구사항이 있다. 재귀의 기본적인 요구조건 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야한다. 모든 case는 결국 bse case로 수렴해야한다. 재귀가 아닌 함수를 재귀적으로 바꿔줄 때나, 재귀함수를 설계할 때 다음 요령을 익혀두면 재귀를 설계하기가 수월해 질 수 있다. 암시적(implicit) 매개변수를 명시적(expl..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 이 문제는 주어진 치킨집에서 도시의 치킨거리가 최소가 되는 치킨집 m개를 뽑는게 관건인 문제이다. 집에서 치킨집까지의 거리중 최소 거리를 치킨거리 라고한다. 따라서 집마다 치킨거리는 한 개씩 나올 것이며, 이 모든 치킨거리를 합한것이 도시의 치킨거리이다. 참고로 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구할 수 있다. 도..

처음에 이 문제를 접근할 때 단순히 bfs 알고리즘을 사용해서 갈 수 있는 방향을 탐색하고, 카운트를 늘려주었다. 그렇게, 더이상 방문할 수 있는 칸이 남아있지 않다면 탐색을 종료하도록 했다. 하지만 그렇게 했을 때 세번째 매뉴얼, '만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.'을 만족할 수 없었다. 그래서 네 방향을 모두 탐색했을 때 더이상 갈 수 있는 방향이 없다면, visited로 처리한 칸이라도 다시 방문했어야 했는데, 여기서 애를 좀 먹었다. 따라서 회전수를 기록하는 turn_times 변수를 선언해서 몇번 회전했는지 추적해야했다..

https://school.programmers.co.kr/learn/courses/30/lessons/42891 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 이 문제를 풀었을 때, 총 k번 while문을 돌면서 해당 음식마다 1초를 감소 시켜 주었다. k는 2,000,000 이하의 자연수가 들어가기 때문에, 위 방법으로 풀었을 때 효율성 테스트에서 전부 통과하지 못했다. 해당 문제는 그리디 알고리즘으로 문제를 해결 할 수 있다. 먹는데 시간이 적게 걸리는 음식부터 우선적으로 제거해나가는 방식을 사용면된다. 시간이 적게 걸리는 음식을 정렬 할 땐 ..

수업시간에 배운 c언어로 아주 열심히!! 만든 소스파일들이 있다고 하자. 열심히 만들었으니 소스파일을 실행시켜 노력의 결실을 맺고싶다. 하지만! 소스파일 하나만으로는 내가 의도한 결과를 볼 수 없다.. 그럼 어떻게 해야할까?! 바로 실행 파일(executable file)을 생성해야한다! 실행파일은 .exe 확장자를 가지는 파일인데, 게임을 다운받거나 할 때 많이 보았을것이다. (lol.exe..) 아래 그림에는 c언어로 작성된 코드가 실행 파일로 만들어지는 과정을 나타내고 있다. 1. 소스 파일 작성 프로그래밍에서 가장 먼저 해야할 작업은 바로 소스 파일을 작성하는것이다. 실행 파일을 만들기 위해서는, 당연히 우리가 만든 소스 파일이 있어야한다. vs이나 코드블럭 등, IDE에서(물론 메모장에서도 만들..

점프 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 이 문제를 처음 봤을 때 dfs를 사용해 목적지에 도착하는 경우만 카운트하면 되겠다는 생각으로 풀었다. 그러나 제출하고나니 선명한.. 주황색 '시간초과'를 볼 수 있었다.. 이 문제의 요건은 간단하다. 각 칸에 적혀있는 수 만큼만 점프를 할 수 있으며, 그 방향은 오른쪽과 아래 두 방향으로 고정된다. 이와 같은 규칙으로 가장 오른쪽 아래 칸으로 갈 수 있는 경우의 수를 찾아내면 되..

분할(Divide)과 정복(Conquer) 이름만 들어도 무언갈 막 분할해서 그것을 해결하는 접근 방법임을 느낄수 있지 않은가? 맞다! 분할 정복은 말 그대로 특정 문제를 분할하고 정복하는 두 단계로 나눠서 해결하는 것을 말한다. 분할 하는 단계에선 말 그대로 특정 문제를 여러개의 부분(sub) 문제로 나누는데, 덩치가 큰 문제를 한 번에 해결하는것이 힘들기에 여러개로 나누어 풀기 쉽게 만드는데 의의가 있다. 그렇게 문제의 크기를 나누다보면 바로 답이 나오는 수준까지 줄일수 있을 것이다.(N = 1, 2 정도까지, 이것은 재귀호출의 base condition과 같다) 이후 구한 답을 합쳐 큰 문제를 해결하는 방법이다. 위 그림을 보면 대략적인 분할 정복의 흐름을 알 수 있을 것이다. 분할 정복의 대표적인..

두 문자열 X, Y가 주어졌을 때, X, Y에서 공통으로 나타나는 부분 문자열을 찾고자한다. 이때 부분 문자열중 길이가 최대인 부분서열을 찾는 방법은 뭐가 있을까? 문자서열 X, Y가 다음과 같이 있다고 하자. X = A, B, C, B, D, A, B Y = B, D, C, A, B, A X, Y의 길이가 짧으니 눈대중으로도 최장 공통 부분 서열을 찾을 수 있을 것이다. 위 예시에서 최장 공통 부분 서열은, LCS(X, Y) = B, C, B, A 이다. 이 문제를 브루투 포스로 접근하면 X의 모든 부분서열 중에서 Y의 부분서열인 것들의 길이를 구한뒤 이 길이들 중에서 최대값을 찾으면 된다. 이때, X의 모든 부분 서열의 갯수는 2^n의 시간복잡도를 가지는데 절대 좋은 방법이 아닐것이다! 길이가 최대인..

배낭 문제(knapsack problem)는 조합 최적화 문제의 일종이다. 간략하게 말하자면, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제이다. 예를 들어 15kg의 무게제한이 있는 배낭에 12kg, 2kg, 1kg를 넣으면 그 가치는 7달러가 된다. 하지만 4kg 물건만 넣더라도 10달러를넘으니 앞의 예시는 가치가 최대가 되는 예가 아닌것이다. 브루투포스로 풀면 각 아이템이 ‘있고/없고’ 인 수열로 나타낼 수 있으니 총 시간복잡도는 2^4일 것이다. 하지만 아이템의 개수가 많아진다면 시간복잡도는 2^n으로 증가하니 좋지못한 방법임엔 분명하다. 배낭문제는 가..