Dev (37) 썸네일형 리스트형 VIM 설정 신규 yml이나 json 파일을 vim에서 다루다보니 tab을 space로 인식하게끔 하는 설정이 추가로 필요해졌다. 이전 포스팅이 옛날 에디터에서 작성했던 포스트여서 그런지 복사도 잘 안되고 하여 다시 올린다. set nu " 줄번호 표시 set autoindent " 자동 들여씌기 set cindent " c언어 들여쓰기 set smartindent " 스마트 들여쓰기 set tabstop=2 " 탭간격 set shiftwidth=2 " 자동 들여쓰기 탭간격?? (아닌듯...) set expandtab "tab to space set nobackup " 백업 파일을 만들지 않음 set hls " 검색 결과 하이라이트 syntax on " 문법 강조 set visualbell filetype on set s.. [백준] 2002 - 벽 부수고 이동하기 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 너비우선 탐색(BFS)로 풀어야 하는 문제다. '벽을 최소 1회는 뚥을수 있다'는 조건이 문제를 어렵게 만드는데, 이부분은 벽을 최소 1회 뚥었는지, 안뚥었는지에 대한 조건 여부를 방문 여부에 차이를 두고 기록해야한다. #include #include using namespace std; #include typedef struct _loc { int y; int x; int distan.. [백준] 10026 - 적록색약 www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 위 문제는 순수 BFS(너비우선 탐색)와 DFS(깊이우선탐색) 두가지 모두로 해결이 가능하다. 색약의 경우만 R, G중 하나를 R 혹은 G로 모두 변경 후에 다시 BFS, DFS를 돌리면 색상의 구역을 구분할 수 있다. 아래 코드는 BFS, DFS 모두를 구현한 정답이다. 직장내 SW 검정이 있어 멘토링을 하느라 두가지 방식 모두 구현하였다. 아래 코드에서 관심있게 볼 포인트는 BFS는 Queue, DF.. [백준] 2573 - 빙산 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net DFS(깊이우선탐색) 응용문제다. 섬의 얼음을 녹인 후에 빙산이 둘로 쪼개졌는지를 알아내기 위해 DFS를 쓰는데, 사실 DFS말고 BFS(깊이우선탐색)으로도 풀이가 가능하다. 주의할 점은 1년이 지나 빙산의 얼음을 녹일때, 다른 copy_map을 만들어서 녹은 빙산의 지도를 만들어야지, 기존 map에서 그냥 주변 0의 갯수만큼 차감하다보면, 이전에 차감해서 0이된 지역을 오인해서 과다차감을 하게될 수 있다.. [백준] 1987 - 알파벳 www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 순수하게 DFS(깊이우선탐색)만으로 풀수 있는 문제이며, 아마 가장 흔하게 나오는 깊이우선탐색의 유형일 것 같다. 주의할 점은 탐색을 하면서 이미 한번 지나간 알파벳에 대해서 방문 여부를 관리해야 하는데, 깊이우선 탐색 전에 방문 상태를 true로.. 탐색을 마치고 재귀호출에서 빠져 나왔을때는 다음 경로 계산을 위해 방문 여부 상태를 false로 되돌려 주어야 한다. #include int R, C; i.. [백준] 2458 - 키 순서 www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 문제만 읽어서는 감이 잘 오질 않는데, 결과적으로 본인의 키가 몇번째인지를 알려면 기술되어있는 N명의 '학생중 자신보다 키가 작은 학생의 수 + 자신보다 키가 큰 학생의 수 = N-1'이 되면 되는데, 이건 플로이드-워셜 알고리즘을 조금 응용하면 문제를 풀 수 있다. 알고리즘에 대한 설명은 나보다는 위키가 훨씬 더 잘 알려주니... ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9.. [백준] 3830 - 교수님은 기다리지 않는다. www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net Union Find를 응용해서 푸는 문제다. !로 시작하는 두 물체간의 무게 비교 결과가 주어질때는 union을 해주고 'diff[a] = a의 무게 - root의 무게'로 정의해서 계산해준다. 두 물체간 비교를 묻는 질의가 들어올때는 두 정점이 서로 Union이 아니면 'UNKNOWN', Union이면 diff[b] - diff[a]의 결과를 출력해주면 된다. #include in.. [백준] 2098 - 외판원 순회 www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 컴공 전공필수 과목인 알고리즘 수업을 들으면 동적계획법/DP을 배우게되면 대표적으로 배우게 되는 사례가 피보나치 수열과 외판원 순회 TSP(Travelling salesman problem)이다. 그런데 대학 졸업한지가 이미 10년이 넘은 시점에 이 문제를 보니, 전형적인 외판원 순회 문제라면서 문제 설명이 이것도 친절하지가 않다;;; 외판원 순회 문제에 대한 설명은 내가 .. [백준] 5626 - 제단 www.acmicpc.net/problem/5626 5626번: 제단 첫째 줄에 가능한 제단의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명이 너무 불친절하다. 이해하는데만 한참이 걸렸다. 동적계획법/DP 문제다. DP는 점화식을 세우는게 관건인데, 이게 문제마다 점화식을 도출하는 방식이 워낙 다양하다보니 잘하는데에 왕도가 없다. -_-;;; 그냥 많이 풀어보는 것 밖에는 답이 없는 듯... 이 문제는 DP의 사이즈를 제단의 사이즈만큼 모두 잡아버리게 되면 10000 x 5000 x 4 바이트의 저장공간이 필요하게 되는데 이러면 메모리 초과가 난다. 그래서 점화식을 세우면서 메모리를 절약하는 방법에 대한 고민을 해결하는게 포인트다. N번째 제단 열에서 가.. [백준] 1339 - 단어수학 www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 그리디(탐욕 알고리즘)로 풀 수 있는 문제다. 그리디가 보통 잘 나오지 않는 편인데 그리디로 된다. #include #include #include int count[28]; int compare(const void *a, const void *b) { return *(int*)b - *(int*)a; } int main(){ int N; memset(count, 0x00, sizeof(count)); s.. 이전 1 2 3 4 다음