삼성 SW 역량 테스트 기출문제 - 구현 위주의 문제들 https://www.acmicpc.net/workbook/view/1152 문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon) www.acmicpc.net 단기간 성장 - 알고리즘 기법 사용하는 문제들 https://www.acmicpc.net/workbook/view/4349 문제집: 단기간 성장 (redbin0471) www.acmicpc.net 초등학교를 졸업하자 KOI 편 https://www.acmicpc.net/workbook/view/140 문제집: 초등학교를 졸업하자 - KOI편 (yukariko) www.acmicpc.net
파이썬으로 그래프 문제를 풀 때 아직 익숙하지 않아서 계속 헷갈려서 이 글에서 정리를 한다. 인접리스트 인접리스트는 정점의 개수가 많은데에 비해 간선의 개수가 적을 때 유용하다. 6 10 # 노드수 간선 수 0 1 # 출발노드 도착노드 0 2 0 3 1 2 1 3 1 4 3 5 4 3 4 5 # 인접리스트의 구현 node, edge = map(int, input().split()) graph = [[] for i in range(node)] for _ in range(edge): startNode, endNode = map(int, input().split()) graph[startNode].append(endNode) graph[endNode].append(startNode) 위의 소스코드는 무방향그래..
1. python 입력 1.1. input() 기본적인 입력방식이며 input() 함수는 str 로 입력을 받는다 str1 = input() num1 = int(input()) 1.2. input.split() split 은 구분자를 통해 문장을 나눠서 입력 받고 이를 배열 형태로 저장한다. default 구분자는 공백 (' ') 이다. str1 = input().split() 1.3. map([자료형], input().split()) map 은 입력을 받아서 split 한후 spread 형태로 변수에 값을 할당한다. 주의할점은 입력받는 변수의 개수가 내가 직접 지정한 변수의 개수와 일치하여야 한다. 그렇지 않으면 아래 이미지 밑쪽의 에러가 나온다 a, b, c = map(int, input().spli..
1. cin, cout 으로 파일 입출력 하기 freopen("stairs.inp", "r", stdin); freopen("stairs.out", "w", stdout); 2. 파일입출력, 표준입출력 효율성 개선 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
위의 문제는 브루트포스로 풀려고 하면 무조건 시간초과가 뜬다. 마지막 해는 M 과 N 의 LCM 이다. M 과 N 이 소수라면 그 크기는 대략적으로 40000 * 40000 정도가 되니 이는 1초이상의 결과가 나온다. 따라서 다른 방법을 생각해 봐야 한다. 핵심 : 1. 위 문제에서 우리가 구하고자 하는 년도를 k 로 둔다. 2. (k - x) % M == 0, (k - y) % N == 0 이다. (위의 2번의 유도는 아래의 사진을 첨부한다.) 3. k 를 M 만큼 증가시키면 그 나머지는 계속 x 를 유지한다.(k % M == x 일 때 (k + M) % M == x 이다) 위의 3번 방식으로 지속적으로 k 를 M 만큼 증가시키면 LCM(M, N) / M 정도의 big O 를 가지므로 시간제한에 안걸릴..
문제링크 : https://www.acmicpc.net/problem/11286 1. 입력 관련 힙과 관련된 문제였다. 힙을 직접 구현하지 않고 힙의 구조를 가지고 있는 priority queue 를 사용했다. 절대값이 가장 작다는 것은 0과 가장 가깝다는 것이다. 즉 -1 과 3 을 비교 했을 때 -1 이 더 가깝다는 것이다. 즉 가장 0과 가까운 수를 결정할 때 부호는 영향을 주지 않는다. 하지만 출력을 할 때는 부호를 신경써야 하기 떄문에 아래와 같은 pair 를 둔다. pair 소스는 아래와 같다. #include #include using namespace std; int N, inp; priority_queue pq; pair pqTop; int main(void){ ios_base::sync..
문제 링크 : https://www.acmicpc.net/problem/1931 문제 핵심 : 정렬 후 그리디 1. 문제를 처음에 풀 때 들어올 수 있는 최대 크기가 100,000 이었으므로 n^2 으로는 못풀어서 브루트포스는 배제했다. 2. 따라서 n log n 이나 n 으로 풀 수 있는지 확인했다. 3. input case 를 적절하게 정렬을 하면 시간을 충분히 줄일 수 있을 것 같았다. (사실 이것도 긴가민가 했음) 정렬의 기준 : input case 에서 들어오는 start, end 값들을 pair vector 로 표현했다. 문제에서 start 와 end 중에서 end 가 중요하다는 것을 깨달았다. end 를 기준으로 오름차순 정렬을 하게 되면 앞에서부터 차례대로 순회하면서 조건을 만족하면 회의 ..
기본적인 BFS 문제였다. 처음에 BFS 로 구현해서 바로 제출을 했는데 틀렸다. 처음에 depth 라는 변수를 두고 그 while 문 들어가는 곳에 depth ++ 로 BFS 의 깊이를 측정하려 했다. 그렇게 되면 depth 가 증가하기만 하고 q 에서 pop 되는 지점으로 depth 를 돌려야 하는데 그렇게 하지 못했다. 아래 소스는 내가 틀렸던 소스이다. #include #include #include #include #include using namespace std; int M, N, A, B; int friendArr[102][102]; int check[102]; int kbArr[102]; int BFS(int start, int friendNum){ queue q; check[start]..
기본적인 DP 문제였다. 처음에는 1차원 dp 로 생각하려 했다. 그런데 i 번째로 올 수 있는 경우의 수가 많아서 1차원 dp 는 안된다는 걸 알았다. 그래서 0, 1, 2 로 dp 를 나눠서 생각하기로 했다. x == 0 : 0 은 x 번째 계단을 선택하지 않는 것 x == 1 : 1 은 x 번째 계단을 선택하고 x-1 은 선택하지 않는 것 x == 2 : 2 는 x 번째, x-1 번째 계단을 선택하고 x-2 번째 계단은 선택하지 않는 것 https://www.acmicpc.net/problem/2579 #include #include #include #include #include #include #include using namespace std; int dp[3][301]; int stair[3..
문제 링크 1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다. 1234567891011121314151617181920212223...99100101102... 핵심 로직 1. 위의 수열에서 자리수별로 그 개수를 배열에 저장한다. ex) 1~9 : v[0] = 9 10~99 : v[1] = 180 100~999 : v[2] = 2700 : : 위의 식을 일반식으로 나타내면 아래와 같다. 2. 원래 수와 k 번째 숫자를 구한다. 여기서 말하는 원래 수는 위의 수열에서 2자리 수 이상의 수가 들어갈 때 등록되는 원본 수이다. 예를 들어 밑의 표에서 원래 주어진 수열에서 노란색 부분을 보자. 문제에서 주어진 수열은 1 이지만 그 1은 11에서 나온 것이다. 이 11을 원래 수라고..
백준 10844(쉬운 계단 수) 와 비슷한 문제이다. 핵심로직 1. 2차원 배열로 작은 조각에서 각각 접근해야 한다. 2. 점화식은 아래와 같다. #include using namespace std; int N; long long dp[10][1001]; long long result; int main(void) { cin >> N; for (int i = 0; i < 10; i++) { dp[i][1] = 1;// 초기값 셋팅 } for (int x = 2; x
처음에 1차원 dp 배열로 풀려고 했는데 답이 잘 안나와서 한참 헤메다가 2차원 배열이 필요함을 알았다. 핵심로직 1. 1차원 dp 로는 풀리지 않기 때문에 각각의 조각에 대한 것을 단계별로 저장을 한다 -> 2차원 배열 2. 점화식은 아래와 같다(위의 사진도 참조) dp[i][x] = dp[i-1][x-1] + dp[i+1][x-1] : (x는 N 으로 가는 수) 3. 위의 점화식은 범위를 생각해서 조각을 나눠야 한다. i == 0 : dp[i][x] = dp[i+1][x-1] 1 N; for (int x = 2; x
이번에 NHN 신입공채 코테를 보게 되었는데 입출력이 평소에 풀던 거랑 달라서 많이 헤메었다. 또한 PS 문제를 풀고 나서 다른 사람의 소스를 보는데 함수에서 매개변수 호출 할 때 referece 호출이 많아서 이걸 정리해 보려 한다. 1. call by value 제일 기본적으로 값 자체를 받는 경우이다. 이러한 방식은 문제가 발생하는데 아래의 예시를 보자 #include using namespace std; void swap(int A, int B) { int tmp; tmp = B; B = A; A = tmp; } int main(void) { int A = 10; int B = 30; swap(A, B); cout
핵심로직 1. 경로를 알 필요가 없고 도달한 곳까지의 최소거리를 구하면 되므로 껍질의 수를 세면 된다. 2. 껍질 마다의 범위를 책정하고 만약 N > N; for (int i = 0;; i++) { if (N == 1) { cout
[https://www.acmicpc.net/problem/12851](백준 12851 숨바꼭질 2) 이전에 풀었던 [https://www.acmicpc.net/problem/1697](백준 1697(숨바꼭질)) 과 유사한 문제이고 로직은 거의 비슷하다. 핵심로직 위에서 말했듯 기본적인 로직은 이전에 숨바꼭질과 같다. 1.1. x-1, x, x*2 를 탐색하는 BFS 로 풀면 된다. 1.2. 처음으로 도착하는 노드가 최소시간이다. -> 바로 return 시킨다. [https://www.acmicpc.net/problem/1697](백준 1697(숨바꼭질)) 과는 다른 점은 아래와 같다. 2.1. 최소가 나올 수 있는 경우의 수도 구해야 하므로 방문하고 바로 return 을 하는 게 아니라 다시 conti..
백준 10250 핵심로직 왼쪽 아래부터 위로 그 다음 열 제일 아래서 다시 위로가 최소 거리로 넣는 방식이다. N % H 가 0 이면 H 을 넣어야 한다. #include #include using namespace std; int T, H, W, N, result; int tmpArr[2]; int main() { cin >> T; for (int i = 0; i > H >> W >> N; if (N % H == 0) { result = H * 100 + N / H; } else { result = N % H * 100 + N / H + 1; } cout
백준 4153 핵심로직 피타고라스의 정리 이용 입력이 작은 순으로 들어오는 게 아니기 때문에 sorting 필요 #include #include using namespace std; int triArr[3]; int main() { for (int i = 0; ; i++) { cin >> triArr[0] >> triArr[1] >> triArr[2]; if (triArr[0] == 0 && triArr[1] == 0 && triArr[2] == 0) break; else { sort(triArr, triArr + 3); if (triArr[0] * triArr[0] + triArr[1] * triArr[1] == triArr[2] * triArr[2]) cout
백준 1805번 직사각형에서 탈출 핵심로직 좌표평면을 생각하면 편하다. 4 가지 중 최소값을 가져오면 된다. -> x 와 w 사이의 거리, y 와 h 사이의 거리, x 와 y축 사이의 거리, y 와 x 축 사이의 거리 #include #include using namespace std; int x, y, w, h, result; int main() { cin >> x >> y >> w >> h; result = min({x, y, h-y, w-x}); cout
이제 본격적으로 dp 를 공부하면서 만난 첫번째 문제이다. top-down 방식으로 풀기를 원했지만 재귀가 아직 익숙하지 않아 bottom-up 으로 풀었다. 핵심로직은 2가지 이다. 1. 이전의 값을 이용해서 풀어야 한다. 2. 최초로 들어가 있던 값이 최소가 아닐 수 있다. #include #include using namespace std; int dp[3000001]; int X; void dpFunc(int X) { for (int i = 1; i dp[i] + 1) { dp[i * 3] = dp[i] + 1; } if (dp[i * 2] > dp[i] + 1) { dp[i * 2] = dp[i] + 1; } if (dp[i + 1] > dp[i] + 1) { dp[i + 1] = dp[i] +..
