분류 전체보기 (174) 썸네일형 리스트형 [ 백준 12851 ] 숨바꼭질 2 (C++) https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 고민하다가 못 풀어서 정답을 봤다. 근데 대부분의 코드가 비슷했다. 다들 누군가의 코드를 참고했나...? 약간 발상의 전환이 필요한 문제다. 일반 bfs와 달랐던 점은 두 개였다. 1. 큐에 push 할 때 현재 위치 외에 time이라는 변수 추가 2. 방문처리의 위치 나는 기존에 bfs 문제를 풀 때 방문처리를 범위 조건문 안에서 해줬다. 그러니깐 새로운 원.. [ 백준 16953 ] A → B (C++) https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 재귀함수로 쉽게 해결할 수 있는 문제다. 재귀함수가 정말 직관적이면서도 짜기 어려운 코드 같다. 그런데 꾸준한 연습으로 충분히 극복 가능한 영역이라고 생각한다. 예전에는 재귀함수 정말 어려워 했었는데 이 문제는 거의 10분 만에 푼 것 같다. 딱히 설명할 게 많이 없다. 문제 조건대로 2를 곱해주거나 끝자리에 1을 더해 주는 것을 반복하면 된다. 종료 조건은 숫자가 일치하거나, 초과하거나 이렇게 두 가지다. Min 함수를 선언해줘서 최소값을 계속 갱신하면 된다. 코드를 보면 어렵지 않게 이해할 수 있을 것이다. 주의할 점.. [ 운영체제 ] 경쟁상태(Race Condition)와 동기화(Synchronization)의 필요성, 임계 구역(Critical Section) Race Condition이란, 여러 개의 프로세스가 공유 자원에 동시 접근할 때 실행 순서에 따라 결과값이 달라질 수 있는 현상이다. 이 한 문장이 race condition에 대한 모든 것이다. Race condition을 번역하면 '경쟁 상태'라고 한다. 영어 쓰기가 귀찮아서 앞으로 경쟁 상태로 부르도록 하겠다. 경쟁 상태는 컴퓨터 입장에서 아주 큰 문제다. 왜 큰 문제냐? 똑같은 코드를 100번 돌리면 실행 결과가 항상 같아야 하는데, 경쟁 상태가 발생하면 결과가 달라질 수 있기 때문이다. 이러한 문제를 방지하기 위해 공유 메모리를 쓰는 프로세스끼리 '동기화'를 해줘야 한다. 정리하면 공유 메모리를 쓰는 프로세스끼리는 경쟁상태가 발생할 수 있는데, 이에 대한 해결책이 동기화다. Race Condi.. [ 백준 1743 ] 음식물 피하기 (C++) https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 이차원 배열 map을 만들고 음식물 위치에 모두 1을 대입해준다. 모든 경로를 탐색하면서 아직 방문하지 않았고, map의 값이 1이면 bfs를 통해 연속된 1을 찾아주면 된다. 이때 bfs는 연속된 1의 개수를 반환해주는데, 마지막에 최대값을 출력해주기만 하면 된다. #include #include #include #include using namespac.. [ 백준 2178 ] 미로 탐색 (C++) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS 문제!! 이제 경로 탐색은 어느정도 숙달된 것 같다. 이 문제는 딱히 예외 상황이 없어서 한 번에 해결할 수 있었다. visit 배열이 방문 배열이면서 해당 위치까지 도달하기 위한 최소의 칸 수가 된다. 큐에 push 할 때 visit 배열 초기화를 아래와 같이 해주면 된다. visit[new_row][new_col] = visit[row][col] + 1 #include #include #include using nam.. [ 백준 1303 ] 전쟁 - 전투 (C++) https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net BFS로 해결할 수 있는 문제다. 이차원 문자 배열을 map이라고 했을 때 문자값이 'W'인지 'B'인지에 따라 케이스를 나눠 탐색을 진행하야 한다. 나는 type 변수를 두어 1일 때 'W'를, 2일 때 'B'를 탐색하도록 코드를 짰다. 방법은 간단하다. 각 군집 벡터 w, b를 생성한 뒤에 map을 처음부터 끝까지 탐색하면서 'W'면 문자에 맞는 군집을 찾아주고 w에 .. [ 백준 1260 ] DFS와 BFS (C++) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS의 원리만 알면 쉬운 문제다. 주의할 점은 노드간 간선 연결을 할 때 양방향이기 때문에 둘 다 연결해줘야 한다. 또한 작은 숫자부터 방문해야 하기 때문에 노드를 오름차순으로 정렬해줘야 한다. 벡터 또는 배열을 사용할 수 있는데 나는 벡터를 사용해서 풀었다. #include #include #include #include using namespac.. [ 백준 17070 ] 파이프 옮기기 1 (C++) https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제를 읽고 dfs로 해결할 수 있겠다는 생각을 했다. 파이프는 가로, 세로, 대각선 모양만 허용되고 각 경우마다 움직일 수 있는 방법이 정해져 있다. 이를 각 케이스마다 구현해주면 된다. 목표 지점이 벽인 경우만 주의하면 된다. DFS 함수 형태 void dfs(int row, int col, int type, int* cnt) row: 이동 방향 머리의 행 인덱스 co.. 이전 1 ··· 11 12 13 14 15 16 17 ··· 22 다음