BOJ (223) 썸네일형 리스트형 [BOJ] 14226. 이모티콘 * BFS로 완전 탐색한다. * 큐에 모든 연산을 한 결과(now) 와 clipboard에 저장된 값(buffer), 연산 횟수(cnt)를 저장해나가면서 now == s가 되면 그 때의 cnt가 최소값이 된다. * now의 값이 변화되는 연산을 실행할 때 (이모티콘 삭제, 버퍼에 있는 값 붙여넣기) 범위를 제한해야 한다. (제한하지 않으면 오버플로우 발생 가능) * bfs의 기본인 방문 체크를 하면서 탐색한다. #include #include #include #define INF 987654321 using namespace std; //boj 이모티콘 https://www.acmicpc.net/problem/14226 typedef pair pp; typedef pair ipp; bool dp[1001.. [BOJ] 1976. 여행 가자 * 서로소 집합(union find)를 이용한다. * 연결되어 있는 도시들은 양방향으로 연결되고, 여행 경로는 중복이 가능하기 때문에(=최단경로가 아님) m개의 도시들이 같은 집합에 속해있는지만 확인하면 된다. #include #include #include #include #define MAXX 3001 using namespace std; // BOJ 여행가자 https://www.acmicpc.net/problem/1976 int n, m; int parent[MAXX]; int find(int a) { if (parent[a] == -1) return a; return find(parent[a]); } void unionFind(int a, int b) { int pa = find(a); int .. 이메일 만들기 import collections company = input() input = list(map(str,input().split(', '))); res=[] nameDic={} for value in input: name = list(map(str, value.split())); last = name[len(name)-1].replace('-','') lastfirst = last.lower() + name[0][0].lower() cnt = int(nameDic.get(lastfirst,'0')) finalName=lastfirst if cnt > 0 : finalName = finalName + str(cnt+1) nameDic[lastfirst] = cnt+1 tmp=[] tmp.append(fin.. [BOJ] 16957. 체스판 위의 공 * 체스칸 위의 적힌 값은 변동이 없기 때문에 공의 위치에 따라 이동할 방향이 정해져있다. * 이 특징을 이용해서, 좌표마다 움직이는 방향을 저장하고 (dir[][]) 해당 위치에 오면 저장된 방향으로 이동하도록 한다. * 공을 이동시킬 때는 해당 좌표에 있는 공을 모두 가지고 이동한다. #include #include #include #define INF 300001 using namespace std; //BOJ https://www.acmicpc.net/problem/16957 int r, c; int map[501][501]; int ball[501][501]; int dir[501][501]; bool visited[501][501]; int dx[9] = {-1, -1, -1, 0, 0, 0,.. [BOJ] 17298. 오큰수 * 스택을 사용한다. * 나중에 들어오는 수가 오큰수가 정해지기 때문에 스택을 이용해서 가장 최근 넣은 값과 (top) 현재 값을 비교한다. 이전 값보다 더 큰 수가 들어오면 => 이전 값 수의 오큰수는 현재 값이다. * 더 큰 수가 없으면 -1이다. #include #include #include #define MAXX 1000001 using namespace std; typedef pair pp; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int res[MAXX]; int num[MAXX]; stack st; for (int i = 0; i < n; i++) res[i] = -1; for (int i = 0; i .. [BOJ] 4378. 트ㅏㅊ; * 주어진 문자열을 키보드 상에서 한 칸 씩 왼쪽으로 간 결과로 치환해야 하기 때문에 키보드를 그대로 배열에 저장한다. * 문자열을 탐색하면서 문자가 탐색되면 그 인덱스 -1의 결과를 출력한다. * 인풋은 여러 줄을 나눠서 들어오고, 중간에 공백이 있을 수 있으므로 getline()으로 입력받는다. #include #include using namespace std; //boj https://www.acmicpc.net/problem/4378 int main() { ios_base::sync_with_stdio(0); cin.tie(0); string keyBoard[4] = {"`1234567890-=", "QWERTYUIOP[]\\", "ASDFGHJKL;\'", "ZXCVBNM,./"}; strin.. [BOJ] 9019. DSLR * 경로를 남기고, 역추적한다. * visited[i] = j 는 i가 되기 전의 숫자가 j임을 표시한다. op[i] = i가 되기 위한 연산을 저장한다. * a = 시작점 일 때, visited[a] = -2로 저장한다. (이 표식을 발견하면 역추적을 중지한다.) * a가 b가 되었을 때, 역추적을 하면서 벡터에 사용한 연산들을 저장한다. * a가 b가 아니라면, D ,S, L, R 연산을 진행하면서 만들어진 숫자들을 모두 큐에 넣는다. 중복 탐색을 방지하기 위해 이미 한 번 생성된 숫자는 더 이상 탐색하지 안흔ㄴ다. * 이 문제는 L, R 연산을 효율적으로 작성하는 게 중요하다. deque, string 등은 시간이 초과된다. L : d2 d3 d4 d1 이므로 가장 마지막 숫자를 추출한다. (n =.. [BOJ] 17085. 십자가 2개 놓기 * 십자가를 놓을 수 있는 최대 길이를 chk[][] 에 미리 저장을 해 놓는다. * 십자가는 한 좌표를 중심으로 상 하 좌 우 인접한 칸으로 퍼져나간다. * 이 특성을 이용해서 chk에는 몇 번이나 뻗어나갔는지를 저장한다. * dfs(int cnt, ll res) 에는 2개의 십자가를 놓았으면 최대값을 비교하여 갱신한다. (종료조건) *(0,0) ~ (n,m)까지 검사하면서 chk[][]가 1이상일 때 (== map[][] 가 # 일때) 주변을 검사하면서 십자가가 겹쳐서 생성되지 않는지 검사한다. *무조건 한 십자가가 크다고 정답이 되는 것은 아니기 때문에 십자가의 크기가 chk[][] 의 값보다 작더라도 dfs()를 호출해서 다른 십자가도 놓을 수 있도록 한다. (line 81) * visited는 .. 이전 1 2 3 4 ··· 28 다음
