https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 아이디어 1. 파이썬 이슈 처음에 dfs로 접근했는데 Python3로 채점하면 80% 에서 시간 초과가 발생했다. (pypy로는 통과) 포기하고 bfs로 접근했는데 또 시간 초과가 발생해서 조건을 몇 개 추가하니 통과됨. c++ 였으면 dfs로 통과했을 거 같다. 2. 구현 파트는 크게 두 개로 나눴다. 국경선 열기 인구수 분배 코드 설명 기본적으로 이중 for문을 사용해서 각 위치..

작년 2회 때 필기 합격하고 실기를 안 보러 가서 이번에 응시해서 합격했다. 책은 필기,실기 전부다 시나공으로 했다. 양이 많아서 그냥 독서하는 느낌으로 보면 편함. 필기1권은 거의 1주보고 2권은 시험 하루 전에 봤다. 이렇게 책 한번보고 기출문제 풀고 틀린 거 한번 보고 시험 봤다. 기출 매우 좋다. 본인이 CS기본지식이 있다하면 기출만 보고 시험 쳐도 무방하다. 아무래도 문항수가 많아서 중요한 것만 알아도 합격 가능 실기거의 1주일정도 공부한 거 같다. 필기 때와 비슷하게 1권 2권 다 보고 시간이 없어서 기출문제 보고 인터넷에 있는 요약집을 읽고 쳤다. 생각보다 요약집이 정말 유용하다. 본인이 python, c, java 그리고 sql을 잘 알고 있으면 기출만 봐도 괜찮다. 후기범위에 비해 문제는..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제를 보다가 최근에 공부한 플로이드 워샬로 풀 수 있을 거 같아 사용했더니 통과됐다. 풀이 과정 for _ in range(M): a,b = map(int,sys.stdin.readline().rstrip().split()) graph[a][b] = 1 graph[b][a] = 1 for i in range(1, N + 1): for j in ra..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 미로 찾기랑 비슷하다. 저번에 탐색 문제 풀 때 bfs로 시간 초과가 뜬 경험을 삼아 dfs로 풀었는데 해결이 안 됐다. 생각해보다가 bfs로 풀었는데 바로 답이 나왔다. 내 생각에는 bfs니까 자연스럽게 최단거리가 나오니까(depth 별로 탐색) 이런 문제는 bfs로 푸는 게 좋은 거 같다. 풀이 과정 dx = [2,2,1,1,-1,-1,-2,-2] dy = [1,-1,2,-2,2,-2,1,-1]..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-와샬 알고리즘을 쓰는 문제. 모든 노드 쌍의 최단 거리를 구할 수 있다. 시간 복잡도는 O(N^3) 풀이과정 cost = [[INF for _ in range(N + 1)] for _ in range(N + 1)] for i in range(1, N + 1): for j in range(1, N + 1): if i == j: cost[i][j] = 0 for i in range(m): a..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이썬이라 억까당함. 난이도는 낮지만 시간 초과로 고생했다. 맨 처음 bfs로 풀었을때 시간 초과가 채점 70%에서 자꾸 걸리길래 방법이 틀린 줄 알았다. 아마 파이썬이 아니였으면 맞았을 거 같다. from collections import deque import sys count = 0 N = int(input()) home = [] for _ in range(N): h..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 구역의 수를 찾는 문제 근데 이제 색약을 곁들인 dfs나 bfs 중 하나를 택해 문제를 해결하면 된다. 해결하는 방법이 정말 다양하지만 그중 하나만 작성함. 문제 풀이 이 문제는 색약일때와 색약이 아닐 때 각각 어떻게 처리하냐에 풀이가 다를 것이다. 나는 배열을 복사해서 색약일 때(R == G) 따로 함수를 만들어 탐색하도록 만들었다. 다른 방법으로는 색약이 아닌 경우 탐색을 해주고 원래 ..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 어린이에겐 매우 어려운 게임이다. 시간제한이 0.1초 인걸 보니 기존 정렬 방식으로는 해결이 힘들 거 같다. 사실문제 풀기 전에 우선순위 큐 문제 인걸 알고 있어서 이걸 어떻게 적용할지 생각하면 되는 문제다. 우선순위 큐 문제는 내가 정한 우선순위가 높은 데이터가 가장 먼저 pop 되는 큐다. 근데 예제 출력 부분을 보면 1 1 2 2 같이 중복된 값이 여러 번 출력된다. 따라서 ..