728x90 전체 글83 [c++] 백준 불!(4179), BFS, 반례모음 문제 https://www.acmicpc.net/problem/4179 J와 F(불)이 미로에 있음. J는 F를 피해 미로를 빠져나와야 한다. 미로 밖으로 나오면 성공 #: 벽 .: 지나갈 수 있는 공간 J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간) F: 불이 난 공간 J가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다. J가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다. 풀이 맵에서의 J와 F의 좌표를 모두 큐에 쌓고, 하나씩 BFS를 이용해 인접한 좌표로 이동한다. 핵심은 조건문을 통한 예외처리가 아닐까 싶다. 특이사항 - 불이 여러개일 수 있음. - J가 벽에 갇힐 수도 있음. 맵을 문자열로 구성하고, J나 F가 이동시에 현재 좌표에.. 2023. 7. 26. [c++] 백준 토마토(7576), BFS, 반례모음 문제 https://www.acmicpc.net/problem/7576 격자 모양에 안익은 토마토와 익은 토마토가 존재 익은 토마토는 하루가 지날 때마다 인접한 안익은 토마토를 익게 만듬 모든 토마토를 익게 만드는데 걸리는 날짜는? 반례모음 2 2 1 1 1 1 0 5 3 0 -1 0 0 0 -1 -1 0 1 1 0 0 0 1 1 -1 2 2 -1 0 0 1 1 3 3 1 0 0 0 0 -1 0 -1 0 -1 3 3 0 0 1 0 0 1 0 0 1 2 3 3 -1 0 -1 0 1 0 -1 0 0 2 풀이 익은 토마토들 각각으로부터 BFS를 수행해 인접한 토마토를 익게 만든다. 마치 멀티 프로세스처럼 하루마다 동시에 수행하는 것처럼 보임 그러나, 이는 현재 익은 토마토의 위치 정보들을 큐에 쌓아서 순차적으.. 2023. 7. 26. [c++] vector 입력 1. vector 초기화 안했을 시 push_back()으로 입력해야 함. v[i]처럼 인덱스로 입력 안됨. 2. vector 초기화 시 v[i] 처럼 인덱스로 접근하여 입력 가능 2023. 7. 25. [c++] 백준 미로탐색(2178), BFS 문제 https://www.acmicpc.net/problem/2178 위와 같은 미로에서 1로 표시된 곳만을 통과하여, 좌측상단 -> 우측하단으로 가는 최단 경로의 수를 구하는 문제이다. 아래의 예시와 같이, n x m의 미로판이 주어지는데, 1과 0이 붙여서 주어지게 됨. 풀이 핵심 : BFS와 큐를 잘 이해하고 있는가. BFS는 상,하,좌,우를 탐색하여 다음 탐색할 그리드의 좌표를 큐에 쌓음. 큐는 first in first out 구조로써 먼저 큐에 쌓인 그리드의 좌표를 방문한다. 목표까지 최단거리를 구하는 문제는 큐에 쌓인 좌표들을 하나씩 방문해가면 된다. 목표에 가장 빨리 도달했을 때가 곧 최단거리가 됨. 아래 그림은 7x7미로판에서 1을 찾아 점차 경로를 찾는 과정을 보여준다. ... (중간.. 2023. 7. 25. [c++] 2차원 배열(벡터) 선언 및 초기화 2차원 배열을 선언하는 2가지 방법에 대해서 소개합니다. 1. 기본 배열로 선언 및 초기화 2. vector를 이용한 선언 및 초기화 1. 기본 배열로 선언 및 초기화 행과 열의 사이즈를 전역 상수 const로 할당 change_arr()함수 인자로 넘겨줄 시 사용 가능한 foramt을 보여줌 함수 내에서 값 변경시, 원본 값도 변경됨 모든 배열 값들을 특정 값으로 할당하기 위해서는, 1) 이중 반복문 2) fill() 이용 fill(arr[i], arr[i] + column, value) : i번째 행마다 column까지의 원소에 value를 할당함 2. vector를 이용한 선언 및 초기화 vector v(n, vector(m)) : (n,m)형태의 벡터 생성됨 vector안에 또 다른 벡터를 선언하.. 2023. 7. 25. [c++] 1차원 배열(벡터) 선언 및 초기화 방법 1차원 배열을 선언하는 2가지 방법에 대해서 소개합니다. 1. 기본 배열로 선언 및 초기화 2. vector를 이용한 선언 및 초기화 1. 기본 배열로 선언 및 초기화 배열 선언시, const로 미리 지정된 size만큼 선언합니다. 여기서 "size"라는 이름으로는 할당이 안됨. void change_arr_value() 함수에서 배열은 arr[] or *arr2 형태 모두 동일하게 주소를 받아 원본 배열 값에 접근, 값 변경 가능. 배열의 모든 값을 특정 값으로 초기화 하는 방법은 2가지가 있음. 1) 반복문으로 일일이 값 할당 2) fill()을 이용한 할당. (동작은 동일하겠지만 간편히 한 줄로 작성 가능) 2. vector를 이용한 선언 및 초기화 #include를 통해 컨테이너를 불러옴. vec.. 2023. 7. 25. [c++] 백준 그림 (1926), BFS 문제 https://www.acmicpc.net/problem/1926 입력 그리드와 1과 0으로 이루어진 값들을 받고, 1로 이어진 도형 개수와 최대 크기를 출력하는 문제. 도형은 상하좌우로만 이어질 수 있음. 풀이 BFS 알고리즘을 기반으로 모든 그리드의 좌표들에서 도형을 찾으면 됨 코드 알게 된 점 BFS 알고리즘 git 코드 https://github.com/intlabSeJun/c-plus-coding-test/blob/master/9.%20BFS/%EA%B7%B8%EB%A6%BC(1926).cpp 2023. 7. 24. [Git] .gitignore 사용법 git으로 연동시에 로컬에 있는 특정 파일들을 제외시키고 싶을 때, .gitignore를 사용하면 간편합니다. 아래와 같이 오른쪽 파일들에서 제외시키고 싶은 것들을 echo 명령어로 .gitignore에 추가! 이후에 git저장소와 연동해주면 제외된 것을 보실 수 있습니다. 2023. 7. 24. [c++] BFS example from 바킹독 BFS (Breadth First Search) : 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 예를 들어, 위와 같은 배열에서 파란색 지역을 탐색하는 알고리즘이다. 시작은 좌측 상단(0,0)에서부터 상,하,좌,우의 인접한 배열의 값들을 방문하여 파란색 좌표를 search한다. 이때, 그림에서 오른쪽과 같이 queue의 자료구조를 이용해, 현재 탐색하는 배열의 (행,열)의 번호를 저장한다. 새로운 파란색 점이 나올시 쌓이며(push), 이전에 탐색한 파란색 점의 정보는 제거한다(pop). queue가 비워질때까지 계속한다. queue는 #include에 있는 pair라는 쌍 자료형을 받을 수 있는 객체를 사용해서 queue에 쌓아준다. 관련 내용은 아래 링크에서 자세히 확인 할 .. 2023. 7. 24. [c++] <STL> pair 사용법 pair는 두 종류의 데이터 타입을 하나로 묶어, 한번에 전달 할 수 있음 서로 연관된 2개의 데이터를 한 쌍으로 묶어서 처리할 때 편리하다. 아래와 같이 여러 데이터 타입을 묶어서 사용할 수 있음, queue 또는 vector 등과 같은 컨테이너와도 유용하게 같이 사용할 수 있음. 2023. 7. 24. [c++] 백준 쇠막대기 (10799) 문제 https://www.acmicpc.net/problem/10799 레이저로 쇠막대기를 분리하는 문제 쇠막대기와 레이저 모두 문자열 '('와 ')'로 나타냄 풀이 문자열을 입력 받고, 하나씩 문자를 가져와 '('일 경우에 스택에 쌓음 ')'가 나왔을 시, 레이저로 간주하고 이전까지 쌓은 스택의 사이즈만큼 count. (잘린 쇠막대기 개수) ')'가 나왔을 시, 레이저가 아닌 경우, 쇠막대기를 닫는 경우를 위해 layzer라는 변수를 설정해서 on/off 해줌 layzer=0일 경우, 가장 안쪽의 쇠막대기가 닫히면서 count+1해준다. 코드 알게 된 점 스택의 활용 예외처리가 너무 힘들다 스택 문제라는 틀에 갇혀서 문제풀이가 더 어려워진 것 같다. 아니면 내가 스택을 잘 활용하지 못하거나. git .. 2023. 7. 23. [Pytorch] Negative Pair Loss 코드 두 feature가 멀어지도록 학습하는 loss Negative Pair Loss = max(margin - distance_metric(feature_1, feature_2), 0) -------- (1) where, max(f(x),0)은 f(x) > 0 이면 backpropagation 수행, margin은 feature_1과 feature_2를 얼마나 멀게 할 것인지, distance_metric은 두 feature의 거리를 구하는 function. 즉, 두 feature의 거리를 구하고 margin을 더했을 시, 0보다 크면 역전파하여 멀어지게 한다. 이 term은 triplet loss에서 positive pair과 같이 사용되기도 한다. 그렇다면 어떻게 두 feature를 멀어지게 한다는 것.. 2023. 7. 21. 이전 1 2 3 4 5 6 7 다음 728x90
