코영방

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int n, m, start;
vector<pair<int, int>> graph[100001];
bool visited[100001];
int d[100001];

int getSmallestNode(){
    int min_value = INF;
    int index = 0;
    for(int i=1; i<=n; i++){
        if(d[i] < min_value && !visited[i]){
            min_value = d[i];
            index = i;
        }
    }
    return index;
}

void dijkstra(int start){
    priority_queue<pair<int, int> > pq;
    pq.push({0,start});
    d[start] = 0;

    if(d[now] < dist) continue;
    while(!pq.empty()){
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();

        for(int j=0; j<graph[now].size(); j++){
            int cost_via_now = d[now] + graph[now][j].second;
            if(cost_via_now < d[graph[now][j].first]){
                d[graph[now][j].first] = cost_via_now;
                pq.push(make_pair(-cost_via_now, graph[now][j].first));
            }
        }
    }

}


int main()
{

    cin >> n >> m >> start;

    for(int i=0; i<m; i++){
        int a, b, c;
        cin >> a >> b >>c;
        graph[a].push_back({b,c});
    }

    fill_n(d, 100001, INF);

    dijkstra(start);

    for(int i=1; i<=n; i++){
        if(d[i] == INF){
            cout << "INFINITY" << "\n";
        }
        else{
            cout << d[i] << "\n";
        }

    }
    return 0;
}


/*
입력 예시
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
*/

#시각
n=int(input())
t=0
for i in range(n+1):
  for j in range(60):
    for k in range(60):
      s = str(i) + str(j) + str(k)
      if '3' in s:
        t += 1
print(t)

#왕실의 나이트 
a = input()
r = int(a[1])
z=0
col = int(ord(a[0])) - int(ord('a')) + 1
x=[1,2,-1,-2]
y=[2,1,-2,-1]
for i in range(4):
    for j in range(2):
        if(col+x[i]<9 and col+x[i]>0 and r+y[(i%2)+(j*2)]>0 and r+y[(i%2)+(j*2)]<9):
            z=z-1
        z=z+1
print(8-z)

#게임개발 
n, m=map(int, input().split())
x, y, d=map(int, input().split())
check=0
v = [[0]*m for _ in range(n)]
v[x][y]=1
dx=[-1,0,1,0]
dy=[0,1,0,-1]
cnt=0
array = []
for i in range(n):
  temp = list(map(int, input().split()))
  array.append(temp)
while True:
  if(array[x+dx[(d+3)%4]][y+dy[(d+3)%4]]==0):
    if(v[x+dx[(d+3)%4]][y+dy[(d+3)%4]]==0):
      x=x+dx[(d+3)%4]
      y=y+dy[(d+3)%4]
      v[x][y]=1
      d=(d+3)%4
      check=0
      continue
    #d=(d+3)%4
    #check=check+1
    #continue 
  d=(d+3)%4
  check=check+1
  #continue
  if(check==4):
    if(array[x+dx[(d+2)%4]][y+dy[(d+2)%4]]==1):
      break
    else:
      x=x+dx[(d+2)%4]
      y=y+dy[(d+2)%4]
      check=0
for i in range(m):
  for j in range(n):
    if(1 == v[i][j]):
      cnt=cnt+1
print(cnt)

#include <bits/stdc++.h> 
using namespace std; 
//상하좌우 
int main() 
{ 
    int n; 
    cin >> n; 

    int x=1,b=1; 

    char a[5]; 
    for(int i=0; i<6; i++){ 
        cin >> a[i]; 
        if(a[i]=='R'){ 
           if(b+1<=n){ 
                b++; 
           } 
        } 
        else if(a[i]=='L'){ 
           if(b-1>0){ 
                b--; 
           } 
        } 
        else if(a[i]=='D'){ 
           if(x+1<=n){ 
                x++; 
           } 
        } 
        else if(a[i]== 'U'){ 
           if(x-1>0){ 
                x--; 
           } 
        } 
    } 

    cout << x << "  " << b; 

    return 0; 
}

www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5

www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4

www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4

www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3

www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3

www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2

<추가 설명>

딱히 없네요.^^

그리디하게, 0,1 아니면 곱하기를 먼저 선택하면 되는 문제네용 ㅎㅎ

www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2

<추가 설명>

n 23, k 3

target = (n//k)*k  -> target 이 21이 된다.

n - target을 하면 -> 2가되고

result에 2를 더한다는 것은 -1 연산을 2번 한다는 것이된다. 

요렇게 구현하면 성능이 좋아지겠지요.ㅎㅎ

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a[10]={0,},i;
    for(i=0;i<10;i++)
        scanf("%d",&a[i]);
    for(i=9;i>=0;i--)
    {
        //printf("=1=\n");
        int child = i;
        do{
            //printf("=2=\n");
            int parent = (child-1)/2;

            if(a[parent]<a[child])
                swap(a[parent],a[child]);
            child = parent;
        }while(child != 0);
    }
    for(i=0;i<10;i++)
        printf("= %d ",a[i]);
    int k=9;
    while(k!=0)
    {
        printf("==k= %d\n",k);
        if(a[0] <= a[k]) break;
        swap(a[0],a[k--]);
        int parent=0;
        int child;
        do{
            //printf("=2=\n");

            int child1 = parent*2+1;
            int child2 = parent*2+2;
            child = child1;
            if(child <= k-1 && a[child2]>a[child1])
                child = child2;

            if(child <= k-1 && a[parent]<a[child])
                swap(a[parent],a[child]);

            parent = child;
        }while(parent<=k);
        for(i=0;i<10;i++)
            printf("%d ",a[i]);
        printf("\n");
    }
    for(i=0;i<10;i++)
        printf("%d ",a[i]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    priority_queue <int> q;
    q.push(3);
    q.push(5);
    q.push(7);
    q.push(9);
    q.push(2);

    cout << q.top() << endl;
    q.pop();
    cout << q.top() << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    priority_queue <int> q;
    q.push(-3);
    q.push(-5);
    q.push(-7);
    q.push(-9);
    q.push(-2);

    cout << -q.top() << endl;
    q.pop();
    cout << -q.top() << endl;
    return 0;


}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    priority_queue <int, vector<int>, greater<int>> q;
    q.push(3);
    q.push(5);
    q.push(7);
    q.push(9);
    q.push(2);

    cout << q.top() << endl;
    q.pop();
    cout << q.top() << endl;
    return 0;


}

2.2.1 부분집합 생성하기

vector <int > subset;
void search(int k){
	if(k == n+1){
    	//부분집합을 구한 상태임.
    }
    else{
    	//k를 부분집합에 포함시킨다.
        subset.push_back(k);
        search(k+1);
        subset.pop_back();
        //k를 부분집합에 포함시키지 않는다.
        search(k+1);
    }
}

2.2.2 순열 생성하기

vector <int> permutation;
bool chosen[n+1];

void search(){
	if(permutation.size() == n){
    	//순열을 만든 상태임
    }
   	else{
    	for(int i = 1; i <= n; i ++){
        	if(chosen[i]) continue;
            chosen[i] = true;
            permutation.push_back(i);
            search();
            chosen[i] = false;
            permutation.pop_back(i);
        }
    }
}

C++ 표준 라이브러리 next_permutation사용하기

for(int i = 1; i <=n; i ++){
	permutation.push_back(i);
}

do{
	//
}while(next_permutation(permutation.begin(), permutation.end());

#include <bits/stdc++.h>

표준 라이브러리 전체를 포함시키는 g++컴파일러의 기능이다. 이 것을 사용하면 iostream, vecotr, algorith 등의 라이브러리를 개별적으로 포함시키지 않다도 사용가능하다.

string s;

getline(cin, s)

입력 한줄을 통째로, 공백을 포함한 채로 읽어 들이는 방법

while(cin >> x)

만일 데이터의 양을 사전에 알수 없다면 사용.

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

몇몇 대회 시스템은 입력과 출력을 위해 파일을 사용하기도 한다. 이를 간단하게 처리하는 방법은 평소처럼 표준스트림을 사용하는 코드를 작성한 후, 위 두줄을 코드의 시작 부분에 추가한다.

ios::sync_with_stdio(0);

cin.tie(0);

코드 시작부분에 위 코드를 넣으면 입력과 출력을 좀더 효율적으로 할 수 있다.

단, 이코드를 사용했을 때는 scanf, printf와 같은 C언어 입출력 함수를 C++입출력 함수와 동시에 사용할 수 없다.

"\n" vs endl

개행 문자 "\n"는  endl보다 빠르다. 이는 endl을 상ㅇ하면 명시적으로 flush가 일어나기 때문이다.

long long x = 123456789123456789LL;

int 범위(32bits) = -2 * 10의 9승 ~  2 * 10의 9승

long long범위(64bits) = -9 * 10의 18승 ~ 9 * 10의 18승

int a = 123456789;

long long b = a*a;

cout << b << "\n";  //-1757895751

"a*a"를 저장하는 변수는 long long이지만, 계산은 결과가 int으로 되기때문에 에러를 유발한다.

a자료형을 long long으로 바꾸던지, (long long )a*a 으로 코드를 수정해야 한다.

나머지 연산 - skip

if(abs(a-b) < 1e-9){

     // a와 b가 일치한다

}

부동 소수점 실수를 == 연산자를 이용하여 비교하는 것은 위험한데, 이는 비교하는 값이 실제로는 일치하지만, 정밀도 오류로 인해 다르다는 결과가 나올 수도 있기 때문이다. 좀더 나은 방법은 두 실수의 차이가 x보다 작을 때 서로 일치한다고 판단하는 것이 좋다.