Written

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제를 보고나서 드는 생각은 DFS로도 풀 수 있을것 같고, Union-Find로도 풀 수 있을 것 같다고 생각했는데 DFS로 문제를 풀어본지가 좀 오래된것 같아 DFS로 구현해서 풀어보았습니다. 컴퓨터간의 방향이 따로 없어서 인접리스트 형식으로 서로 연결되어 있게끔 데이터를 저장합니다. 그리고 문제가 1번 컴퓨터를 기준으로 시작하기 때문에 DFS(1)로 구현한 DFS함수를 호출합니다. DFS에 들어오..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 이번 문제의 핵심은 '연결되어있기만 하다면' 다른 곳을 통하여 목적지까지 갈수 만 있으면 되는 것 입니다. 그래프의 연결관계를 확인하고 싶을 때, 사용되는 Union Find알고리즘으로 문제를 풀어보았습니다. 입력으로 주어지는 정보를 바탕으로 두 도시가 연결되어있다면 Union함수를 통해 이어주고, 마지막으로 답을 구하기 위한 최종 여행 루트의 연결관계를 파악해서 그 중 하나의 도시라도 이어져있지..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 출발점에서 인접한 방향(상,하,좌,우)으로 이동하면서 도착지점까지 가장 적은 루피손실을 만들어내는 문제였습니다. BFS로도 풀 수 있겠지만, 다익스트라 알고리즘으로 풀어보았습니다. 다익스트라 알고리즘 문제는 아직 경험치가 부족해서 풀다보니 BFS랑 다익스트라를 합친 것 같은 .. 혼종 알고리즘이 되어버렸지만 ... 그래도 출력은 잘되고 채점은 맞았다고 나왔습니다 ! 완벽하게 다익..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 큐에 좌표값을 저장해서 이동할 수 있는 곳이면 거리값들을 1씩 증가시키면서 마지막에 거리 정보를 저장한 배열의 [N][M]값을 출력하는 BFS탐색으로 문제를 해결해보았습니다. 그런데 첫번째 코드에서 메모리초과가 발생했습니다. 메모리제한이 192MB인데 , 배열의 크기도 크지않은데 어째서 메모리초과가 나는 것인지 ..궁금해 하다가 구글링 해본 결과 BFS를 사용할 때, 종종 발생하는 일이더라구요. 예를 들면 아직 (3,3)의 좌표..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS를 사용해서 큐에 익힐 수 있는 조건의 토마토의 위치와 익는데까지 걸리는 날짜를 넣고 익힐 수 있는 모든 토마토를 탐색하는 방식으로 풀어보았습니다. 출력을 위해서 zeroCnt라는 변수를 만들어서 0의 개수를 세면서 토마토를 다 익힐수 없는경우와 처음부터 다 익혀져있는 경우에 대해서 정상적으로 출력할 수 있도록 했습니다. 최종적인 날짜 출력은 max라는 변수를 만들어서 큐에있..

구현 할때마다 헷갈리는 우선순위 큐를 사용할 때 , 자료형이 구조체인 경우 정렬을 위한 연산자 오버로딩을 정리해보려고합니다. 우선순위 큐 안에 기본적인 int 형 자료형이 들어가면 내림차순으로 정렬되어 들어갑니다. (내부적으로 heap(디폴트로 Max_heap)으로 구현되어있기때문입니다.) 이런 간단한 구조에서는 쉽지만, 만약 여러 값들을 갖는 구조체가 자료형으로 우선순위 큐 안에 들어가게되면 어떤 값을 기준으로 정렬을 해야 할 지 모르기때문에, 그 기준을 정해주어야 합니다. 그 기준을 정하는 방법은 구조체 내부에서 < 연산자 오버로딩을 통해 가능합니다. Pos라는 구조체 내부에서 연산자 오버로딩을 해주면 , PQ에 push를 할 때 연산자 오버로딩의 정의에 맞추어 정렬하게 됩니다. 저 부등호 방향때문에..

if-else가 아닌 switch를 사용하는 조건문 if-else에 비해 사용할 수 있는 경우가 조금 한정적이긴 하지만 , 필요할 때가 있음. int choice; switch (choice) { case 0: // choice의 값이 case 옆의 숫자에 대응됨. Console.WriteLine("가위 입니다."); break; case 1: Console.WriteLine("바위 입니다."); break; case 3: Console.WriteLine("보 입니다."); break; default: Console.WriteLine("전부 아닙니다."); break ; } 삼항연산자 ( 조건 ? 맞았을때 : 틀렸을때 ) 예시 int number = 25; bool isPair = ((number % 2..

알고리즘 문제를 풀다보면 자주 헷갈리는 부분이 있어 정리해봅니다. 입력으로 문자열을 받을때 string배열에 받을때와 char배열에 받을때 저장되는 방식이 다릅니다. 다시 생각해보면 char는 말그래도 하나의 문자 (Ex. 'a')를 뜻하기 때문에 어떻게 보면 당연한 부분이지만 자주 헷갈렸었는데 , 이번에 이렇게 정리를 함으로써 앞으로는 안 헷갈릴 수 있을것 같습니다. 1) string s1[50]; cin >> s1[0] // 반드시 인덱스 번호를 지정해서 받아야합니다. 그냥 cin >> s1으로 받으려하면 오류발생. // 이렇게 받으면 띄어쓰기 전 까지의 입력 내용을 s1에 저장합니다. // 콘솔에 my name is 를 입력하면 my만 s1[0]에 저장됩니다. 2) char a1[50]; cin >..