2JINISHAPPY 2JINISHAPPY

https://www.acmicpc.net/problem/20160 20160번: 야쿠르트 아줌마 야쿠르트 주세요 첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ www.acmicpc.net 값의 범위를 신경써야 하는 다익스트라 문제 정점은 10000개라서 인접행렬을 만들 시 10000*10000=1억개 * 4byte의 메모리가 필요한데 간선이 최대 10만개 들어오므로 꼭 인접리스트로 처리해야 한다 #include #include #include #define ull unsigned long long #defin..

https://www.acmicpc.net/problem/22114 22114번: 창영이와 점프 창영이는 버스에서 내린 뒤 회사로 걸어가고 있다. 창영이가 걸어가는 길은 대부분 회색 보도블럭으로 포장되어 있는데, 가끔씩 빨간 보도블럭이 놓여있을 때가 있다. 창영이는 어린 시절 빨간 www.acmicpc.net 오랜만에 푸는 DP문제 처음에 bottom-up으로 풀려고 했는데 점화식이 계속 생각이 안 나서 재귀로 푼 다음에 메모이제이션 적용했다 dp도 재귀(top-down)이기 때문에 base case, inductive step, memoization 이 세 가지 위주로 설계해야 할 듯 #include #include using namespace std; int n, k, l[100005], dp[2][..

https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 특정 좌표에서 BFS또는 DFS를 시행하여 같은 숫자인 칸을 전부 업데이트 시킨 뒤 주어진 배열과 같은지 검사하면 되는 간단한 BFS 문제 import sys from collections import deque def bfs(r, c, num): global origin, after, n, m dx=[1,0,-1,0] dy=[0,1,0,-1] visit..

https://www.acmicpc.net/problem/20304 20304번: 비밀번호 제작 서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부 www.acmicpc.net 익숙한 문제? ㅎㅎ 틀린문제 리스트에 있는게 싫어서 오랜만에 다시 풀어봤다 아주 훌륭한 문제였다 ( = 어렵다는 뜻 ) 안전거리와 안전도가 등장하는데 안전거리를 구하는 것 자체는 XOR 풀이가 직관적으로 떠오를 수 있지만 비밀번호 후보를 찾는 데에 Bitmask + BFS를 바로 떠올리기는 쉽지 않다 항상 특별한 분류의 알고리즘 문제를 풀 때에는 (바로 생각나는 브루트포스 풀이 + 최적화할 수 있는 솔..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 회전할 부분 배열을 탐색하는 방법을 나눠서 2가지 버전으로 풀었다 한 가지 헤맸던 부분은 사방의 얼음 유무를 보고 얼음의 양을 감소시키는 로직에서 탐색 도중에 감소시키는 것이 아닌 탐색이 완료된 뒤 감소시켰어야 했는데 그 부분을 혼동하다 보니 정확한 값을 찾는 데 헤맸다 ㅠ #include #include #define pow2(x) (1= 0 && y < n; } void m..

https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 류호석배 알고리즘 코딩 테스트는 문제 퀄리티가 정말 좋아서 자주 푸는데 이번에도 새로운 코딩 테스트가 열렸다 실시간으로 참여할까 했지만 평일에 5시간이나 백준 문제를 풀면 너무 지칠 것 같아서ㅠ 천천히 풀어보려고 한다 이 문제는 특이하게 숫자 -> 숫자로 변환하는 과정에서 비트마스킹을 사용했다 아래의 그림처럼, 5를 3으로 바꾸기 위해서는 오른쪽 위의 LED를 켜고 왼쪽 위의 LED를 꺼야해서 2회의 반전이 필요하다 나는 각각의 위치에 대해 번호를 매기고 LED가 켜져있으면 1, 꺼..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라를 이용해서 최소 비용 및 경로를 구하는 문제 경로를 구할 때에는 pre라는 vector를 만들어서 각 노드로의 최소 비용이 갱신될 때 마다 pre배열도 갱신시켜주면 된다 마지막에는 도착지점으로부터 시작 지점이 나올 때 까지 재귀적으로 tracking하면 끝 #include #include #include #include #define pii pair #d..

https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 해싱을 이용한 문제가 종종 나오는 추세인듯 .... ㅠ 실제 코테에서는 뭔가 해싱을 써야되지 않을까?라는 생각만 하고 어려워보여서 다른 문제 풀었었는데 실제로 풀어보니 생각만큼 어렵진 않았다 연습할 때 정확성/효율성이 나뉘어져 있는 문제는 우선 러프하게 정확성만 통과하게 짜본 뒤 효율성 풀이로 고치는 편이다 그래..