복습용 블로그

www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 처음 생각했던 것은 O(nlogn) 정렬을 활용해 정렬 후 기존 배열의 인덱스를 비교해가며 더하는 것이었는데 배열에 중복된 값이 존재하면 안 된다는 것을 깨달았습니다. 아이디어가 떠오르지 않아 다른 분들의 풀이를 참고했습니다. 아이디어 : merge sort 과정에서 교차점의 개수와 버블 소트의 swap 횟수는 같다. 예를 들어 1 3 5 7 / 2 4 6 8 을 정렬한다고 하면 swap 횟수는 6번이..

www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net 삼성 SW A형 문제로 알려진 큐빙문제입니다. 특별한 알고리즘은 필요 없이 정말 정말 열심히 구현하면 됩니다. 함수를 이용해 좀 더 깔끔하게 만들 수 있지만, 문제를 그려 가며 풀 때 전개로를 마구 그리다 보니 엄청난 하드코딩이되었습니다. 백준 사이트 질문에 어떤 분께서 예제를 올려주셔서 그거를 좀 더 활용하시면 좋을 것 같습니다. 풀이 : 윗면을 가운데 놓고 전개도를 그립니다. 전개도는 마음대로 그려도 되지만,..

www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 주어진 문자열을 팰린드롬으로 나누는 경우 중 분할된 개수의 최솟값을 구하는 문제입니다. ABACABA의 경우 문제에 나와있듯이 {A,B,A,C,A,B,A}, {A,BACAB,A}, {ABA,C,ABA}, {ABACABA} 와 같이 나타낼 수 있고 이 때는 분할의 최소 개수가 1입니다. 풀이 : dp를 이용해 풀었습니다. 1. 주어진 문자열에 대..

www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 아이디어가 떠오르지 않아 다른 분들의 풀이를 참고했습니다. (공짜 케이블이 1개인 경우는 아이디어가 떠올랐지만 2개 이상은 어떻게 처리할 지 고민하다 배가 너무 고파 다른 분들 풀이를 봐버렸다. 배고프다.) 공짜 케이블의 개수가 K개 일때, 1~N번 노드까지의 경로 중 가중치가 x보다 큰 경로의 개수를 구합니다. 그리고 그 개수가 K보다 크면 1000000부터 x까지는 ..

www.acmicpc.net/problem/2174 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 아주 열심히 구현하면 되는 문제였습니다. 로봇의 위치가 주어지고, 각 로봇별 움직임이 주어졌을 때, 해당 로봇이 충돌하냐 안 하냐 구하는 문제입니다. 로봇이 충돌하는 경우는 아래의 2가지 경우입니다. 1. 벽에 부딛힌다. 2. 다른 로봇에 부딛힌다. 1번 경우 : 로봇이 F 명령을 받았을 때 맵을 벗어나면 그렇습니다. 2번 경우 : 로봇이 F 명령을 받았을 때 맵에 다른 로봇이 있을 때 ..