본문 바로가기

분류 전체보기

 (157)
#1987 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 골드 4의 문제이다. 처음 봤을때 이런문제가 왜 골드 4이지? 생각을 했었다. 코드도 쭉쭉 잘 써내려가서 테스트케이스까지 잘 통과하였다. 근데 제출하니까 2%에서 틀렸다고 나왔다. 보자마자 문제가 있음을 인지하고 직접 손으로 써보면서 dfs를 따라가보니까 문제에서 원하는 방향과는 다르게 답이 나오고있었다. 내가 쓰지않은 알고리즘이 있었던것이다. 바로 백트래킹 이다. #include #inc..
#2573 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 골드 4의 문제였다. 조건이 굉장히 많아서 어려웠다. 각 부분부분들을 해결하는건 어렵지 않았는데 마지막에 이들을 한개의 코드로 묶으려니까 좀 어려웠다. 결국 해결은 했는데 시간초과가 나버렸다. T.T #include #include #include using namespace std; int n,m; int year; int cnt; //덩어리를 표현하는 변수 int map[301][301]..
#14503 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 골드 5의 문제였다. 골드 5 치고는 좀 어려웠던 느낌? 조건이 너무 많아서 그랬던거 같다. 계속 오류뜨고 답이 다르게 나와서 결국 고수분들의 코드를 보고 해결 하긴 했지만.. 얻어가는건 많았다. #include using namespace std; int n, m; int map[51][51]; int dx[] = { -1, 0, 1, 0 }; int dy[] = { 0, 1, 0, -1 };..
#10451 순열 사이클 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 실버2 문제이다. #include #include #include #include using namespace std; int N,cnt; int map[1001][1001]; int graph[1001]; int visit[1001]; void dfs(int x){ visit[x]=1; for(int i=1;i>t; whi..
#5014 스타트링크 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 골드 5문제라서 괜히 쫄았었다. 문제는 생각보다 단순했다. '최소 blah~' 문제니까 bfs를 써서 풀 수 있을것이라고 생각했다. 저번에 풀었던 숨바꼭질 문제랑 비슷하다고 느꼈던 게, 위로 올라가거나 아래로 내려가거나 두 경우가 있고 이 두 경우는 가중치가 같다(사실 가중치가 없지만). ->bfs로 풀 수 있는 문제의 조건에 부합한다! 그래서 X라는 위치에서 X+2가 되는 경우와 X-1이 되는 경우로 나누어..
memset 과 최대 최소 1. memset 문제를 풀다보면 쓰고있는 배열, 벡터 등등을 특정 값으로 리셋하고싶을 때가 많다 (아니 리셋을 해야만 하는 경우가 많다). 물론 이럴때 마다 개인적으로 함수를 직접 만들어서 사용하면 된다. 근데 C++ STL에서는 기본적으로 제공하는 memset함수가 있으니 사용하지 않을 수가 없다. 헤더파일 : #include 함수의 원형 void* memset(void* ptr, int value, size_t num); 출처: https://blockdmask.tistory.com/441 [개발자 지망생] 사용법은 다음과 같다. /* 배열의 이름이 arr 일때 */ memset(arr, 0, sizeof(arr)); vector의 경우, memset과 같은 역할을 하는 fill이라는 함수가 있다...
#2468 안전영역 문제가 굉장히 길어 캡처가 안된다 ㅎㅎ; URL을 남겨보도록 하겠다. https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net #include #include #include #include using namespace std; int n,maxH; int cnt[101]; int map[101][101]; int visited[101][101]; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; queue q; void bfs(int..
#1697 숨바꼭질 문제는 위와 같다(실버1). 문제를 처음 봤을때는 이게 왜 bfs문제 이지? 생각했다. 백준 수업을 듣고 알게되었다. BFS를 이용해 풀 수 있는 문제는 다음의 조건을 충족한다 1. 최소 비용 문제여야 한다 2. 간선의 가중치가 1 이어야 한다. 3. 정점과 간선의 개수가 문제의 조건에 맞추어 해결할 수 있을 정도로 적어야 한다. ++ 간선의 가중치가 문제에서 구하라고 하는 최소 비용과 의미가 일치해야한다. (즉, 최단거리 문제라면 가중치는 거리를 의미해야하고, 최단시간 문제라면 가중치는 시간을 의미 해야 한다.) #include #include #define MAX 100000 using namespace std; int n,k; int visited[100001]; int dist[100001]; q..

티스토리툴바