코딩을 기초부터 디테일하게 쉽게 배우자

코딩테스트 알고리즘에서 자주 사용되는 vector 자료구조 활용방법에 대해 알아 보겠습니다. 해당 글에서는 값추가, 값제거, 값 정렬, 중복제거, 객체 추가, 객체 정렬에 대해서 설명하고 있습니다. 1. 값 추가 벡터는 배열처럼 크기가 정해져있지 않고 동적으로 값을 추가 할 수 있습니다. 벡터의 push_back(value)를 호출하여 값을 추가합니다. vector numbers; numbers.push_back(0); numbers.push_back(1); numbers.push_back(2); numbers.push_back(2); numbers.push_back(3); numbers.push_back(3); numbers.push_back(3); for (int i = 0; i < numbers.s..

문제는 링크로 대체합니다. https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다. www.acmicpc.net n과 m이 주어졌을 때 조합 nCm값의 끝에 0이 몇자리가 있는지 구하는 문제입니다. 직관적으로 봤을 때 n!과 m! n-m! 세가지를 직접구한후 0의 개수를 구하면 될 것 같지만 n,m의 범위가 20억이기 때문에 20억! 의 값은 상상도 할 수 없을만큼 큰 수이기 때문에 long long 자료형을 쓴다고 하더라도 저장할 수 없습니다. 때문에 20억!의 값을 구하지 않고도 0의 개수를 구할 수 있어야합니다. 그렇다면 0의 개수는 어떻게 구할 수 있을까요? 끝자리에 0이 5..

문제는 링크로 대체합니다. https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 문제 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의 www.acmicpc.net 문제를 간략히하면 출발점에서 도착점으로 도달할 수 있느냐를 결정하는 것입니다. 맥주를 50m마다..

문제는 링크로 첨부합니다. https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 출발지점 0,0 에서 N,M으로 가는 최단거리를 구하는 문제입니다. 단순히 bfs를 활용해서 탐색하다가 도착지점을 만났을때 종료하고 거리를 구하려 했지만 최악의 경우 모든 지점을 탐색하게 되어 시간초과가 발생하였습니다. 그래서 큐에 넣는 지점마다 출발지점으로부터의 거리를 저장하고 우선순위 큐를 이용하여 거리가 짧은것을 우선으로 탐색하도록 하였습니다. 하지만 이 역시 최악의 경우 한방향으로 가다가 반대로..

문제링크 https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재석이는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2

백준 사이트의 1012번 dfs문제 유기농 배추의 풀이법을 정리해보겠습니다. dfs가 아닌 bfs로도 풀이가 가능한 문제이지만 저는 dfs로 풀었습니다. https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www...

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net 문제와 입력예제는 링크로 대체합니다. dfs와 bfs방식 모두 풀 수 있는 문제인데요. 저는 dfs방식으로 풀었습니다. 입력으로 주어지는 맵 정보를 2차원배열에 저..

일 년 동안 세계일주를 하던 영식이는 여행을 하다 너무 피곤해서 근처에 있는 코레스코 콘도에서 하룻밤 잠을 자기로 하고 방을 잡았다. 코레스코 콘도에 있는 방은 NxN의 정사각형모양으로 생겼다. 방 안에는 옮길 수 없는 짐들이 이것저것 많이 있어서 영식이의 누울 자리를 차지하고 있었다. 영식이는 이 열악한 환경에서 누울 수 있는 자리를 찾아야 한다. 영식이가 누울 수 있는 자리에는 조건이 있다. 똑바로 연속해서 2칸 이상의 빈 칸이 존재하면 그 곳에 몸을 양 옆으로 쭉 뻗으면서 누울 수 있다. 가로로 누울 수도 있고 세로로 누울 수도 있다. 누울 때는 무조건 몸을 쭉 뻗기 때문에 반드시 벽이나 짐에 닿게 된다. (중간에 어정쩡하게 눕는 경우가 없다.) 만약 방의 구조가 위의 그림처럼 생겼다면, 가로로 누..