[C++] ๋น„ํŠธ ์—ฐ์‚ฐ์ž

2020. 5. 1. 16:04ยท๐Ÿ“ Computer Science/โœ Algorithm

๋น„ํŠธ ์—ฐ์‚ฐ์ž

์ •์ˆ˜ ํƒ€์ž…์˜ ํ”ผ์—ฐ์‚ฐ์ž์—๋งŒ ์ ์šฉ๋  ์ˆ˜ ์žˆ๋‹ค.

 

๊ธฐ๋ณธ ์›๋ฆฌ

  • A^B๋Š” ๊ฐ’์ด ๊ฐ™์œผ๋ฉด 0 ๋‹ค๋ฅด๋ฉด 1์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค.
  • ~A๋Š” -A-1๊ณผ ๊ฐ™๋‹ค.
  • ์‹œํ”„ํŠธ ์—ฐ์‚ฐ์ž์—์„œ ๋นˆ ๋น„ํŠธ์—” ๋ชจ๋‘ 0์ด ์ฑ„์›Œ์ง€์ง€๋งŒ >> ์—ฐ์‚ฐ์ž์—์„œ A๊ฐ€ ์Œ์ˆ˜์ธ ๊ฒฝ์šฐ์—” 1์ด ์ฑ„์›Œ์ง„๋‹ค.

 

๋ฌธ์ œ

https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

 

์นด์นด์˜ค ์‹ ์ž… ๊ณต์ฑ„ 1์ฐจ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ๋ฌธ์ œ ํ•ด์„ค

‘๋ธ”๋ผ์ธ๋“œ’ ์ „ํ˜•์œผ๋กœ ์‹ค์‹œ๋˜์–ด ์‹œ์ž‘๋ถ€ํ„ฐ ์—„์ฒญ๋‚œ ํ™”์ œ๋ฅผ ๋ชฐ๊ณ  ์˜จ ์นด์นด์˜ค ๊ฐœ๋ฐœ ์‹ ์ž… ๊ณต์ฑ„. ๊ทธ ์ฒซ ๋ฒˆ์งธ ๊ด€๋ฌธ์ธ 1์ฐจ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ๊ฐ€ ์ง€๋‚œ 9์›” 16์ผ(ํ† ) ์˜คํ›„ 2์‹œ๋ถ€ํ„ฐ 7์‹œ๊นŒ์ง€ ์žฅ์žฅ 5์‹œ๊ฐ„ ๋™์•ˆ ์˜จ๋ผ์ธ๏ฟฝ๏ฟฝ

tech.kakao.com

#include <iostream>
using namespace std;

int main()
{
	int n = 0;

	cout << "์ง€๋„ ํ•œ ๋ณ€์˜ ํฌ๊ธฐ๋ฅผ ์ž…๋ ฅํ•ด์ฃผ์„ธ์š”: ";
	cin >> n;

	int* arr1 = new int[n];
	int* arr2 = new int[n];

	cout << "์ง€๋„ 1์˜ ์ •์ˆ˜ ๋ฐฐ์—ด์„ ์ž…๋ ฅํ•ด์ฃผ์„ธ์š”: ";
	for (int i = 0; i < n; ++i)
		cin >> arr1[i];

	cout << "์ง€๋„ 2์˜ ์ •์ˆ˜ ๋ฐฐ์—ด์„ ์ž…๋ ฅํ•ด์ฃผ์„ธ์š”: ";
	for (int i = 0; i < n; ++i)
		cin >> arr2[i];

	int* map = new int[n];
	for (int i = 0; i < n; ++i)
		map[i] = arr1[i] | arr2[i];	// ์ง€๋„ 1, 2๋กœ ์ „์ฒด ์ง€๋„ ๋งŒ๋“ค๊ธฐ

	int d = 1 << (n - 1);	// n์ด 4์ผ๋•Œ, 1000 -> ๊ฐ€์žฅ ์ฒซ ๋ฒˆ์งธ ๋น„ํŠธ์™€ and ์—ฐ์‚ฐ์„ ํ•˜๊ธฐ ์œ„ํ•ด
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (map[i] & d)
				cout << "#";
			else
				cout << " ";

			map[i] <<= 1;	// ๋น„ํŠธ ์™ผ์ชฝ์œผ๋กœ 1 ์ด๋™ ํ›„ ํ• ๋‹น
		}
		cout << endl;
	}

	return 0;
}

 

https://www.acmicpc.net/problem/11811

 

11811๋ฒˆ: ๋ฐ์Šค์Šคํƒ€

๋ฌธ์ œ ์ Š์€ ์ œ๋‹ค์ด ์ด๋ฐ˜์˜ ์ž„๋ฌด๋Š” ๋ฐ์Šค์Šคํƒ€์— ์นจํˆฌํ•˜์—ฌ ํŒŒ๊ดดํ•˜๋Š” ์ผ์ด๋‹ค. ๋ฐ์Šค์Šคํƒ€๋ฅผ ํŒŒ๊ดดํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ๊ธธ์ด N์˜ ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜ ์ˆ˜์—ด ai๊ฐ€ ํ•„์š”ํ•˜๋‹ค. ๊ทธ๋Ÿฌ๋‚˜ ์ด๋ฐ˜์€ ์ด ์ˆ˜์—ด์„ ๊ฐ€์ง€๊ณ  ์žˆ์ง€ ์•Š๋‹ค. ๋Œ€์‹  ๊ทธ์—๊ฒŒ๋Š” ์˜ค๋žœ ์นœ๊ตฌ ๋‹ค์Šค ๋ฒ ์ด๋”์—๊ฒŒ ๋ฐ›์€ ์ชฝ์ง€๊ฐ€ ํ•˜๋‚˜ ์žˆ๋‹ค. ์ด ์ชฝ์ง€์—๋Š” ๊ทธ ์ˆ˜์—ด์ด ๋งŒ์กฑํ•ด์•ผ ํ•˜๋Š” ์กฐ๊ฑด์ด ์ ํ˜€ ์žˆ๋‹ค. ์ด ์ชฝ์ง€์—๋Š” ํฌ๊ธฐ N์˜ ์ •์‚ฌ๊ฐ ํ–‰๋ ฌ์ด ์žˆ๋Š”๋ฐ, i๋ฒˆ์งธ ํ–‰ j๋ฒˆ์งธ ์—ด์— ์ ํžŒ ์ˆซ์ž๋Š” ai์™€ aj์— ๋น„ํŠธ์—ฐ์‚ฐ and๋ฅผ ์ˆ˜ํ–‰ํ•œ ๊ฒฐ๊ณผ๊ฐ’์ด๋‹ค. ํ•˜์ง€๋งŒ

www.acmicpc.net

#include <iostream>
using namespace std;

int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i) {
		int a = 0, tmp;
		for (int j = 0; j < N; ++j) {
			cin >> tmp;
			if (i != j)
				a = a | tmp;
		}
		cout << a << " ";
	}

	return 0;
}

 

https://leetcode.com/problems/single-number-ii/description/

 

LeetCode - The World's Leading Online Programming Learning Platform

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

#include <vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int first = 0, second = 0;

        for (int i = 0; i < nums.size(); ++i) {
            first = (first ^ nums[i]) & (~second);
            second = (second ^ nums[i]) & (~first);
        }

        return first;
    }
};

 

https://leetcode.com/problems/bitwise-and-of-numbers-range/description/

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        while (left < right)
            right = right & (right - 1);

        return right;
    }
};
์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)
'๐Ÿ“ Computer Science/โœ Algorithm' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [C++] ํˆฌ ํฌ์ธํ„ฐ(Two Pointer)
  • [C++] next_permutation, prev_permutation
  • [C++] ์ตœ๋‹จ ๊ฒฝ๋กœ(๋‹ค์ต์ŠคํŠธ๋ผ, ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ, ๋ฒจ๋งŒ ํฌ๋“œ)
  • [C++] ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰(DFS), ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(BFS)
Blxxming
Blxxming
CS ์ง€์‹๊ณผ ๊ณต๋ถ€ํ•˜๋‹ค ๋ฐฐ์šด ๊ฒƒ, ๊ฒฝํ—˜ํ•œ ๊ฒƒ ๋“ฑ์„ ๊ธฐ๋กํ•˜๋Š” ๋ธ”๋กœ๊ทธ์ž…๋‹ˆ๋‹ค.
  • Blxxming
    ๐Ÿ’ก๋ฒˆ๋œฉ๐Ÿ’ก
    Blxxming
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
  • ๊ณต์ง€์‚ฌํ•ญ

    • Tech Interview
    • ๐Ÿ“š Tech (246)
      • ๐Ÿ“ Computer Science (96)
        • โœ OS (12)
        • โœ Network & Web (10)
        • โœ Database (11)
        • โœ Data Structure (6)
        • โœ Algorithm (40)
        • โœ Design Pattern (9)
        • โœ Cloud Computing (3)
        • โœ (5)
      • ๐Ÿ“ Language (73)
        • โœ Language (6)
        • โœ C & C++ (11)
        • โœ C# (19)
        • โœ JAVA (37)
      • ๐Ÿ“ Game (43)
        • โœ Computer Graphics (2)
        • โœ Unity (14)
        • โœ Unreal (26)
        • โœ (1)
      • ๐Ÿ“ Book (34)
        • โœ Effective (3)
        • โœ Game Server (16)
        • โœ Clean Code (14)
        • โœ (1)
  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.0
Blxxming
[C++] ๋น„ํŠธ ์—ฐ์‚ฐ์ž
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”