울퉁 불퉁 멋진 몸매에~ 새빨간 옷을 입고~ 새콤달콤 향기 풍기는~ 멋쟁이 토!마!토! 토마토~ 1. 문제 출처 1일 1알고리즘을 풀기위해 노력하는 나... 제법 멋져 2. 설계 1) 익은 토마토 4방으로 안익은 토마토가 익는다. 그렇기 때문에 익은 토마토들의 좌표를 큐에 넣고, 그 토마토들부터 4방 탐색을 시작해야겠다고 생각했다. 때문에 데이터를 입력받음과 동시에 익은 토마토(1)인 곳을 큐에 넣어줬다. 큐에 넣어주면서 이 공간의 토마토는 이미 익었다는 표시로 visited = true를 해주었다. for(int i=0;i
오늘 수업 끝나기 1시간 전에 선택한 문제 프림으로 풀라다가 생각안나서 다익스트라로 풀었는데, 민성이 오빠의 이해할 수 없다는 표정과 호진이 오빠의 웃음소리가 선명하다. 시무룩 MST 문제를 풀기 위해 내가 선택할 수 있는 알고리즘은 프림과 크루스칼 둘 중 하나였는데, 간지나 보인다고 크루스칼로 풀라는 오빠들의 말을 뒤로하고, 프림으로 풀 것이다. +23.04.16 추가 시험공부하면서 크루스칼로도 풀어보았다. 1. 문제 출처 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 2. 설계 모든 노드를 최소 비용으로 연결해야 하기 때문에 MST 문제이고, 크루스칼 또는 프림으로 풀어야 한다. (그 외 더 ..
BFS DFS가 좀 익숙해졌으니 언젠가 태영이 오빠가 추천해준 '불'이라는 문제를 풀어보겠다. 불! 이라는 문제도 있는 거 같은데, 이 문제가 더 까다로운 모양이다. 1. 문제출처 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 갖은 고난을 맞이하여 겨우 풀어 낸 문제 ... Let's GO! 2. 설계 1) 실패한 설계 그렇다... 처음에는 각각 깊이를 파고들어 1 경로씩 탐색하고자 DFS로 접근했었다... 근데 문제가 있었으니... 바로 배열을 주고 받을 때 같은 시간 대 별로 같은 배열을 공유하지 못한다는 점이다. ..
오늘은 나의 실패썰과 다른 분의 좋은 코드를 보며 공부한 나의 일기라고 할 수 있다. 나는 처음에 부분집합으로 해당 문제를 풀다가 '메모리 초과'가 떴었다. 그래서 내가 아직 풀기에는 어려운 문제라고 판단하여 다른 분의 코드를 보았다. 내가 참고한 블로그는 아래와 같다. [백준-2668]-[DFS]-숫자고르기 문제링크 : https://www.acmicpc.net/problem/2668 이 문제는 사이클이 발생할 때 까지 DFS로 탐색을 진행하면 된다. 만약 사이클이 발생하지 않는다면 visited 정보를 초기화 해주고 사이클이 발생했다면 방 pangsblog.tistory.com 1. 문제출처 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1..
1. 문제 출처 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 2. 설계 [입력 예시] 5 RRRBB GGBBB BBBRR BBRRR RRRRR 첫 값은 배열의 크기이다. 다음줄부터는 빨강(R) 파랑(B) 녹색(G) 정보가 어떻게 되어있는지를 받는다. 일반인은 정확하게 3가지 색을 구분할 수 있지만, 적록색약인은 빨강, 녹색을 같은 색으로 본다. 나는 다음과 같은 루트로 문제를 풀었다. 1) 영역을 확인했는지 체크하기 위해 visited 배열을 만든다. 2) 메인 함수에서 2중 for문으로 입력예시의 ..
1. 그리디 알고리즘이란? 탐욕스런 알고리즘이다. 미래를 생각하지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 것이다. 때문에 간단하고 빠르지만, 항상 최적의 답이 보장되지는 않는다. 2. 그리디 알고리즘이 최적의 답을 갖는 문제는? 1) 문제의 일부분에서 전체의 해답을 찾을 수 있는 경우 2) 다이나믹 프로그래밍처럼 모든 부분을 고려하는 것이 아닌 탐욕적 선택만 하더라도 최적인 답을 찾을 수 있는 경우 예를 들면 거스름돈을 가장 적게 거슬러주는 문제가 있다. 그리디 알고리즘 참고 문서 : https://seungjuitmemo.tistory.com/23 알고리즘: 그리디 알고리즘(Greedy Algorithm) 공부하고 예제 한번 풀어보자! 그리디 알고리즘이란(Greedy Algorithm)이란? ..
1) 사이트 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 2) 문제 저는 이 문제를 보고 최단 거리를 구하는 문제인 줄 알았지만, 어느 방면에서든 가장 가까운 거리의 직사각형의 경계선에만 닿으면 되는 문제였습니다. 그래서 제가 고려한 거리로는 출발지점(x, y)에서 1)왼쪽 2)오른쪽 3)위쪽 4)아래쪽이었습니다. 대각선은 삼각비 1:1:루트2 생각하니 대각선으로 가는 길이 더 멀다고 판단되어 위처럼 4가지로만 따져보게 되었습니다. 3) 파이썬 코드 ver1 - 복잡한 코드 x,y,w,h=ma..
1) 사이트 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 2) 문제 간단히 말하면 a부터 z까지 몇 번째로 처음 발견되는지를 출력하면 됩니다. 3) 파이썬 코드 alpha=input() al_li=list(alpha) order_li=[str(-1)]*100 number=0 for i in al_li: storage=ord(i)-97 if order_li[storage]!='-1': number=number+1 continue else: order_li[storage]=str(number) nu..
