신입사원 현재의 개발일기

- 문제 링크 https://www.acmicpc.net/problem/1012 - 풀이 그래프를 가로 x 세로 만큼 먼저 선언해놓고, K만큼 배추의 위치를 입력받을 때 graph 배열에 배추의 위치를 1로 표시한다. 그리고 배추가 있는 곳에서 bfs를 돌려주면 된다. 밑에 코드를 보면 알겠지만 배추의 위치를 입력받을 때 a, b 위치만 바꿔주는 것만 고려하면 특별히 예외처리 해줄만한 것도 없어서 푸는데 한.. 7분 걸렸던 것 같다. bfs를 한 번 실행할 때 마다 배추흰지렁이가 1마리씩 필요하다고 생각하면 편하다. - 코드 import sys from collections import deque input = sys.stdin.readline dx = [0,0,-1,1] dy = [-1,1,0,0] d..

- 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/169199 - 풀이 나는 사실 프로그래머스를 거의 안 푼다. 입출력 자체가 백준이 나에게 좀 더 편하기도 하고.. 백준에 너무 익숙해져버린 나머지 프로그래머스는 손을 잘 안댈 때가 많았는데 백준 풀다가 현타가 조금 와서 프로그래머스 문제를 한 번 풀어봤다. 이 문제가 레벨 2 문제였는데, 백준에서 이 문제와 비슷한 아이디어를 쓰는 구슬탈출 문제가 골1인걸 보면 체감상 이 문제도 한 레벨 3 정도는 되야 하지 않을까 ? 싶은 생각이 들기도 했다(근데 구슬탈출 문제가 더 어렵긴 하다). 풀이를 보자면, bfs 문제인데 그냥 탐색이 아니라 벽이나 장애물에 걸렸을 때 횟수를 카운트 해서 구현하..

어느새 플레티넘을 달성했다. 사실 달성한 지는 한.. 2주가.. 넘었다. 그런데 왜 이제 글을 쓰냐? 게을러서 그렇습니다.. 죄송합니다.. 플레티넘 까지 80점 정도밖에 안 남으니까 눈이 돌아가버려서 5 클래스에 있는 원래는 알지도 못했던 MST, 위상 정렬을 갑작스레 배워 날먹으로 올라간 플레티넘이라.. 흔히 말하는 물플레다. 상위 5%의 실력이 되냐 ? 이건 절대 아니다. 그래프 탐색 문제가 그나마 재밌어서 그래프 하나만으로 올라왔기 때문에 아직 실버 문제도 버겁다.. 그래서 아직도 참 많이 부족하다고 느낀다. 이젠 티어 상승이 아닌 내실을 다져 나가야겠다. 그래도 조금은 뿌듯했다. 나는 사실 살아오면서 노력을 통해 마음에 드는 결과물이 있었던 적이 거의 없다. 내가 노력을 안해서 그런 게 제일 크긴..

- 문제 링크 https://www.acmicpc.net/problem/17144 - 풀이 어제 올린 것과 같은 SW 역량 테스트 기출문제 중 하나이고, 구현 + 시뮬레이션 문제였다. 미세먼지를 확산시키는 함수, 위쪽 공기청정기 함수, 아래쪽 공기청정기 함수, 총 3개의 함수를 만들어서 사용했다. 1. 미세먼지를 확산시키는 함수 def chk(): arr = [[0] * C for _ in range(R)] for i in range(R): for j in range(C): x, y = i, j count = 0 if graph[i][j] == 0: continue if graph[i][j] == -1: arr[i][j] = -1 continue for k in range(4): nx = x + dx[k..

- 문제 링크 https://www.acmicpc.net/problem/21610 - 풀이 백문 문제집에 있는 SW 역량 테스트 기출문제 중 하나이고, 악명(?) 높은 상어 문제 중 비교적 쉬운 편에 속하는 구현 + 시뮬레이션 문제였다. divide and conquer 방법으로 구현했다. 문제 하나를 더 작은 단위의 문제로 쪼개서 구현하는.. 그런 방법이다. 구름을 이동시키는 함수, 물복사버그 함수, 다시 구름을 만드는 함수 총 3개의 함수를 만들어서 사용했다. 함수 하나씩 차근차근히 살펴보자. 1. 구름 이동 함수 def move(x, y): queue = [] while cloud: a, b = cloud.popleft() for i in range(y): a = a + dx[x] b = b + d..

- 문제 링크 https://www.acmicpc.net/problem/14938 - 풀이 보통 기본적인 다익스트라 문제는 간선의 비용을 출력하거나 했는데 이 문제는 간선의 비용이 아니라 정점(노드)의 최댓값을 구하는 문제였다. 지문에 보면 양방향 통행이 가능하다고 하니 양방향 그래프로 구현해주면 된다. 1. 거리 배열인 distance 배열을 return 하는 다익스트라를 구현한다. 경로 탐색 중 간선의 비용이 M보다 크다면 생략한다. 2. 1번 노드부터 N번 노드까지 반복을 하며 distance 배열에 INF 값이 아닌 값들의 위치에 있는 아이템의 합을 배열에 넣어준다. 3. 배열 중에서 제일 큰 값을 출력한다. - 코드 import sys import heapq input = sys.stdin.re..

- 문제 링크 https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net - 풀이 거의 기본 다익스트라 문제였다. 마지막 부분에 조금 헤맸지만 그래도 맞혔다. 1. 지문에서도 양방향 통행이 가능하다고 했기 때문에 그래프를 양방향 그래프로 만들어 준다. 2. 다익스트라 함수에서 별 다른 특이사항은 없다. 그냥 다익스트라 함수 원형을 구현해주면 된다. 거리 배열인 distance 배열을 return 해주면 된다. 3. 이제 for문을 도는데, list 형태로..

- 문제 링크 https://www.acmicpc.net/problem/1270 1270번: 전쟁 - 땅따먹기 첫째 줄에는 땅의 개수 n(n

https://www.acmicpc.net/problem/27211 27211번: 도넛 행성 준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 www.acmicpc.net 쇼미더 코드에서 나온 은근 재미있는 문제였다. 보통의 bfs 알고리즘을 통한 그래프 탐색은 0과 N, M 사이의 범위 안에서만 탐색을 했는데, 이 문제는 범위가 없고 nx, ny가 끝 지점에 다다랐을 때 다시 처음 지점으로 이동시키면 되었다. 문제 자체는 어렵지 않고, 기본 bfs에서 조금만 응용하면 되는 문제이다. 코드를 보면 이해가 빠를 것 같다. import sys from col..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제의 핵심은 방문 여부를 체크하는 visited을 3중 배열로 만들어야 한다는 것이다. 그래야 벽을 부순 횟수의 파악이 수월하다. 나도 이 아이디어를 생각해내는 데 많은 시간이 걸렸다. ㅠㅠ 최단경로로 가는 길에 벽이 있다면 단 한 번만 부시고 계속 이동하면 된다. 더 자세한 풀이는 주석을 참고하면 된다. import sys input = sys.stdin.readlin..