시나위

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 이전 문제와 같이 벨만포드 알고리즘을 사용한 문제이다. edge를 그대로 넣고 사용할수도 있고 연결 그래프를 만들어서 사용할수도 있다. 뭐가 좋을진 문제마다 다를 것 같지만 이 문제에서는 edge를 사용하는게 조금 더 빠르다. 그래프를 사용하면 필요없는 곳까지 반복해야해서 시간이 더 걸리는 듯하다. 1) edge # import sys; input = sys.stdin.readline..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만 포드 알고리즘을 사용하는 문제이다. 알고리즘에 대한 자세한 내용은 아래 링크로 달아놓겠다. # import sys; input = sys.stdin.readline INF = 20_000_000_000 def bf(start): global dist, N, M, edges dist[start] = 0 for i in range(N)..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 시뮬레이션 문제여서 문제에 나와있는 순서대로 풀었다. 더보기 import sys; input = sys.stdin.readline from heapq import heappop, heappush def main(): N, M, K = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(N)] t..

https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 백트래킹 문제이다. 한글자, 두글자씩 읽어서 확인하고 마지막까지 순회했을 때 (포커의 스트레이트 같이) 모든 값이 이어지는지 확인한다. # import sys; input = sys.stdin.readline def backtrack(ind, limit): global s, stack if ind == limit: max_v = max(stack) for i in range(1..

https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 문자열에서 문자 하나씩 확인하면서 교체할수 있는지 확인했고, 사전순이므로 AAAA 한 뒤 BB를 교체했다. #include int check(char* s, int length, int start, int size) { if (start + size > length) return 0; for (int i = 0; i < size; i++) { if (s[start + i] != 'X') return 0; } return 1; } int main() { // 0 initialize int i, j, l..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 백트래킹과 그래프 탐색이 합쳐져 있어서 뭔가 삼성 기출 같은 문제이다. 이 문제는 선거구를 두 지역으로 나누고(조합, backtracking) 선거구끼리 연결되어있는지 확인해서(graph traversal, bfs, dfs) 연결되어있는 경우 최솟값이 되는지 확인하면 된다. # import sys; input = sys.stdin.readline from collections import deque def check(..

1. 교육 끝 약 한달동안 진행했던 교육이 드디어 끝났다. 교육과 프로젝트가 적절히 있는 교육이었고 한달간 정말 열심히 살았다. 마지막 주에는 프로젝트가 있었는데 C만 사용해서 진행했었다. 프로젝트를 진행하는 주는 잠도 최대한 줄여가면서 팀원들과 회의하고 개발했다. 덕분에 금요일엔 체력이 바닥났고 교육 끝나자마자 저녁도 안먹고 바로 잤다. 그래도 프로젝트를 할 때 에러를 확인하고 고치는 작업에서 많은 걸 얻었다. C는 전공 수업으로도 들었고 이번 교육에서도 학습해서 나름 잘 사용하는줄 알았으나 생각보다 모르는 부분이 많았다. 프로젝트를 사용하는 도중 가장 많이 봤던 건 segmentation fault. 포인터를 사용할때 잘못된 메모리 주소를 읽는 경우 많이 떴다. 자료구조 몇개를 직접 만들어서 사용했었..

https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹 연습을 위한 쉬운 문제 # import sys;input = sys.stdin.readline def backtrack(ind=0, cnt=0): global n, m, nums, ans_set, visit if cnt == m: tmp = tuple([nums[i] for i, v in enumerate(visit) if v]) if tmp not in ans_set: ans_..

1. 3주째 교육 거의 한달동안 교육을 받고 있는데 막바지에 다다랐다. C, C++, 자동차 SW공학 등등 배웠고 어제부터 프로젝트 기간으로 들어갔다. 수업 자체는 어렵진 않았으나 온라인 교육 특성상 집중이 자주 깨지는 문제가 있었는데 다음주는 계속 프로젝트니까 괜찮겠지… 또 교육이라고 한달동안 열심히 살았는데 그 여파인지 지금 굉장히 육체적으로나 정신적으로나 힘들다. 취업이라는 목표에 끝이 보이지 않아서 더 힘든건지도 모르겠다. 적당한 사람으로 살아야하는데 눈만 높아서 그러는 걸까 다음주 일정이 다 끝나면 좀 쉬어야지.. 2. 이번주는 1일 1알고리즘, 1일 1커밋 기록도 깨졌다. 1일 1포스팅은 그래도 꾸준히 해오고 있긴한데 의미없는 포스팅만 작성하는게 아닌가 싶다. 두 달 정도 꾸준하게 살아왔으니 ..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 그리디 알고리즘으로 풀었다. 강의 시간을 정렬한 다음 모든 강의 시간을 순회하면서 힙 answer에 데이터를 추가하거나 수정하는 방식이다. 추가하는 시간은 해당 강의실의 강의가 끝나는 시간을 나타낸다. python의 heap은 최소힙이므로 0번째(top)가 최솟값이 되고 항상 모든 강의실 중 가장 빨리 끝나는 시간을 나타내므로, 강의실을 계속 사용해도 되는지 아니면 하나 더 사용해야하는지 판단할수 있다. import sys; input = sy..