백준

4179번: 불! (acmicpc.net) 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 난이도 : 골드 4 풀이 과정 : arr 배열을 선언을 해줘서 입력을 받을 때 #(벽)은 0, .(길), J(지훈)은 1, F(불)은 -1로 초기화를 시켜줬다. 나중에 다른 사람 풀이 과정을 보면 불 bfs를 돌리고 지훈이 bfs를 돌려줬는데 나는 불과 지훈이를 bfs를 동시에 돌리면서 bfs를 돌릴때 전 x, y값을 기준으로 지훈이인지 불인지를 체크하며 돌렸다. 흐름은 이렇다. 먼저 arr 초기화 과정에..

1406번: 에디터 (acmicpc.net) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 난이도 : 실버2 풀이 과정 : 일단 시간제한이 0.2초이고 문자열이 십만, 명령어의 개수가 50만이므로 최악의 경우 최대 연산 개수가 십만*50만 = 500억이 된다. 그러면 O(n)으로 짜면 무조건 시간 초과가 나고 선형 시간에 알고리즘을 짜야된다. 선형 시간에 이 문제를 푸는 방법은 바로 연결리스트 자료 구조를 이용하면된다. 배열/벡터와 달리 연결리스트는 특정 인덱스의 원소를 삭제, 추가 하는데 시간복잡도가 O(1..

14503번: 로봇 청소기 (acmicpc.net) 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 난이도 : 골드 5 풀이 과정 : 와.. 그냥 빡구현으로 풀었슴... ㅋ ㅋ ㅋ 푼다음에 다른 사람꺼 풀이 보니까 dy dx 배열 선언해서 4방향으로 돌수 있게 반복문으로 처리한거같았는데 나는 그 방향 바뀔 때 dy dx가 규칙성 있게 바뀔 거라는 건 예상이 가지만 수식이 도저히 생각이 안나서.... 그냥 동서남북 조건 나눠서 일일히 x랑 y값 선언해주면서 했음.. 위에 chk함수는 청소하고자 하는 (r,c)가..

15686번: 치킨 배달 (acmicpc.net) 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 난이도 : 골드 5 풀이 과정 : 각 집마다의 치킨거리를 구해 마을의 총 치킨거리가 최소가 되도록하는 문제입니다. n이 50이므로 최대 집 개수+치킨집개수은 250이 됩니다. 따라서 집개수와 치킨집 개수가 반반이라고 했을 때 최대 125*125 = 15625 번 연산을 하므로 제한시간이 1초라서 완탐으로 풀 수 있는 문제 였습니다. 완전탐색문제가 되면 복잡할거없이 치킨집을 조합으로 m개 고른다..

2623번: 음악프로그램 (acmicpc.net) 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 난이도 : 골드3 풀이 과정 : 위상정렬 문제로 사이클 여부 판별 + 중복간선 제거 를 해결해야되는 문제였습니다. 저는 맨처음엔 벡터로 하려다가 set자료형을 이용하여(중복을 허용하지 않음) set배열로 입력을 받았습니다. 만약에 중복된 간선이 나오면 삽입을 해도 set배열의 크기가 같으므로 만약 삽입을 했는데도 전에랑 크기가 같으면 진입차수를 저장하는 배열은 업데이트를 하지 않게 해주었습니다..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 난이도 : 골드 5 풀이 과정 : 최근에 코테를 몇번 참가해보면서 구현을 정확하고 빠르게 푸는 것의 중요성을 깨달았다. 이 문제는 구현+bfs인데, 백준에서 bfs문제중 바이러스 문제가 있어서 그거 먼저 풀면 도움이 될듯하다. n과 m이 최대 8까지기 때문에 완탐! 으로 가능하다 왜냐면 0이나올수 있는 곳에 벽 3개를 두는 것이기 때문에 최대 64C3 번 연산 이기 때문 관건은 벽 3개를 두는 방법을 어떻게 ..

2110번: 공유기 설치 (acmicpc.net) 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 난이도 : 골드5 풀이방법: 이분탐색 문제인데, 내가 구한 방식은 일단 좌표를 오름차순으로 정렬을하고, 첫번째 인덱스부터 시작해서 반복문을 돌려 차이가 mid이상이면 두 점 차이가 가능하다는 의미에서 chk=true로 해주었고, 공유기 개수를 +1 해준다. 그다음 mid이상이나오는 인덱스부터 다시시작해서 다음번째 그다다다음번째가 mid이상인지 계속 체크해서 공유..

14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 난이도 : 골드5 풀이과정 : 완전 탐색 문제이다. 모든 경우의 수.. 회전.. 대칭 에 대한 모든 경우의 수를 따져주면된다. 기존 좌표가 (x,y) 라 할때 나올수 있는 회전, 대칭에 대한 경우의 수는 8개 (x,y), (x,-y), (-x,y), (-x,-y), (y,x), (y,-x), (-y,x), (-y,-x) 다음과 같다..!!! 중딩때 배우던가... 이거 rx배열은 부호곱해줘야되서 선언해줬다. 이 걸 ..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 난이도 : 골드 4 풀이과정 : 다익스트라를 이용한 문제 2차원 배열에서 다익스트라 알고리즘을 활용하면 되는 문제였다. 도둑루피 값은 2차원 배열에 저장하고, 우선순위 큐는 다중 페어를 이용하여 pair (pair 형태로 넣어주도록 했다. 가중치 dist 배열은 2차원 벡터 형태로 선언하였다. 다익스트라를 안다면 2차원 형태를 어떻게 구현하느냐가 주요 문제였음 코드 : #incl..